Erdős–Hajnal–Simonovits–Sós–Szemerédi periodic structure conjecture for Ramsey–Turán extremal graphs

From papers

Let GG be an asymptotically extremal graph for the Ramsey–Turán density ϱp(q)\varrho_p(q), where the pp-independence number is the largest size of a vertex set inducing a KpK_p-free graph. Let q=pt+r+2q=pt+r+2, where tNt\in\mathbb{N} and rZpr\in\mathbb{Z}_p. Then there exists a partition

V(G)=V0V1VtV(G)=V_0\cup V_1\cup\cdots\cup V_t

such that e(G[Vi])=o(n2)e(G[V_i])=o(n^2) for every 0it0\leq i\leq t, dG(V0,V1)=r+1po(1)d_G(V_0,V_1)=\frac{r+1}{p}-o(1) with degrees in G[V0,V1]G[V_0,V_1] differing by o(n)o(n), and dG(Vi,Vj)=1o(1)d_G(V_i,V_j)=1-o(1) for every pair {i,j}{0,1}\{i,j\}\neq\{0,1\}. Periodic structure conjecture. The asymptotically extremal graph has this structure; in particular,

ϱp(q)=ϱp(q):=(t1)(2pr1)+r+1t(2pr1)+r+1.\varrho_p(q)=\varrho_p^\star(q):=\frac{(t-1)(2p-r-1)+r+1}{t(2p-r-1)+r+1}.

This conjecture predicts a periodic structure for asymptotically extremal graphs in Ramsey–Turán problems, extending the fully determined case p=2p=2. The cited work of Erdős, Hajnal, Simonovits, Sós and Szemerédi is the source of the conjecture; the material provided does not state whether it has been resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

József Balogh, Domagoj Bradač and Bernard Lidický, “Weighted Turán theorems with applications to Ramsey-Turán type of problems”, arXiv:2302.07859 (2023).

Solutions 0

No solutions have been posted yet.