Papers for

combinatorial optimization teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Minimum imbalance of Latin rectangles improves with new search methods

How Unbalanced Must a Latin Rectangle Be?

Abstract: We view a $k\times n$ Latin rectangle as $n$ points in the grid $[n]^k$. Each symbol gives one point, whose coordinates are the columns it occupies. The rectangle is balanced when these points are pairwise equidistant in the $\ell_1$ metric. Its imbalance measures the distance from this ideal. We study the minimum imbalance from three sides. Constructively, we use a simulated annealing that moves symbols within rows and only penalises column clashes. Against the reference table of Voboril et al. (2025), it improves 33 of the 51 non-square values for $8\le n\le 13$, by up to 39.4%, and matches the rest. A cheap invariant, the row group, certifies that none of the 33 new rectangles is isotopic to rows of a group table, so the earlier column-swapping local search cannot reach any of them. Exactly, a computer-assisted branch and bound proves that the minimum imbalance of a $3\times 9$ rectangle is $56$. Díaz et al. found this value, but its optimality was open. A sharper pruning bound, derived from the identity $I=2\sum(d-t)^+$, reduces the search tree by a factor of $2.4$ to $3.3$ on the instances with $k\ge3$ that we solve. Asymptotically, the minimum imbalance is $Θ(n^3)$ for every fixed $k$. A pigeonhole argument gives a lower constant of order $k\,4^{-k}$, and random rectangles give an upper constant of order $\sqrt k$. For $k=2$, the limit of $\min I/n^3$ exists, a permuton attains it, and it lies between $4/375$ and $0.1196$. Perfect balance is an $\ell_1$-equilateral problem, so it forces $k=Ω(n/\log n)$ rows. For $2\times n$ rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for $14\le n\le 20$. Finally, the Lean 4 kernel checks every rectangle reported in this paper against a 74-line specification that imports only Lean's core library. We also prove the pigeonhole lower bound in Lean with Mathlib.

Wed 4 NovDiscrete MathematicsArtificial Intelligence
The gist
A Latin rectangle is an arrangement of numbers where each symbol appears once per row and column, and its balance can be measured by how evenly spaced its symbols are. The authors studied how unbalanced these rectangles must be and improved existing examples using smart search techniques, confirming some previously unknown minimum imbalance values. They also proved theoretical limits on imbalance and perfect balance conditions, while verifying all results with formal computer checks. Their work refines both practical construction and theoretical understanding of these mathematical objects.
Open → 2611.06003v1

Graph pfaffian number bounded by symbolic pfaffian number with new linear algebra proof

The symbolic pfaffian method I: A generalization of the Gallucio-Loebl-Tesler Theorem

Abstract: The pfaffian number of a graph $G$, denoted by $\mathrm{pf}(G)$, is the minimum integer $k$ such that the generating function of perfect matchings of $G$ can be written as a linear combination of $k$ pfaffians of signed adjacency matrices. The Galluccio-Loebl-Tesler Theorem states that $\mathrm{pf}(G) \leq 4^g$, where $g$ is the orientable genus of $G$. We generalize this theorem by relating the pfaffian number of a graph to another graph parameter: the symbolic pfaffian number, denoted by $\mathrm{spf}(G)$. Namely, we prove that $\mathrm{pf}(G) \leq 2^{\mathrm{spf}(G)}$. Our proof is based on linear algebra arguments and does not depend on topological properties of graphs. As a consequence of our generalization, we conclude that $\mathrm{pf}(K_{2n}) = 2^{\mathcal{O}(n \log n)}$, an improvement on the previous upper bound of $4^{\mathcal{O}(n^2)}$ based on the genus. We also consider lower bounds for $\mathrm{pf}(G)$ related to $\mathrm{spf}(G)$. In particular, we show that the graphs with $\mathrm{pf}(G) = 4$ are the graphs with $\mathrm{spf}(G) = 2$. On the other hand, we show that our main result is strictly more general than a previous generalization by Norine.

