The finite-graph INT_f-minimizing partition conjecture

Let f:[0,1]Rf:[0,1]\rightarrow\mathbb R be continuous and strictly concave, let ϵ>0\epsilon>0, and let GG be a finite graph. A partition Q\mathcal Q of V(G)V(G) is INTf\mathrm{INT}_f-minimizing with MM parts if it has MM parts and minimizes INTf(G;)\mathrm{INT}_f(G;\cdot) among all partitions of V(G)V(G) with MM parts. A partition is weak ϵ\epsilon-regular if it satisfies the weak regularity condition with error parameter ϵ\epsilon.

Finite-graph INTf\mathrm{INT}_f-minimizing partition conjecture. For every continuous and strictly concave function f:[0,1]Rf:[0,1]\rightarrow\mathbb R and every ϵ>0\epsilon>0, there exist numbers M,n0M,n_0 such that, for every graph GG of order at least n0n_0, every INTf\mathrm{INT}_f-minimizing partition of V(G)V(G) with MM parts is weak ϵ\epsilon-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

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.