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

About 3 years old · traced to

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 t∈Nt\in\mathbb{N} and r∈Zpr\in\mathbb{Z}_p. Then there exists a partition

V(G)=V0∪V1∪⋯∪VtV(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 0≤i≤t0\leq i\leq t, dG(V0,V1)=r+1p−o(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)=1−o(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):=(t−1)(2p−r−1)+r+1t(2p−r−1)+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.

References

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).

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.