Fri 30 OctDiscrete Mathematics
The gist
Graphs can be analyzed by looking at their perfect matchings, which are ways to pair up all the points without overlap. The pfaffian number measures how complicated it is to describe these matchings using a special mathematical tool called pfaffians. The authors found a new way to link this number to another measure, called the symbolic pfaffian number, with a proof that uses only linear algebra and no complex geometry. This approach improves our understanding and gives better upper bounds on this measurement for certain graphs, including complete graphs. They also clarified cases where small pfaffian numbers occur and showed their result is more general than previous work.
Open → 2611.00468v1

Maximum distinct character values in finite projective systems

Extremal character spectra of finite projective systems

Abstract: Let $\mathcal M$ be a finite spanning multiset of points in ${\rm PG}(k-1,q)$, and let ${\rm Char}_{\mathcal M}$ be its character function. For $1\le r\le k$, we study the maximum number of distinct values attained by ${\rm Char}_{\mathcal M}$ on the codimension-$r$ flats under a total-multiplicity budget. The spectrum is subject to two natural upper bounds, whose extremal cases lead respectively to $r$-maximum character spectrum ($r$-MCS) and $r$-full character spectrum ($r$-FCS) systems. We establish the existence of $r$-FCS systems in a broad parameter range, and solve the size-constrained extremal problem completely when $r=k-1$, including the minimum-cost multiplicity profiles. For $1\le r<k$, put $M_r=\qbinom{k}{r}$ and $B_r=\qbinom{k-1}{r}$. The minimum size $ν_r(k,q)$ of an $r$-MCS system satisfies \[\left\lceil\frac{\binom{M_r}{2}}{B_r}\right\rceil\le ν_r(k,q)\le \binom{M_r-1}{2}+\frac{q^k-q^{k-r}}{q-1}.\] The upper bound is at most $\binom{M_r}{2}$, strictly less when $r\le k-2$, and exact when $r=k-1$. Its proof applies positive additive labelings to the complement of one flat, whose trace is empty while all remaining traces are distinct. For $r=1$, we improve the known upper bounds on the minimum length of such systems. We also develop global moment identities and local flat-incidence bounds that impose strong structural constraints on large character spectra. Under the projective-system correspondence, complementary character spectra are the support-weight spectra of $r$-dimensional subcodes.

Fri 30 OctInformation Theory
The gist
This paper studies how to maximize the variety of values a certain function takes when applied to collections of points in a finite projective space, which is a mathematical setting used in coding theory and combinatorics. The authors find the largest number of distinct values possible under certain size and multiplicity constraints, and fully solve the problem in a key special case. They also provide new mathematical inequalities that describe the structure of these value patterns. These findings relate to the properties of specific error-correcting codes called subcodes.
Open → 2610.42006v1

Semi magic squares and moment conditions reveal new permutation thresholds

Moments of Magic Squares: Line-Sum Conditions, a Permutation Threshold, and Random Energies

