Generalized weak-subdivision conjecture for complete graphs

About 7 years old · traced to

Let GG be a graph with nn vertices, and let G‾\overline{G} denote its complement. An induced weak-subdivision of KtK_t is an induced subgraph of GG obtained by the weak-subdivision operation applied to the complete graph KtK_t; a bi-clique is a complete bipartite subgraph.

Generalized weak-subdivision conjecture. For every ϵ>0\epsilon>0 and integer t≥3t\geq 3, there exists δ>0\delta>0 such that, if GG has at most

(1t−1−ϵ)n22\left(\frac{1}{t-1}-\epsilon\right)\frac{n^{2}}{2}

edges and does not contain an induced weak-subdivision of KtK_t, then G‾\overline{G} contains a bi-clique of size at least δn\delta n.

The conjecture generalizes the proved K5K_5 case discussed immediately beforehand and is stated as sharp in the source: examples formed from t−1t-1 clique parts can have nearly the threshold number of edges while their complements have no linear-sized bi-clique. The supplied text does not indicate that the general case has been resolved.

References

Primary source

Istvan Tomon, “A sharp threshold phenomenon in string graphs”, arXiv:1908.05550 (2019).

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.