← All problems

Split-rank conjecture of Basu, Conforti, Di Summa, and Jiang

Let P={x∈Rd:Ax≤b}P=\{x\in\mathbb{R}^d:Ax\le b\} be a bounded rational polytope, let L(P)L(P) denote its binary encoding length, and let PI=conv⁡(P∩Zd)P_I=\operatorname{conv}(P\cap\mathbb{Z}^d). For a∈Zda\in\mathbb{Z}^d and β∈Z\beta\in\mathbb{Z}, define the split disjunction aTx≤βa^{\mathsf T}x\le\beta or aTx≥β+1a^{\mathsf T}x\ge\beta+1. If SC⁡(Q)\operatorname{SC}(Q) is the intersection, over all such disjunctions, of the convex hulls obtained by imposing the disjunction on QQ, and SC⁡r\operatorname{SC}^{r} denotes rr iterations of this operation, then there should be a polynomial bound on the split rank: there exists a polynomial pp such that min⁡{r:SC⁡r(P)=PI}≤p(L(P))\min\{r:\operatorname{SC}^{r}(P)=P_I\}\le p(L(P)) for every bounded rational pure-integer polytope PP, with the bound applying in unrestricted dimension.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A November 2026 unrefereed preprint proves the conjecture for bounded integer polytopes in each fixed dimension, but the full conjecture remains open.

The conjecture concerns bounds on split rank in integer optimization. A new preprint establishes the predicted behavior for bounded pure-integer polytopes when the dimension is fixed, rather than settling the unrestricted conjecture.

November 2026 fixed-dimensional result

Avinash Bhardwaj and Vishnu Narayanan claim polynomial split rank and a polynomial-time constructible split proof for bounded pure-integer polytopes in every fixed dimension, with related results for split closures and mixed-integer systems. This is substantial progress, but it covers only a fixed-dimensional class and is reported in an unrefereed preprint.

Current status (as of November 2026): The conjecture is claimed for bounded pure-integer polytopes in fixed dimension, while the general conjecture remains open and the new result is unverified.

Sources

Solutions 0

No solutions have been posted yet.