32 problems

Consider the random K-LSAT linear program with $n$ variables and $m$ constraints, with all auxiliary variables $\psi$ set to zero. Let $N(n,m)$ be the maximum cardinality of a feas…

Let $c^*_K$ be the constant introduced in the source's theorem for the optimal value ${\cal LP}(n,c)$ of the random K-LSAT linear program, and consider the corresponding feasibilit…

Let $\alpha$ be the middle real root of … For odd $n=2m+1$, let $L_m^{\mathrm{fat}}$ and $L_m^{\mathrm{thin}}$ denote the relaxation optima on the fat and thin colour classes, resp…

LP optimum conjecture for $D_n$. If $n$ and $d$ are odd integers with $1\leq d\leq n$, then

Integrality conjecture. If the optimal value of $\operatorname{Lp}(G,G_1,Z,P,Y_a)$ is $|Z|+|P|$, then there is an integer solution.

For a graph $G$, let $\mathcal{C}\mathcal{C}_t(G)$ and $\mathcal{C}\mathcal{C}^*_t(G)$ denote its integral and fractional $t$-clique cover numbers, respectively. Additive-gap conje…

Let $T$ be a tree, and consider the linear program obtained from the MacGillivray–Wang integer program for virus spread by relaxing $x(v)\in\{0,1\}$ to a linear constraint and addi…

Recovery-threshold conjecture. If $\Delta > 2.14$, then Problem recovers the planted clusters with high probability.

Let $\boldsymbol v=(v_1,\ldots,v_{n-1})$ be a vector of increasing positive integers, and let $\operatorname{gap}(\boldsymbol v)$ and $\lambda_+(\boldsymbol v)$ be the quantities d…

Strong Fractional Tuza's conjecture. For every $k\in\mathbb{N}$ with $k\geq 2$ and every graph $G$, …

Siegel's Conjecture. If $H$ satisfies the Hirsch Conjecture and $C$ is a cube, then $H\cap C$ satisfies the Hirsch Conjecture.

Let $q\geq 3$, let $n$ and $\ell$ be fixed, and let $T_n$ denote the discrete set of admissible points used in the relaxed linear programs over $[\ell,s]\cap T_n$ and…

Consider the metric traveling salesperson problem and its subtour linear programming relaxation. A feasible solution is half-integral if every edge variable satisfies…

Let $G_p$ be the Paley graph for a prime $p\equiv 1~(\operatorname{mod}4)$, let $\operatorname{LS}(p)$ denote the linear programming bound obtained in the paper, and let…

Let $amma$ be a cubic graph. Let $Mathcal{P}b$ be the feasible region defined by constraints … , and let $Mathcal{P}c$ be the feasible region defined by the degree, subtour, symm…

De Klerk–Dobre conjecture. For every circulant TSP instance,

Consider the two-curve Chebyshev approximation problem and its corresponding linear programming formulation. The de la Vallée-Poussin procedure is an iterative procedure for findin…

Let $P$ be a $d$-dimensional polytope with $n$ facets, and let ${\bf c}$ be a generic linear functional. Orient the graph of $P$ according to increasing values of ${\bf c}$, and de…

Let $P$ be a simple polytope and let ${\bf c}$ be a generic cost vector such that $G(P, {\bf c})$ is the Hasse diagram of a lattice. A directed path in $G(P,{\bf c})$ is said to re…

Let $G$ be a $d$-regular graph, let $q\ge d+1$, let $\beta>0$, and let $U^q_G(\beta)$ denote the objective associated with the Potts-model linear-programming relaxation. Davies–Jen…

Large-scale performance conjecture. There exists a size level of huge problems above which LinSup will perform better than linear minimization algorithms.

Partition-LP tightness conjecture. The minimization LP is tight and yields, for every $d$-regular graph $G$,

Let $f$ and $\widehat{f}$ be optimal radial functions for the Euclidean linear programming sphere-packing bound, normalized so that … Their quadratic Taylor coefficients are the co…

Let $n\in\{2,8,24\}$, and let $f$ satisfy the hypotheses of the Cohn–Elkies linear-programming bound. Write $r$ for the radius parameter in that bound. Cohn–Elkies sphere-packing c…

Circuit diameter bound. For any $n$-dimensional polyhedron with $f$ facets, the circuit diameter is bounded above by