CS Paper Radar

An upper bound on the number of edges of a Gomory corner polyhedron

A. Yu. Chirkov, S. I. Veselov, D. V. Gribanov, D. S. Malyshev, N. Yu. Zolotykh

cs.CG math.COcs.DMmath.OC ·submitted 2026-11-12 14:17 UTC · v1
theory

Abstract

We establish the first nontrivial upper bound on the number of edges of a Gomory corner polyhedron, resolving a long-standing open question. For an $n$-dimensional corner polyhedron associated with an integer lattice of determinant $δ$, the number of edges is at most $$ O\left(n6^n \cdot \bigl(1+\log_2(2δ)\bigr)^{2n-3}\right). $$ This improves the standard bound obtained by counting pairs of vertices, reducing the logarithmic exponent from $(2n-2)$ to $(2n-3)$.

Closest papers

Nearest neighbours by meaning across the whole index.

An Improved Upper Bound for the Turán Number of the Hexagon

cs.DM math.CO ·2026-09-09 ·Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
theory similarity 0.60
Abstract · 9 pages

For a graph $F$, the Turán number $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Turán numbers of even cycles is a central problem in extremal graph theory and remains open in general. For $C_6$, the best previous upper bound was due to Füredi, Naor, and Verstraëte [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq λn^{4/3}+O(n)<0.6272 n^{4/3}, $$ where $λ$ is the real root of $ 16λ^3-4λ^2+λ-3=0$. We improve this bound by showing that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq αn^{4/3}+O(n)<0.6144 n^{4/3}, $$ where $α$ is the unique real root of $ 4 α^{3} (3/2)^{1-1/(2α)} =1$ in the interval $(1/2,2/3)$.

0.27

Log-concavity and Approximate Counting for Totally Unimodular Polytopes

cs.DM math.CO ·2026-09-30 ·Jonathan Leake, Maryam Mohammadi Yekta
theory similarity 0.59
Abstract

We present a new lower bound on the number of lattice points of all totally unimodular polytopes, generalizing previous lower bounds on contingency tables, integer flows, and beyond. Our bound is based on the Gurvits capacity convex optimization problem, and thus our result implies an efficient deterministic algorithm for approximate counting of the lattice points up to an explicit exponential factor. We achieve our bounds by showing that the associated generating polynomials fit into a new general class of log-concave polynomials called VLC ("variable-wise log-concavity''). This also implies a conjecture of Ferroni and Higashitani on the evaluations of the Ehrhart polynomials of unimodular polytopes. The essential ingredient for these results is the resolution of Barvinok's log-concavity conjecture for contingency tables on lines, which was proven using ChatGPT 6 Astra. We conjecture a generalization of Barvinok's conjecture, which we believe will lead to stronger and more general bounds.

0.21

Determinant boundaries and gaps in determinantal complexity

cs.CC ·2026-11-02 ·Karthik Sheshadri
theory similarity 0.58
Abstract · 75 pages, in submission to FoCM

Landsberg, Manivel, and Ressayre constructed determinant-boundary components whose defining forms, for odd n >= 3, are limits of n x n determinants but cannot themselves be represented by determinants of that size. Their border determinantal complexity (DC) is therefore smaller than their exact DC. We prove that the difference can grow linearly with n. For every n >= 10, we construct an explicit homogeneous form of degree n, concise in n^2 variables, whose orbit closure is a boundary component, whose border DC is n, and whose exact DC is at least 2n - 1. Thus n rows suffice when limits are allowed, whereas every exact representation requires at least 2n - 1 rows. The same bound holds for the unpadded odd-skew forms at every odd n >= 3. We also prove that every concise degree-n boundary form in n^2 variables has exact DC at least n + 2. We construct three families of pairwise distinct boundary components. Together with the traceless determinant, they give at least floor((n-1)/2) + floor(n/3) components for every n >= 3, with an additional term counted explicitly in the paper. The main lower bound follows from a general degree lemma. If an affine matrix represents an irreducible homogeneous polynomial f of degree d and has globally free rank-one cokernel over the coordinate ring of f = 0, its size is at least 2d - 1. The adjugate factors into two nonzero kernel vectors, each requiring a coordinate of degree at least d - 1. Comparing their product with the degree of a cofactor proves the bound. The lemma is sharp for individual representations, as witnessed by algebraic branching programs. Whether the exact-versus-border gap can grow superlinearly remains open.

0.32

A New Upper Bound for the Turán Density of the Tetrahedron

cs.DM math.COmath.OC ·2026-09-23 ·Gyeongwon Jeong, Seonghun Park, Seonghyuk Im, Joonkyung Lee, Hongseok Yang
theorycode/data similarity 0.58
Abstract · 28 pages, 5 figures, 8 tables. v2: Slightly improved upper bound and updated exact certificate following continuation of the search to conve…

We prove that the Turán density of the tetrahedron $K_4^{(3)}$ satisfies $π(K_4^{(3)}) \le 14993367693127837/26880000000000000 < 0.557789$, improving Baber's upper bound of $0.5615$ and closing about $62\%$ of the gap to the conjectured value $5/9$. The proof uses an exact seven-vertex flag-algebra certificate incorporating degree-stationarity from Razborov's differential method. To find the certificate, we combine the established techniques of cutting planes and column generation to optimize jointly over flag families whose types have at most five vertices. We give a complete formal proof of this Turán density bound in Lean 4.

0.63

New bounds on the boxicity of Kneser graphs

cs.DM math.CO ·2026-11-12 ·L. Sunil Chandran, Suraj Kumar Sahoo
theory similarity 0.57
Abstract

For a graph $G=(V,E)$, the boxicity $\operatorname{box}(G)$ is the least integer $d$ such that $G$ is the intersection graph of axis-parallel boxes in $\mathbb{R}^d$. The Kneser graph $K(n,k)$ is the graph whose vertex set corresponds to the family of $k$ sized subsets of an $n$ sized ground set, and a pair of vertices are adjacent if and only if the corresponding sets are disjoint. In this short paper, we provide new bounds for the boxicity of $K(n,k)$. We first show that for $k\ge 2$ and $n\ge 2k+1$, $\operatorname{box}(K(n,k))\ge n-2k$, thereby improving the lower bounds of Caoduro and Lichev [Discrete Mathematics 346(5):113333 (2023)] when $n\geq 3k+1$ and $k\ge 3$. The proof of this result uses the topological method and follows a strategy similar to Greene's proof of the Kneser's conjecture on the chromatic number of $K(n,k)$. We also show that for $k\ge 2$, $t\ge 1$ and $n=2k+t$, $\operatorname{box}(K(2k+t,k)) \leq O( t^3\log(2k+t) ).$ In particular, for every $t=t(k)\ge1$ with $t^3\log k=o(k)$, $\operatorname{box}(K(2k+t,k))=o(k)$. This is the first upper bound on the boxicity of $K(n,k)$ that is sublinear in $n$. We also show that for large enough $k$, $\operatorname{box}(K(2k+1,k))\le \frac{3\ln (2k+1)}{\ln\ln (2k+1)}$.

0.28

Non-simple Arrangements of Lines and Pseudolines with Many Triangles

cs.CG math.CO ·2026-11-02 ·Roman Parpalak, Denis Utkin
code/data similarity 0.57
Abstract · 72 pages, 19 figures, 8 tables. Code, enumeration outputs and certificates: https://github.com/parpalak/nonsimple-arrangements

We study affine arrangements of an even number $n$ of lines and pseudolines with many triangles. For simple ones, Blanc's bound limits the number of triangular faces to $\lfloor n(n-5/2)/3\rfloor$. Adapting the Bartholdi-Blanc-Loisel doubling to the even case, we construct an infinite series of arrangements of $n=6\cdot2^t+2$ ($8,14,26,50,\ldots$) straight lines with two triple points and $(n(n-5/2)+1)/3$ triangles, one more than the simple bound allows. We obtain exhaustive enumerations of triangle-maximal pseudoline arrangements, simple or not, for even $n\le12$. For $n=6,8,10,12,14$ the maximum number of triangles, for both lines and pseudolines, is $7,15,25,38,54$; for $n=8,12,14$ every optimal arrangement has multiple points. All optimal arrangements for even $n\le12$ are realizable by straight lines, except two arrangements of 10 pseudolines, which are not stretchable. For the odd value $n=11$, no arrangement with $33$ triangles exists even with multiple points. We also obtain even arrangements by adding a line to odd ones. For $n\equiv2\pmod 6$ this again gives one triangle more than the simple bound, in pseudolines up to $n=44$ and in straight lines for $n=20$ and $n=32$. Doubling these pseudoline arrangements gives members of the series $18\cdot2^t+2$ and $30\cdot2^t+2$ with the same excess, up to $n=146$ and $n=242$, respectively; those with $n=38$ and $n=74$ are realizable by straight lines. These results lead us to conjecture that an arrangement of an even number $n$ of pseudolines has at most $\lfloor n(n-2)/3\rfloor-\lfloor n/6\rfloor$ triangles.

0.34

Optimal Configurations for Mordell's Problem

cs.SC math.COmath.OC ·2026-11-02 ·Xiang Ji, Tiancheng Xu, Wensheng Yu
theoryunusual similarity 0.56
Abstract

Mordell's problem asks for the largest product of squared pairwise distances among $n$ points in the complex plane with a prescribed sum of squared distances from the origin. When this sum equals $n$, the maximum for $2\le n\le5$ is known to be $n^n$, attained precisely by the $n$th roots of unity up to rotation and relabeling. For $n\ge6$, Chalk showed that a regular polygon together with its center gives a larger product than the regular $n$-gon. We prove that for $6\le n\le9$ the maximum is $(n-1)^{n-1}r_n^{n(n-1)}$, where $r_n=\sqrt{n/(n-1)}$. Up to the same symmetries, the unique maximizer consists of the origin and the vertices of a regular $(n-1)$-gon of radius $r_n$. For six points, algebraic elimination reduces the proof to an exact comparison of stationary values. For seven points, we compare all twelve classes in a published classification of equilibria. For eight and nine points, rigorous interval arithmetic establishes an inequality for every admissible pair. Summing over pairs gives the sharp global bound, and the equality conditions determine the configuration. An explicit ten-point comparison and a known instability result together exclude Chalk's configuration for every $n\ge10$. For each $n$ from two through eight, Mordell's problem and the minimum-diameter problem studied by Bateman and Erdős have a common optimal configuration.

0.29

Equilibrium Numbers in Non-Square Bimatrix Games

cs.GT math.CO ·2026-09-21 ·Constantin Ickstadt, Thorsten Theobald, Bernhard von Stengel
theory similarity 0.56
Abstract · 32 pages

Bimatrix games may have an exponential number of mixed Nash equilibria if both dimensions of the game are allowed to grow. Bounds on their maximal number give structural insights that have been used to construct hard-to-solve games. We show new sharp or asymptotically sharp bounds on the (polynomial) number of equilibria for generic games where one dimension of the game is fixed and the number of strategies of the other player grows. These results go beyond the hitherto studied square games. Our methods employ combinatorial properties of polytopes, and recent obstructions that relate to the graph of those polytopes. For $n\ge5$, we construct $3\times n$ games that have all $2n+1$ vertices of the best-response polytope as equilibrium strategies, proved using a simple case of the 4-color theorem for planar graphs. Generic $4\times 5$ games are shown to have at most 17 equilibria, using computer calculations with existing datasets for all combinatorial types of the relevant polytopes. For $d\times n$ games, we construct games where all but a fraction of $O(1/n)$ of the maximum number of vertices are equilibrium strategies.

0.29