Kohayakawa–Nagle–Rödl–Schacht conjecture for locally dense graphs

Let HH and GG be graphs, let t(H,G)t(H,G) denote the homomorphism density of HH in GG, and call an nn-vertex graph GG (ρ,d)(\rho,d)-dense when every subset XX of at least ρn\rho n vertices spans at least d2X2\frac{d}{2}|X|^2 edges. Kohayakawa–Nagle–Rödl–Schacht conjecture. For every graph HH and all reals d,ε>0d,\varepsilon>0, there exists a ρ=ρ(d,H,ε)>0\rho=\rho(d,H,\varepsilon)>0 such that

t(H,G)(1ε)dE(H)t(H,G)\geq (1-\varepsilon)\cdot d^{|E(H)|}

holds for every sufficiently large (ρ,d)(\rho,d)-dense graph GG. This conjecture extends the random-graph lower bound from bipartite graphs to locally dense host graphs and is a central open problem in extremal graph theory; the source records only special classes of graphs for which it is known.

Sources & referencesView supporting material

Primary source

Hao Chen, Yupeng Lin and Jie Ma, “Kohayakawa-Nagle-Rödl-Schacht conjecture for subdivisions”, arXiv:2407.10861 (2024).

Additional references

3 papers in this index state this conjecture (2017–2024). The statement above is taken from the most recent of them; the others are arXiv:2206.05800, arXiv:1707.02916.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.