The far-from-Turán positive discrepancy conjecture

For a graph HH on nn vertices, call GG ε\varepsilon-far from HH if at least εn2\varepsilon n^2 edge changes are required to obtain a graph isomorphic to HH. A Turán graph is a complete multipartite graph whose parts are as equal in size as possible.

Far-from-Turán discrepancy conjecture. For every ε>0\varepsilon>0, there exists c>0c>0 such that, if GG is an nn-vertex graph that is ε\varepsilon-far from every Turán graph, including the empty graph, then

disc+(G)cn5/4.\operatorname{disc}^{+}(G)\geq cn^{5/4}.

The conjecture proposes that graphs far from all Turán graphs have substantially larger positive discrepancy than the known O(n)O(n) examples. The source gives a de Caen construction showing the n5/4n^{5/4} scale is motivated, but the assertion remains open.

Sources & referencesView supporting material

Primary source

Eero Räty, Benny Sudakov and István Tomon, “Positive discrepancy, MaxCut, and eigenvalues of graphs”, arXiv:2311.02070 (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.