Abstract: Every semi-magic square of order $n$ satisfies the axial moment identities $\sum_{i,j}s_{ij}j^m=\sum_{i,j}s_{ij}i^m=M(n)\sum_jj^m$ for all $m\ge1$, where $M(n)=n(n^2+1)/2$. For real matrices the converse requires $1\le m\le n-1$, whereas for arrangements of $\{1,\dots,n^2\}$ fewer moments suffice once $n\ge14$. We define the permutation threshold $k^*(n)$ as the least $k$ such that every arrangement satisfying these identities for $1\le m\le k$ is semi-magic. In terms of the column-sum deviations $γ_j$, the degree-$k$ conditions state that $\sum_jγ_jt^j$ is divisible by $(t-1)^{k+1}$, linking $k^*(n)$ to the Prouhet--Tarry--Escott problem. While Schur's bound on real zeros gives $k^*(n)\le\sqrt{2(n-1)\log(n^4/4)}$, we prove the converse realisability bound $k^*(n)\ge(\sqrt2-o(1))\sqrt n$ (and $k^*(n)\ge(\sqrt6-o(1))\sqrt n$ when $4\mid n$) by perturbing semi-magic squares with complementary row pairs via horizontal swaps. We also show that $k^*(n)=n-1$ for $3\le n\le13$, $k^*(n)=n-2$ for $14\le n\le17$, and $k^*(n)\le n-3$ for $n\ge18$, and determine $k^*(n)$ for $18\le n\le40$ with computer assistance. Finally, at the $k=1$ level of the hierarchy, we specialise the Mantel--Hubert quadratic assignment variance formula to obtain exact means, variances, and limit laws under a uniform random arrangement for the full line-sum energy $E_{\mathrm{full}}$, for the four-term energy $E_4$ combining the first moments and the two diagonals, and for Loly's moment of inertia, and find that $|L_4|=14{,}639{,}440$ arrangements of order $4$ satisfy $E_4=0$.

Wed 28 OctDiscrete Mathematics
The gist
Magic squares are grids of numbers where the sums of rows, columns, and diagonals are equal. The authors studied patterns in these squares using moments, which are like weighted sums. They found the minimum number of moment conditions needed to guarantee a grid is semi-magic, a threshold linked to classical number theory problems. They also analyzed the behavior of random arrangements mathematically and used computers to understand these thresholds for squares up to size 40.
Open → 2610.38386v1

Sparse SOS layers speed up certified learning with less memory use

Sparse Sum-of-Squares Layers for Certified Learning

Abstract: A central limitation of modern machine learning systems is the lack of formal certificates guaranteeing their behavior beyond empirical, sample-based evaluation. Sum-of-squares (SOS) methods provide such guarantees by certifying polynomial inequalities over continuous domains via semidefinite programming (SDP). While prior work has introduced SDP layers as differentiable components in neural networks, repeated learning calls can lose the computational benefit of the forward program's sparse representation. We propose Sparse SOS Layers, differentiable value layers whose backward passes reuse the local coordinates of the forward solve. Under a fixed template and learned objective coefficients, each layer avoids building dense certificates and reuses its sparse structure across training steps. Compared with existing methods, our approach achieves up to 2.7 times speedup in total warm-call time, with nearly 100 times lower memory usage (1.7 vs. 160 GiB) for relatively large problem sizes for the tested dense parameterization. Experiments cover sparse polynomial certification, pendulum control, combinatorial relaxations, robotics projection, oscillator chains, and pose graph synchronization. A design study achieves zero certified violations across unseen problem instances and sizes, while requiring roughly 7 times fewer optimization solves than estimating gradients by perturbing the objective coefficients and re-solving the problem (finite differences). These results show that sparse certificate values can be effectively integrated into learning pipelines when the backward pass respects the verifier's structure.

Sun 25 OctMachine Learning
The gist
Many machine learning systems can make mistakes that are hard to catch. The authors focus on a technique called sum-of-squares (SOS) that can provide mathematical guarantees about a system’s behavior. They improve this by creating sparse SOS layers that reuse information efficiently during training, making the process faster and using much less memory. Their method works well for a variety of control, robotics, and optimization tasks and requires fewer computations to certify results.
Open → 2610.34590v1

New method solves large combinatorial programs with less memory

Solving Large SDPs from Flag Algebra Problems

