Quantitative restricted partition conjecture for graphs

For ε>0\varepsilon>0, a graph GG is (N,ε)(N,\varepsilon)-restricted if its vertex set can be partitioned into at most NN subsets that are ε\varepsilon-restricted in GG, where a subset is ε\varepsilon-restricted if one of its induced subgraph or complement has maximum degree at most ε\varepsilon times its size. Let indH(G)\operatorname{ind}_H(G) denote the number of copies of a graph HH in GG. Quantitative restricted partition conjecture. For every ε>0\varepsilon>0 and every graph HH, there exist N=N(H,ε)>0N=N(H,\varepsilon)>0 and κ=κ(H,ε)>0\kappa=\kappa(H,\varepsilon)>0 such that every graph GG satisfying

indH(G)κ\absG\absH\operatorname{ind}_H(G)\leq\kappa\abs{G}^{\abs H}

is (N,ε)(N,\varepsilon)-restricted. This would unify Nikiforov's quantitative theorem with the qualitative restricted-partition theorem and substantially strengthen the corresponding weakly restricted result.

Sources & referencesView supporting material

Primary source

Tung H. Nguyen, “A further extension of Rödl's theorem”, arXiv:2208.07483 (2023).

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.