Reiher–LPR extremal function conjecture for triangle-free graphs

About 6 years old · traced to

For integers nn and ss with n/3<s≤n/2n/3<s\le n/2, let ex(n,s)\mathrm{ex}(n,s) be the largest number of edges in a triangle-free graph on nn vertices whose independence number is at most ss. For every k≥1k\ge1, define

gk(n,s)=k(k−1)n22−k(3k−4)ns+(3k−4)(3k−1)s22.g_k(n,s)=\frac{k(k-1)n^2}{2}-k(3k-4)ns+\frac{(3k-4)(3k-1)s^2}{2}.

Reiher–LPR conjecture. One has

ex(n,s)=min⁡kgk(n,s).\mathrm{ex}(n,s)=\min_k g_k(n,s).

This refines Andrásfai's piecewise-quadratic prediction. The paper proves the formula in a neighbourhood to the right of each critical ratio, while the asserted formula over the full range remains open.

References

Primary source

Tomasz Łuczak, Joanna Polcyn and Christian Reiher, “Andrásfai and Vega graphs in Ramsey-Turán theory”, arXiv:2002.01498 (2021).

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.