Abstract: The flag algebra method is a general tool in extremal combinatorics, which has been useful in tackling open problems concerning graphs, hypergraphs, permutations, point sets, and other structures. The method establishes combinatorial inequalities via sums of squares, which are usually obtained by a semidefinite relaxation of the original combinatorial problem. A typical application of the method in graph theory starts with fixing a parameter $n$ followed by constructing a semidefinite program based on the (subgraph) structure of all $n$-vertex graphs. In the standard formulation before symmetry reductions, there is a coefficient constraint for every admissible $n$-vertex graph up to isomorphism. For 3-uniform hypergraphs, there are 2,136 of them on 6 vertices and 7,013,320 on 7 vertices. While solving the resulting program for $n=6$ is an easy task on any modern computer, the programs for $n = 7$ seems out of reach, mainly because the SDP solvers need too much RAM. Yet solving such programs for as large $n$ as possible is desirable because they typically yield better bounds for the original combinatorial problems. We bypass the aforementioned memory requirements by linear programming with cutting planes. Although we do not guarantee that this cutting-plane procedure reaches an optimum in finitely many iterations, in many flag algebra instances it uses much less memory and yields improved bounds for well-known hypergraph Turán problems. We use this method to obtain numerical bounds for Turán densities and codegree squared densities of several 3-uniform hypergraphs including the tetrahedron, where we obtained the upper bound 0.55753 and tetrahedron without one edge with a new upper bound 0.2865. It also allows to tackle bounds on Turán densities of 7-vertex 3-graphs using flag algebras, which was not possible before.

Sat 24 OctDiscrete Mathematics
The gist
Certain math problems involving large networks or groups of objects are hard to solve because they need too much computer memory. The authors found a way to solve bigger problems by using a step-by-step approach that requires less memory. This lets them get better answers for questions about complex structures like 3D networks and helps with problems previously out of reach. Their method improves bounds on specific patterns, like the tetrahedron shape, which was difficult to analyze before.
Open → 2610.33850v1

Simplified proof improves counting perfect matchings in graphs

A simplified proof of the FPRAS for counting perfect matchings

Abstract: We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.

Mon 19 OctData Structures and Algorithms
The gist
Counting perfect matchings in graphs is a complex problem with many practical applications. The authors provide a simpler proof of an existing algorithm that quickly estimates the number of perfect matchings. Their approach removes complicated steps from the original proof, making the reasoning more direct while keeping the same performance guarantees. This makes understanding and teaching the algorithm easier without sacrificing accuracy.
Open → 2610.26803v1

Forests have special log concavity property in independence sequences

Barrier Log-Concavity of Large Forests

Abstract: We prove that the independence sequence of every sufficiently large forest is strictly barrier log-concave: whenever $i_{k+1}>i_k$, one has $i_k^2>i_{k-1}i_{k+1}$. Consequently, every common downward coefficient tilt is unimodal, with one order threshold valid simultaneously for all $0<t\le1$. As an application, we prove that every sufficiently large well-covered tree has a strictly log-concave independence polynomial. More generally, the latter conclusion holds for well-covered forests with sufficiently large matching number. Every sufficiently large forest with a palindromic independence polynomial is also strictly log-concave, with its modes at the central ranks. The proof establishes local coefficient-curvature estimates uniformly over forests of unbounded maximum degree and over activities tending to zero. Combined with the fixed-density theorem of Fang, Lu, Nevo, Yao, and Zheng, these estimates complete the strict log-concavity interval down to rank one through $\lfloor17α/25\rfloor$; the terminal fraction is inherited. The classical decreasing tail then yields the barrier property. A cumulative-coefficient corona theorem transfers barrier log-concavity of the base forest to full strict log-concavity of its leaf corona.

Thu 15 OctDiscrete Mathematics
The gist
This paper shows that in large forests (collections of trees), the sequences counting independent sets behave in a special way called barrier log-concavity, which means certain numbers in the sequence relate tightly in a curved way. This helps prove that related polynomials, which encode this count, have a smooth shape called strict log-concavity, important for understanding the structure of these graphs. The authors also demonstrate that this property holds under many different conditions and for various large forests and well-covered trees. Their proof involves detailed estimates that work even when the trees have complex structures.
Open → 2610.22098v1

Constraints and constructions for special linear sets in finite geometry

Construction of Regular Fat Linear Sets and Non-Representable q-Matroids

