Regular Turán extremal conjecture for graphs with chromatic number at most k

Let HH be a graph with chromatic number χ(H)k\chi(H)\le k and let k3k\ge 3. Write T(n,k)T(n,k) for the nn-vertex Turán graph with kk parts, and let N(H,G)\mathcal N(H,G) denote the number of copies of HH in a graph GG. The regular Turán number rex(n,H,Kk+1)\operatorname{rex}(n,H,K_{k+1}) is the maximum number of copies of HH in an nn-vertex regular Kk+1K_{k+1}-free graph. Regular Turán extremal conjecture. Then

rex(n,H,Kk+1)=(1+o(1))N(H,T(n,k)).\operatorname{rex}(n,H,K_{k+1})=(1+o(1))\mathcal N(H,T(n,k)).

Moreover, if nn is sufficiently large and divisible by kk, then

rex(n,H,Kk+1)=N(H,T(n,k)).\operatorname{rex}(n,H,K_{k+1})=\mathcal N(H,T(n,k)).

The conjecture asks whether the known asymptotic and exact extremal behavior for ordinary Turán problems persists under the regularity restriction. The preceding discussion notes that known counterexamples to the corresponding unrestricted statement are far from regular; whether regular counterexamples exist is left open here.

Sources & referencesView supporting material

Primary source

Dániel Gerbner and Hilal Hama Karim, “Generalized regular Turán numbers”, arXiv:2311.01579 (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.