8 problems

Alon–Bollobás–Krivelevich–Sudakov conjecture. For some $\varepsilon_H>0$, every $H$-free graph $G$ with $m$ edges satisfies

Let $n$ binary spins be arranged on a ring, with the objective of maximizing the number of neighboring pairs pointing in opposite directions. For even $n$, let $r_p^*$ denote the l…

Let $G$ be a nearly linear $k$-uniform hypergraph with $m$ edges, meaning that each pair of vertices lies in at most $O(\log m)$ edges, and let $2\leq r\leq k$. An $r$-cut is a par…

Let $G$ be a $k$-uniform hypergraph with $m$ edges, where $2\leq r\leq k$, and let an $r$-cut be a partition of the vertex set into $r$ parts whose size is the number of hyperedges…

Let $H$ be a fixed graph, and let $uH(G)$ denote the maximum cut size of an $H$-free graph $G$ with $m$ edges. Alon–Krivelevich–Sudakov conjecture. There exists an appropriate…

Random-regular-graph MaxCut conjecture. For some $\delta>0$, with high probability there is a degree-$n^\delta$ pseudoexpectation operator $\widetilde{\mathop{\varmathbb{E}}}$ on B…

Approximation-ratio conjecture. This lower bound cannot be improved beyond $0.768$; that is,

Let $G\sim G(n,(1+\varepsilon)/n)$ for a fixed $\varepsilon>0$, and let $\mathrm{Dist}_{\mathrm{BP}}(G)=|E(G)|-\mathrm{MAXCUT}(G)$ denote the distance of $G$ from bipartiteness. Co…