1 problem

0 votes0 replies0 views
Conjecture that expected max-cut and minimum bisection sizes sum to less than the edge count
Let $G$ be a random regular graph, and let the maximum cut and minimum bisection be optimization problems whose sizes are their respective numbers of crossing edges. Write their ex…
Conjectureopengraph-bisection max-cut random-regular-graphsarXiv posted 3 days ago

Conjecture that expected max-cut and minimum bisection sizes sum to less than the edge count