Discrete Mathematics
See recent articles
Showing new listings for Monday, 16 November 2026
- [1] arXiv:2611.17386 [pdf, html, other]
-
Title: TSP instances that require exponentially many subtour elimination constraintsSubjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)
We construct pathological TSP instances that require exponentially many subtour elimination constraints (SECs) in the sense that, if a smaller collection of SECs is imposed, then the Dantzig-Fulkerson-Johnson model returns a disconnected solution costing less than an optimal tour. For asymmetric instances on $n$ vertices, we prove a growth rate of \(\Omega(\phi^n)\), where \(\phi\approx 1.618\) is the golden ratio. A node-splitting reduction gives metric instances with \(\Omega(\phi^{n/2})\) growth. We also give instances in the plane under the Euclidean, Rectilinear, and Maximum metrics that require exponentially many SECs. Concorde struggles on them, with solve times growing exponentially despite tiny integrality gaps.
- [2] arXiv:2611.18391 [pdf, other]
-
Title: Color Refinement Distinguishes Connected Rooted Outerplanar GraphsSubjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
Color refinement, also known as the $1$-dimensional Weisfeiler-Leman algorithm ($1$-WL), is a classical near-linear-time heuristic for graph isomorphism, which also captures the expressive power of message-passing graph neural networks. A long line of work asks on which graph classes $1$-WL, or its higher-dimensional variant $k$-WL, identifies every graph; the least such $k$ is the WL-dimension of the class. Planar graphs have WL-dimension at most $3$ (Kiefer, Ponomarenko and Schweitzer, 2019), and whether $2$-WL already distinguishes all planar graphs is a central open problem. We bring new insight on this question for outerplanar graphs, whose WL-dimension is $2$. We show that color refinement, i.e. 1-WL, distinguishes connected rooted outerplanar graphs: two non-isomorphic such graphs receive different stable colorings once a single vertex, the root, is individualized. The root is necessary, as there are non-isomorphic $2$-connected outerplanar graphs that color refinement does not distinguish. Our result extends to pseudo-rooted graphs, in which the stable coloring merely contains a singleton color class, and to non-connected graphs whose components all contain such a class. Consequently, the $(1,1)$-WL test of Rattan and Seppelt (2023) distinguishes all outerplanar graphs. We proceed by inversion: we reconstruct a connected rooted outerplanar graph, up to isomorphism, from its color graph, the weighted quotient of the graph by its stable color classes, together with its root color. The reconstruction runs in time linear in the output size and is canonical, which yields a near-linear-time canonization algorithm for these graphs. Our main tool is a dichotomy lemma, formalized in Rocq: in a rooted outerplanar graph with an equitable coloring, every block either receives pairwise distinct colors or admits a color-preserving mirror symmetry fixing its vertex closest to the root.
New submissions (showing 2 of 2 entries)
- [3] arXiv:2610.40863 (cross-list from math.CO) [pdf, html, other]
-
Title: The Cranston--Li--Su--Wang--Xu (2026) conjecture is trueComments: 15 pages, 5 figures, 1 table. Lean 4 proof: this https URLSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
Let $A$ be a finite abelian group. A nowhere-zero $A$-flow of a graph can be changed along a cycle: going around the cycle, add a fixed non-zero element of $A$ to the value of every edge that points forward and subtract it from the value of every edge that points backward. The Cranston--Li--Su--Wang--Xu (2026) conjecture on the reconfiguration of nowhere-zero flows states that if $A$ has at least four elements, then in every graph in which all degrees are even, any two nowhere-zero $A$-flows are joined by a chain of such changes through nowhere-zero $A$-flows. It also states that, for every integer $k\ge 4$, the same holds for integer flows whose values are between $1$ and $k-1$ in absolute value, where each change adds a non-zero integer. We prove this conjecture. The proof is by induction on the number of edges. If a flow enters a vertex along one edge and leaves it along another edge with the same value, the two edges can be replaced by a single edge; this gives a smaller graph. The main step is to change every flow into a flow with such a pair of edges. For $A$-flows we do this when all degrees are at most $4$; repeatedly replacing a vertex of degree at least $6$ by a triangle, following Cranston et al., reduces the general case to this one. For integer flows, we show that, in a graph in which all degrees are even, any two nowhere-zero flows with values in the cyclic group $\mathbb{Z}_k$, $k\ge 4$, are joined by changes that add only $1$, $-1$, $2$ or $-2$, and that such changes lift to integer flows. All theorems of this paper are also proved in the Lean 4 proof assistant.
- [4] arXiv:2611.17489 (cross-list from math.CO) [pdf, html, other]
-
Title: Isolation of $k$-cliques in uniform hypergraphsComments: 13 pagesSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
A copy of a hypergraph $F$ is called an $F$-copy. For any integers $k$ and $r$ with $2 \leq r \leq k$, let $K_k^r$ denote the complete $r$-uniform hypergraph whose vertex set is $[k] = \{1, 2, \dots, k\}$ (that is, the edges of $K_k^r$ are the $r$-element subsets of $[k]$). Given an $r$-uniform $m$-edge hypergraph $H$, the $K_k^r$-isolation number of $H$, denoted by $\iota(H, K_k^r)$, is the size of a smallest subset $D$ of the vertex set of $H$ such that the closed neighbourhood $N[D]$ of $D$ intersects the vertex sets of the $K_k^r$-copies contained by $H$ (equivalently, $H-N[D]$ contains no $K_k^r$-copy). We prove that if $H$ is connected and not a $K_k^r$-copy, then $$\iota(H, K^r_k) \le \left \lfloor \frac{(r-1)m + 1}{(r-1)(\binom{k}{r}+1) + 1} \right \rfloor.$$ The bound is best possible. This is a solution to a problem of Li, Zhang and Ye. We also provide an alternative proof for $r < k$. Both proofs introduce new ideas for establishing bounds on isolation parameters.
- [5] arXiv:2611.17999 (cross-list from math.CO) [pdf, html, other]
-
Title: Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Formal Languages and Automata Theory (cs.FL)
We prove that additive cubes are avoidable over the alphabet $\{0,1,2,3\}$, thereby solving a long-standing question initiated by Pirillo and Varricchio in 1994. By extending the reduction and spectral machinery of Cassaigne, Currie, Schaeffer, and Shallit (2014), we prove that the search for additive cubes in such morphic images reduces to a finite graph traversal. We exhibit eight explicit morphisms from $\{0,1,3,4\}^*$ to $\{0,1,2,3\}^*$ of length 3 whose images on the Cassaigne \textit{et al.} infinite word contain no additive cubes.
Cross submissions (showing 3 of 3 entries)
- [6] arXiv:2406.01999 (replaced) [pdf, html, other]
-
Title: Random Abstract Cell ComplexesComments: 9 pages, 7 figures (plus appendix). For evaluation code, see this https URLSubjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Social and Information Networks (cs.SI); Algebraic Topology (math.AT)
In machine learning and signal processing, methods based on (abstract) cell complexes (CCs) are being applied successfully in different applications. However, there is currently a lack of random models, which are necessary for a thorough evaluation of these methods, both by generating synthetic data and as null models to compare results to. We fill this gap by defining a random model for abstract cell complexes based on independent inclusion probabilities, similar to the Erdős-Rényi model for graphs. We also discuss how modifications to bias the model to incorporate more structure can be implemented. The model can also be used to lift a graph (or other cell complex) to a cell complex of arbitrary dimension. The main challenge in this is that the number of cycles (possible 2-cells) on graphs is exponential, and the same is true in higher dimensions. We overcome this complexity with an approximate sampling algorithm limited to 2-cells (polygons) that is based on a recent advance in sampling cycles on a graph. Using this algorithm, we analyze the properties of random 2-dimensional CCs and showcase its usage as a performance baseline for both topological signal processing and topological deep learning. The algorithm is available in the package py-raccoon on the Python Package Index.
- [7] arXiv:2502.03312 (replaced) [pdf, html, other]
-
Title: An 'Experimental Mathematics' Approach to Stolarsky Interspersions via Automata TheoryComments: This revision fixes up numerous typographical errors and adds some new resultsSubjects: Formal Languages and Automata Theory (cs.FL); Discrete Mathematics (cs.DM); Number Theory (math.NT)
We look at the Stolarsky interspersions (such as the Wythoff array) one more time, this time using tools from automata theory. These tools allow easy verification of many of the published results on these arrays, as well as proofs of new results.
- [8] arXiv:2508.18104 (replaced) [pdf, html, other]
-
Title: On the Parameterized Complexity of Grundy Domination and Zero Forcing ProblemsComments: version published in the Journal of Computer and System SciencesJournal-ref: Journal of Computer and System Sciences 164, Article 103875 (2027)Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
We consider two different problem families that deal with domination in graphs. On the one hand, we focus on dominating sequences. In such a sequence, every vertex dominates some vertex of the graph that was not dominated by any earlier vertex in the sequence. The problem of finding the longest dominating sequence is known as $\mathsf{Grundy~Domination}$. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem: $\mathsf{Grundy~Total~Domination}$, $\mathsf{L\text{-}Grundy~Domination}$, and $\mathsf{Z\text{-}Grundy~Domination}$. We show that all four problem variants are $\mathsf{W[1]}$-complete when parameterized by the solution size.
On the other hand, we consider the family of zero forcing problems which form the parametric duals of the Grundy domination problems. In these problems, one looks for the smallest set of vertices initially colored blue such that certain color change rules are able to color all other vertices blue. It has been shown that the dual of $\mathsf{Z\text{-}Grundy~Domination}$, known as $\mathsf{Zero~Forcing~Set}$, is in $\mathsf{FPT}$ when parameterized by the treewidth or the solution size. We extend the treewidth result to the other three variants of zero forcing and their respective Grundy domination problems. Our algorithm also implies an $\mathsf{FPT}$ algorithm for $\mathsf{Grundy~Domination}$ when parameterized by the number of vertices that are not in the dominating sequence. In contrast, we show that $\mathsf{L\text{-}Grundy~Domination}$ is $\mathsf{W[1]}$-hard for that parameter. - [9] arXiv:2606.29553 (replaced) [pdf, html, other]
-
Title: An annihilation-number Caro-Wei bound: a TxGraffiti conjecture and an independence-number bracketComments: 9 pagesSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
Computable independence bounds give intervals that can be compared by containment or by their worst-case endpoint ratios. For positive maximum degree $\Delta$, the Caro-Wei sum $W$ bounds the independence number from below, while $(\Delta+1)W/2$ bounds it from above. A second interval has the Havel-Hakimi residue as its lower endpoint and the annihilation number as its upper endpoint. This note proves that the annihilation number does not exceed the Caro-Wei upper endpoint. This upper bound is sharp, with equality for regular graphs of positive degree and even order. Since the residue is at least $W$, this upper bound places the residue-annihilation interval inside the Caro-Wei interval. Both endpoints can improve strictly on one graph, although the sharp worst-case endpoint ratio remains unchanged, even for connected graphs. The annihilation-number bound also proves a conjectured lower estimate based on the annihilation number and residue for every connected graph with at least three vertices. Equality in this estimate holds for exactly eight graph types, while the single edge violates it. For maximum degree at least three, however, the estimate never exceeds the residue, even without connectedness.
- [10] arXiv:2607.01159 (replaced) [pdf, html, other]
-
Title: Online Fair Division Meets Reordering BuffersComments: A conference version of this work appears in the Proceedings of the 40th Conference on Neural Information Processing Systems (NeurIPS 2026)Subjects: Computer Science and Game Theory (cs.GT); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
We study the online fair division of indivisible mixed manna among agents with additive valuation functions. Under the standard online model, at each time step an indivisible item arrives; each agent may assign it a positive, negative, or zero value, and it must be irrevocably allocated, before the arrival of the next item. At the same time, we also wish to maintain some fairness guarantee, and in this work we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item (EF1). Given the strong negative and the scarce positive results for this problem without additional assumptions, we augment our algorithms with buffers that can store and rearrange a limited number of items. This setting interpolates naturally between the fully online case (no buffer) and the fully offline case (a buffer large enough to hold all items). We show that algorithms equipped with reasonably sized buffers can achieve strong guarantees for personalized $k$-value instances, i.e., instances in which each agent assigns at most $k$ distinct values to items. In particular, we construct allocations that are EF1 at every time step and EF at most time steps, using a buffer of size linear in $k$ and in the number of agents. Our approach relies on novel combinatorial arguments and on constructing a sequence of envy-free matchings that allocates most items. Finally, we extend our results to general additive valuation functions, with a dependence on the largest per-agent ratio between two values of the same sign, and we also identify limitations of our approach via impossibility results on the use of buffers with smaller size.