2024/08/23 by António Girão, Zach Hunter, Girão, António +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2408.12913
openalex publication_date 2024/08/23 · openalex created_date 2024/09/21 · openalex updated_date 2026/07/28
A highly influential result of Nikiforov states that if an n-vertex graph G contains at least γnh copies of a fixed h-vertex graph H, then G contains a blowup of H of order Ωγ,H(log n). While the dependence on n is optimal, the correct dependence on γ is unknown; all known proofs yield bounds that are polynomial in γ, but the best known upper bound, coming from random graphs, is only logarithmic in γ. It is a major open problem to narrow this gap. We prove that if H is triangle-free, then the logarithmic behavior of the upper bound is the truth. That is, under the assumptions above, G contains a blowup of H of order ΩH (log n/log(1/γ)). This is the first non-trivial instance where the optimal dependence in Nikiforov's theorem is known. As a consequence, we also prove an upper bound on multicolor Ramsey numbers of blowups of triangle-free graphs, proving that the dependence on the number of colors is polynomial once the blowup is sufficiently large. This shows that, from the perspective of multicolor Ramsey numbers, blowups of fixed triangle-free graphs behave like bipartite graphs.