The finite-graph INT_f-minimizing partition conjecture

About 9 years old · traced to

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.

References

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.