Reiher–LPR extremal function conjecture for triangle-free graphs

For integers nn and ss with n/3<sn/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 k1k\ge1, define

gk(n,s)=k(k1)n22k(3k4)ns+(3k4)(3k1)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)=minkgk(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.

Sources & referencesView supporting material

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.