Bradač–Sudakov–Wigderson conjecture for nearly regular locally dense graphs

About 2 years old · traced to

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)-nearly-regular when all but at most ρn\rho n vertices have degrees in [(d−ρ)n,(d+ρ)n][(d-\rho)n,(d+\rho)n]. Also call GG (ρ,d)(\rho,d)-dense when every subset XX of at least ρn\rho n vertices spans at least d2∣X∣2\frac{d}{2}|X|^2 edges. Bradač–Sudakov–Wigderson conjecture. For every graph HH and all real d,ε>0d,\varepsilon>0, there exists a ρ=ρ(d,H,ε)>0\rho=\rho(d,H,\varepsilon)>0 such that

t(H,G)≥(1−ε)⋅d∣E(H)∣t(H,G)\geq (1-\varepsilon)\cdot d^{|E(H)|}

holds for every sufficiently large (ρ,d)(\rho,d)-dense (ρ,d)(\rho,d)-nearly-regular graph GG. This is a restricted, almost-regular version of the KNRS conjecture. The source presents it as an open conjecture and notes that the authors prove results for subdivisions related to it.

References

Primary source

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

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.