12 problems

Let $G$ be a random regular graph, and let the max-cut be a partition of its vertex set maximizing the number of crossing edges. Let the bisection width be the minimum number of cr…

Räty–Sudakov–Tomon conjecture. For any $\epsilon>0$, there exists a $c>0$ such that, if $G$ is $\epsilon$-far from every disjoint union of cliques, then

Let $\textbf{LB}_{\kappa}(\theta)$ and $\textbf{LB}'_{\kappa}(\theta)$ be the stated inner-minimization problems, with variables $\mathbf r$, $\mathbf s$, $r_1$, $r_6$, $s$, $t$,…

Far-from-Turán discrepancy conjecture. For every $\varepsilon>0$, there exists $c>0$ such that, if $G$ is an $n$-vertex graph that is $\varepsilon$-far from every Turán graph, incl…

Verstraete's conjecture.

Let $G$ be a graph with $m$ edges, and let $\mathrm{sp}(G)=\mathrm{mc}(G)-m/2$ denote its surplus, where $\mathrm{mc}(G)$ is the number of edges in a largest bipartite subgraph of…

Let $G$ be a graph with $m$ edges, and let $\mathrm{sp}(G)=\mathrm{mc}(G)-m/2$ denote its surplus, where $\mathrm{mc}(G)$ is the number of edges in a largest bipartite subgraph of…

Let $G$ be a graph with $m$ edges, and let $\mathrm{sp}(G)=\mathrm{mc}(G)-m/2$ denote its surplus, where $\mathrm{mc}(G)$ is the number of edges in a largest bipartite subgraph of…

Let $G_1$ and $G_2$ be two graphs with vertex sets … Let $(X_1,S_1)$ and $(X_2,S_2)$ be the primal-dual solution pairs to the max-cut SDPs on $G_1$ and $G_2$, respectively. Let $G$…

Carlson et al.'s conjecture. Every $K_r$-free $d$-degenerate graph with $m$ edges has surplus

Alon–Bollobás–Krivelevich–Sudakov conjecture. There exist constants $\varepsilon=\varepsilon(H)>0$ and $c=c(H)>0$ such that, for all $H$-free graphs $G$,

Let $G_{n,p}$ be the binomial random graph. An ordinary max cut is a partition of the vertex set into two parts attaining the maximum possible number of crossing edges. Max-cut loc…