25 problems

Karloff's eigenvalue-range conjecture. The condition $0\leq b\leq m/12$ in the theorem on the smallest eigenvalue of $J(m,m/2,b)$ could be relaxed to

Let $G$ be a triangle-free graph on $N$ vertices. Erdős's conjecture. The graph $G$ can be made bipartite by deleting at most … edges; equivalently, $G$ has a cut containing at lea…

Consider the complete graph $K_n$ with vertices ordered $1,\ldots,n$, whose edges are ordered lexicographically and whose $i$-th edge has weight $r^{N-i}$, where $N=\binom{n}{2}$ a…

Mixed-weight benchmarking conjecture. Mixed-weight graphs form an important class for benchmarking.

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…

Let $G$ be a $K_r$-free graph with $m$ edges, where $K_r$ denotes the complete graph on $r$ vertices, and let its surplus be … where $\operatorname{mc}(G)$ is the size of a maximum…

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$,…

Let $G$ be a triangle-free sub-cubic graph, let $m_G$ denote its number of edges, and let … be its bipartite density. Let $\mathbf{Bad}$ be the seven exceptional 2-connected triang…

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…

Dense regular graph discrepancy conjecture.

Verstraete's conjecture.

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$…

Delorme–Poljak conjecture. The $5$-cycle has the worst ratio:

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

Weaker forms of the Max-Cut Conjecture. The problem

A $2$-regular graph is a graph in which every vertex has degree $2$, and standard QAOA at depth $p$ is evaluated by its expected approximation ratio for the Max-Cut objective. QAOA…

Let $\mathbb G$ be a random regular graph. The one-step replica-symmetry breaking equations provide a variational solution for the maximum cut problem on $\mathbb G$. Zdeborová–Boe…

Optimal-coloring strong-equilibrium conjecture. Every optimal coloring is an SE.

Erdős's bipartisation conjecture. Every $n$-vertex triangle-free graph can be made bipartite by deleting at most $n^2/25$ edges.

Optimal Max-Cut conjecture. There exists a constant $c=c(H)>0$ such that, for all $H$-free $d$-degenerate graphs $G$ with $m\geq 1$ edges,

Montanari's local-algorithm conjecture. Local algorithms find asymptotically optimal configurations for Max-cut on random regular graphs. Consequently, this would imply

Let ${\Rg \gamma}$ denote the Erdős–Rényi random graph with $n$ vertices and $[\gamma n]$ edges, and let ${\sf MCUT}(G)$, ${\sf MaxCut}(G)$, and ${\sf mcut}(G)$ denote respectively…

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…

Let $G$ be a triangle-free graph on $n$ vertices. An odd cycle transversal is a set of edges whose removal makes $G$ bipartite. Erdős's conjecture. Every such graph has an odd cycl…