Extremal-graph classification conjecture for triangle-free graphs

About 6 years old · traced to

Let nn and ss be integers with n/3<s≤n/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)=min⁡kgk(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.

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.