Critical-regime clique-count conjecture for bounded-degree graphs

About 7 years old · traced to

Let n=a(r+1)+bn=a(r+1)+b, and let mm satisfy

nr2≥m>a(r+12)+(b2).\frac{nr}{2} \ge m>a \binom{r+1}{2} + \binom{b}{2}.

For fixed tt, or for k=∑t≥2ktk=\sum_{t \ge 2} k_t, consider graphs of order nn, size mm, and maximum degree at most rr. Critical-regime clique-count conjecture. Any graph maximizing the chosen quantity can be represented as (a−1)Kr+1+H(a-1)K_{r+1}+H. This concerns the remaining, or critical, regime after the known cases in which the extremal graph is a union of copies of Kr+1K_{r+1} and a colex graph; the source provides no resolution of this conjecture.

References

Primary source

Stijn Cambie, Rémi de Joannis de Verclos and Ross J. Kang, “Regular Turán numbers and some Gan-Loh-Sudakov-type problems”, arXiv:1911.08452 (2020).

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.