Bradač–Sudakov–Wigderson conjecture for nearly regular 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)-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 d2X2\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ε)dE(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.

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).

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.