Extremal-graph classification conjecture for triangle-free graphs

Let nn and ss be integers with n/3<sn/2n/3<s\le n/2, and let ex(n,s)\mathrm{ex}(n,s) denote the maximum number of edges in a triangle-free graph on nn vertices with independence number at most ss. Let gk(n,s)g_k(n,s) be the functions defined in the preceding conjecture, and let Gkn(s)\mathscr{G}^n_k(s) and Hkn(s)\mathscr{H}^n_k(s) be the graph families described in the source. Extremal-graph classification conjecture. If GG has ex(n,s)\mathrm{ex}(n,s) edges, then GG is isomorphic to a graph in one of the families Gkn(s)\mathscr{G}^n_k(s) or Hkn(s)\mathscr{H}^n_k(s), and

ex(n,s)=minkgk(n,s).\mathrm{ex}(n,s)=\min_k g_k(n,s).

The source proves the classification in a neighbourhood to the right of each critical ratio, but strongly suspects that it holds throughout the full range.

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.