Abstract: Let $q$ be a prime power. An $(r, i)$-regular fat $\mathbb F_q$-linear set has exactly $r$ points of weight $i\ge2$, called fat points. All of its remaining points have weight one, and at least one such point occurs. We solve two open problems posed by three of the authors of this paper. First, we derive divisibility constraints on the point weights using the scalar stabilizer of the defining subspace. Consequently, a regular fat linear set of rank $2i$ in $\operatorname {PG}(1,q^n)$ has at most two or exactly $q + 1$ fat points. In the latter case, the fat points form an $\mathbb F_q$-subline. Second, we construct higher-dimensional regular fat linear sets whose fat points do not form an $\mathbb F_q$-subgeometry. In particular, for every $k\geq 3$ we obtain examples of rank $2k$ whose fat locus consists of an $\mathbb F_q$-subgeometry $\operatorname {PG}(k-2,q)$ in $\operatorname {PG}(k-1,q^4)$ together with one external point. This construction is then generalized further. Finally, we apply our projective-line results to $q$-matroid representability and present an infinite family of non-representable rank-two $q$-matroids arising from partial spreads.

Mon 12 OctInformation Theory
The gist
This paper studies a special kind of geometric object defined over finite fields called regular fat linear sets, focusing on points with higher weights named fat points. The authors find new rules about how many fat points these sets can have and build examples that break some previous patterns. They also connect these geometric results to the theory of q-matroids, showing there exist certain q-matroids that cannot come from geometric constructions. These findings solve known open problems and provide new examples in the study of finite geometry and matroid theory.
Open → 2610.17055v1

Bipartite graph covers reveal new patterns in independent set counts

Coefficientwise Extremality and Rigidity for Independent Sets in Bipartite Graph Covers

Abstract: Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde G$ with those of the trivial cover, consisting of $M$ disjoint copies of $G$, after prescribing how many vertices are selected above each vertex of $G$. A conjecture from 2011, motivated by the Bethe approximation, asserts that the trivial cover maximizes every such count. We prove this for every feasible occupation profile whose active graph has treewidth at most two or is chordal bipartite. Equality holds exactly when the restricted cover is flat, meaning that fibre relabelings make it trivial. For $M\ge2$ and positive feasible occupations, a nonflat cover of a connected bipartite graph of treewidth at most two has a deficit of at least twice the coefficient of $p_G^{M-2}$ with every occupation reduced by one. A holonomy-dependent bound improves the factor to three for odd-order holonomy; both uniform constants are sharp. Comparison and rigidity survive finite compositions along an edge or a vertex, and quantitative bounds from one piece propagate to the whole graph, giving results beyond the two original classes. On any bipartite base, the first nonzero homogeneous defect is determined by the shortest cycles with nontrivial holonomy. At singleton occupations, our counts are numbers of DP-colorings of full covers. The dual DP color function on these classes and their finite seam compositions equals the chromatic polynomial, with equality attained precisely by canonical labelings. Dong's chromatic-polynomial inequality then yields the Dual-DP Shameful inequality on the same graph class. The main theorems have been formalized in Lean 4.

Sat 10 OctDiscrete Mathematics
The gist
This paper looks at ways to count different groups of disconnected points in complex graph structures built from simpler pieces. The authors prove that for certain kinds of graphs, the simplest way of stacking copies maximizes these counts, confirming a long-standing guess. They also identify precise conditions when these counts match or differ, revealing deeper structural patterns. Their work connects these counting problems to coloring puzzles on graphs and uses computer proof tools to ensure correctness.
Open → 2610.14892v1

Polyhedral methods clarify complexity of cooperative game problems

Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

Abstract: We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

