Alon–Bollobás–Krivelevich–Sudakov conjecture on Max-Cut in H-free graphs

About 8 years old · traced to

Let HH be a graph. A graph is HH-free if it contains no subgraph isomorphic to HH, and for a graph GG let f(G)f(G) denote the maximum number of edges in a cut of GG. Let m≥1m\geq 1 be the number of edges of GG.

Alon–Bollobás–Krivelevich–Sudakov conjecture. There exist constants ε=ε(H)>0\varepsilon=\varepsilon(H)>0 and c=c(H)>0c=c(H)>0 such that, for all HH-free graphs GG,

f(G)≥m2+cm3/4+ε.f(G)\geq \frac{m}{2}+cm^{3/4+\varepsilon}.

This conjecture is presented as a closely related consequence or target of the preceding degeneracy-based conjecture and concerns Max-Cut lower bounds depending only on the edge count. Its general validity is not established in the source.

References

Primary source

Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov and Luca Trevisan, “Lower bounds for Max-Cut in H-free graphs via semidefinite programming”, arXiv:1810.10044 (2020).

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.