CS Paper Radar

Daily listing

2026-11-17 · cs.DM

5 papers first submitted this day (UTC) in cs.DM — Discrete Mathematics. arXiv announces a day's submissions the next evening, so the newest day fills up over ~24 h.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works

Theory & Algorithms 5

More lower bounds for Hales--Jewett and van der Waerden numbers

cs.DM math.CO ·2026-11-17 ·Younes Mouhib
code/data
Abstract · 6 pages. Explicit certificates, search algorithms, and verification code are available at https://github.com/ysmouhib/hj-vdw-reproducibility…

We give explicit colourings improving the comparison lower bounds assembled here for several Hales--Jewett and van der Waerden numbers. The main algebraic tool generalises Rabung's power-residue colouring from arithmetic progressions to arbitrary sets. If every translate of a t-element set S in F_p meets at least two classes of the r-th power character, and the integer weights have both parities, then a period-2p one-weight colouring of [t]^p has no monochromatic combinatorial line. The 19 displayed algebraic certificates comprise 18 improvements and one closed-form reproduction; they include HJ(4,3)>=164, HJ(5,4)>=7418, and HJ(5,6)>=34034. The underlying period-p construction also proves kappa_ow(t,r)>=p-1 for the one-weight bracket ceiling, in particular kappa_ow(5,4)>=7416 and kappa_ow(5,6)>=34032. Warm breakout-weighted tabu search on the type simplex gives HJ(3,4)>=51. Whole-colouring local search gives W(8,3)>522, W(11,3)>1193, and W(17,3)>3620. All accepted certificates are available separately and are checked by direct enumeration; unresolved searches are reported as UNKNOWN, not UNSAT.

0.56

Heap-type permutation generation with a prescribed final arrangement

cs.DM math.COcs.DS ·2026-11-17 ·Luís M. S. Russo
theory
Abstract · 22 pages. Software archived at https://doi.org/10.5281/zenodo.24311260

Heap's algorithm generates all permutations of an array of n items, obtaining each one from its predecessor by a single swap. We determine the net permutation applied to the array by every complete recursive call: a transposition when the number of items is odd and at least three, and a cycle through all items when it is even. We show that the output of each call is a concatenation of right cosets of the symmetric group on one item fewer, and we prove a general formula: the order in which the items are parked at the last position may be chosen freely, every such order corresponds to exactly one valid schedule, and it determines the net permutation of the call. Two variants follow. In the cyclic variant a complete sweep over an even number of items rotates the array by one position. In the extremal variant, for even n, a sweep started from the identity ends in the lexicographically largest arrangement that any single-swap enumeration can leave; by a parity argument this is the reversal exactly when n is congruent to 2 modulo 4. The construction of the extremal variant is proved correct when n is divisible by 4 and verified by computer for all even n up to 10000.

0.41

Strong Transitivity of Group Cellular Automata: Characterization and Decidability

cs.DM cs.FLmath.DS ·2026-11-17 ·Niccolò Castronuovo, Alberto Dennunzio, Luciano Margara
theory
Abstract

A discrete-time dynamical system is strongly transitive if every point can be reached, in finitely many steps, from every non-empty open set. We study this property for group cellular automata, \ie cellular automata over a finite group alphabet whose global map is a group endomorphism, in every dimension $d\geq1$. We prove that no group cellular automaton over a non-abelian group is strongly transitive, and we develop a decomposition of group cellular automata over abelian groups, via quotients by power subgroups, which preserves strong transitivity. For linear cellular automata over $(\mathbb Z/p\mathbb Z)^n$ we use Pontryagin duality to characterize strong transitivity in terms of the characteristic polynomial $χ_A$ of the associated matrix $A$ of Laurent polynomials: the automaton is strongly transitive if and only if $\det(A)\neq0$ and no irreducible factor of $χ_A$ has an invertible constant term. Combining these results, we obtain that strong transitivity is decidable for group cellular automata in every dimension. For every fixed dimension $d$, we give an explicit decision procedure whose running time is polynomial in the group size $N$, the number $k$ of neighbours, and the neighbourhood radius $\varrho$.

0.34

Sharp lower bounds for weighted bisections of graphs with bounded maximum degree

cs.DM math.CO ·2026-11-17 ·Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou
theory
Abstract

A bisection of a graph is a partition of its vertex set into two parts the sizes of which differ by at most one. We prove that every finite simple graph of maximum degree at most an odd positive integer $k$, with arbitrary nonnegative real edge weights, has a bisection of weight at least $(k+1)/(2k)$ times its total edge weight. The corresponding bound $(k+2)/(2(k+1))$ for even $k$ follows immediately. Both coefficients are best possible. Somewhat surprisingly, these are exactly the sharp coefficients known for maximum weighted cuts, despite the additional balance requirement.

0.27

On (Pathwidth, Clique)-boundedness

cs.DM math.CO ·2026-11-17 ·Amir Nikabadi
theory
Abstract

We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor $K_{σ,σ}$ as an induced minor, where $\B_ρ$ is the complete binary tree of height $ρ$ and the bound depends only on $ρ$ and $σ$. We then obtain an asymptotically sharp bound on the path-independence number of $n$-vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest $F$ and every $\ell\in\N$, there is a constant $k=k(F,\ell)\in\N$ such that every graph $G$ with no induced theta or $\ell$-long prism and no induced subgraph isomorphic to $F$ satisfies tree-independence number at most $k$. This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer $s\ge2$, we characterize the forests $F$ for which excluding $F$ as an induced minor and $K_{s,s}$ as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with $K_{s,s}$ excluded as a subgraph.

0.08