The finite-graph INT_f-minimizing partition conjecture
The finite-graph INT_f-minimizing partition conjecture
Let be continuous and strictly concave, let , and let be a finite graph. A partition of is -minimizing with parts if it has parts and minimizes among all partitions of with parts. A partition is weak -regular if it satisfies the weak regularity condition with error parameter .
Finite-graph -minimizing partition conjecture. For every continuous and strictly concave function and every , there exist numbers such that, for every graph of order at least , every -minimizing partition of with parts is weak -regular.
The conjecture proposes that minimizing the entropy-like functional over a sufficiently large fixed number of parts yields a weak regularity approximation for all sufficiently large finite graphs. The supplied text does not state whether this has been proved or disproved.
Sources & referencesView supporting material
Primary source
Martin Dolezal and Jan Hladky, “Cut-norm and entropy minimization over weak* limits”, arXiv:1705.09160 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.