9 problems

For fixed $r\geq 3$, let $\alpha_r$ be the largest exponent such that every $K_r$-free graph $G$ with $m$ edges satisfies … where $\operatorname{surp}(G)$ is the maximum-cut surplu…

Mirka–Williamson conjecture. If a graph admits a unique partition corresponding to its maximum cut and the Goemans–Williamson relaxation on the graph is exact, then the rank-1 opti…

Maximum-cut conjecture. There exists $\varepsilon>0$ such that every $H$-free graph with $m$ edges has a cut of size

Zdeborová's conjecture. The limiting constants satisfy

Let $G$ be a weighted triangle-free graph with maximum degree at most $3$; equivalently, $G$ is a weighted triangle-free subcubic graph. Weighted subcubic conjecture. One should ha…

Let $G$ be a weighted triangle-free graph, and let $T$ be a spanning tree of $G$. Spanning-tree bound conjecture. One should have … The conjecture would determine the optimal value…

Let $k\geq3$, and let $G$ be a $C_k$-free graph with $m$ edges. Write $\operatorname{Max-Cut}(G)$ for the maximum number of edges in a bipartite subgraph of $G$. Alon's conjecture.…

Exact maximum-cut conjecture. The maximum cut equals the upper bound:

Let $G$ be a random $r$-regular graph with $N$ vertices, edge set $E$, maximum cut size $|MC|$, and minimum bisection size (bisection width) $|BW|$. Here $|E|$ is the total number…