Mon 21 SeptComputer Science and Game TheoryComputational Complexity
The gist
Cooperative games involve many players working together and require a huge amount of information, making computations very hard. The authors study special cases where the input size is smaller, called k-additive games, and find efficient ways to solve key problems in these cases. They also prove that for certain games, these problems remain very hard to solve, explaining why some game properties are difficult to understand. Their work builds bridges between geometry and game theory to better understand when cooperative game computations are feasible.
Open → 2609.24593v1

Efficient improved algorithms solve Beck Fiala problem for bounded sets

Improved Algorithms for Beck--Fiala with Bounded Sets

Abstract: We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\in\{0,1\}^{m\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\log^*$ denote the iterated logarithm and $\ell_j$ denote the $j$-fold composition of log. Assume $s\le\exp(O(\sqrt d))$. We provide an efficient algorithm that, for arbitrary sparsity $d$, gives $O(\sqrt d(1+\log^*n))$ discrepancy. Moreover, if $d\ge\ell_j(n)$ for a fixed integer $j\ge1$, the algorithm gives $O_j(\sqrt d)$ discrepancy. The proof is a bootstrapping scheme using the Bansal-Jiang algorithm.

Thu 17 SeptData Structures and AlgorithmsDiscrete Mathematics
The gist
The Beck–Fiala problem involves splitting items into two groups so that the groups stay well balanced across many overlapping sets, especially when each item belongs to only a few sets. The authors present a better, faster algorithm to find such a balanced partition when each set includes only a limited number of items. Their method improves how closely balanced the groups can be, depending on the size and overlap of sets. They build upon previous algorithms to achieve these improvements effectively.
Open → 2609.19714v1

Delta matroid polytopes always have dyadic volume triangulations

Regular dyadic triangulations of delta-matroid polytopes

Abstract: Backman and Liu proved that every integral generalized permutohedron of type $A$, and in particular every matroid base polytope, admits a regular unimodular triangulation. The analogous statement fails in type $B$: the delta-matroid simplex \[\operatorname*{conv}\{\mathbf{0},\ e_1+e_2,\ e_1+e_3,\ e_2+e_3\}\] has normalized volume $2$ and no lattice points other than its vertices, so it has no unimodular triangulation. We show moreover that, up to the natural symmetries of the $0/1$ cube and deletion of constant coordinates, it is the unique non-unimodular delta-matroid polytope that is a simplex. We prove instead that every delta-matroid polytope admits a regular dyadic triangulation, meaning a lattice triangulation whose maximal simplices have normalized volumes that are powers of two. More generally, every integral type $B$ generalized permutohedron admits such a triangulation. The main lattice-theoretic ingredient is that the type $B$ root configuration forms a totally dyadic system, a $2$-local analogue of total unimodularity. As a consequence, these polytopes satisfy a dyadic version of the integer decomposition property. In each dimension the corresponding exponent can be chosen uniformly, even though ordinary integer decomposition can fail for delta-matroid polytopes.

Wed 16 SeptDiscrete Mathematics
The gist
Some shapes, called polytopes, can be broken down into simpler pieces called simplices. For certain shapes related to math structures known as matroids, these pieces can all have the smallest possible volume. But for related shapes called delta-matroid polytopes, this isn’t always true. The authors found that while the simplest kind of these shapes may not break down so simply, all delta-matroid polytopes can be subdivided into pieces whose volumes are powers of two, giving a neat structured way to break them apart.
Open → 2609.18331v1

Archdeacon conjecture bounds nonplanar quadruples in rotation systems

Some results on Archdeacon's conjecture for rotation systems

Abstract: A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

Thu 10 SeptComputational Geometry
The gist
A rotation system arranges elements so their connections have a circular order. The paper studies how many groups of four elements must create some unavoidable 'crossings' in such systems, a problem linked to drawing complete graphs without overlaps. The authors confirm a longstanding conjecture for small sizes using computers and provide approximate bounds for larger sizes, partly by hand. They also prove the conjecture for a certain special class of these systems. This helps understand the limits of how 'tangled' such arrangements must be.
Open → 2609.11599v1