We establish a novel connection between the well-known chromatic threshold problem in extremal combinatorics and the celebrated (p, q)-theorem in discrete geometry. In particular, for a graph G with bounded clique number and a natural density condition, we prove a (p, q)-theorem for an abstract convexity space associated with G. Our result strengthens those of Thomassen and Nikiforov on the chromatic threshold of cliques. Our (p, q)-theorem can also be viewed as a χ-boundedness result for (what we call) ultra maximal Kr-free graphs. We further show that the graphs under study are blow-ups of constant size graphs, improving a result of Oberkampf and Schacht on homomorphism threshold of cliques. Our result unravels the cause underpinning such a blow-up phenomenon, differentiating the chromatic and homomorphism threshold problems for cliques. Our result implies that for the homomorphism threshold problem, rather than the minimum degree condition usually considered in the literature, the decisive factor is a clique density condition on co-neighborhoods of vertices. More precisely, we show that if an n-vertex Kr-free graph G satisfies that the common neighborhood of every pair of non-adjacent vertices induces a subgraph with Kr−2-density at least ε > 0, then G must be a blow-up of some Kr-free graph F on at most 2 O(rε log 1ε ) vertices. Furthermore, this single exponential bound is optimal.

We obtain an approximate sparse hypergraph version of the blow-up lemma, showing that partite hypergraphs with sufficient regularity of small subgraph counts behave as if they were complete partite for the purpose of embedding bounded degree hypergraphs.

We study the problem of finding pairwise vertex-disjoint copies of the ℓ-vertex cycle Cℓ in the randomly perturbed graph model, which is the union of a deterministic n-vertex graph G and the binomial random graph G(n, p). For ℓ ≥ 3 we prove that asymptotically almost surely G U G(n, p) contains min{δ(G), min{δ(G), [n/l]} pairwise vertex-disjoint cycles Cℓ, provided p ≥ C log n/n for C sufficiently large. Moreover, when δ(G) ≥ αn with 0 ≤ α/l and G and is not ‘close’ to the complete bipartite graph Kαn,(1 - α)n, then p ≥ C/n suffices to get the same conclusion. This provides a stability version of our result. In particular, we conclude that p ≥ C/n suffices when α > n/l for finding [n/l] cycles Cℓ. Our results are asymptotically optimal. They can be seen as an interpolation between the Johansson-Kahn-Vu Theorem for Cℓ-factors and the resolution of the El-Zahar Conjecture for Cℓ-factors by Abbasi.

Confirming a conjecture of Gyárfás, we prove that, for all natural numbers $k$ and $r$, the vertices of every $r$-edge-colored complete $k$-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles. We further prove that, for all natural numbers $p$ and $r$, the vertices of every $r$-edge-colored complete graph can be partitioned into a bounded number of $p$th powers of cycles, settling a problem of Elekes, Soukup, Soukup, and Szentmiklóssy [ Discrete Math., 340 (2017), pp. 2053--2069]. In fact we prove a common generalization of both theorems which further extends these results to all host hypergraphs of bounded independence number.

In this paper we prove an asymptotic multipartite version of a well-known theorem of Kühn and Osthus by establishing, for any graph $H$ with chromatic number $r$, the asymptotic multipartite minimum degree threshold which ensures that a large $r$-partite graph $G$ admits a perfect $H$-tiling. We also give the threshold for an $H$-tiling covering all but a linear number of vertices of $G$, in a multipartite analogue of results of Komlós and of Shokoufandeh and Zhao.