Generalized weak-subdivision conjecture for complete graphs

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 t3t\geq 3, there exists δ>0\delta>0 such that, if GG has at most

(1t1ϵ)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 t1t-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.

Sources & referencesView supporting material

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.