CS Paper Radar

Daily listing

2026-11-18 · math.CO

8 papers first submitted this day (UTC) in math.CO — math.CO. 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 7

A combinatorial proof of a symmetric joint distribution on strict binary trees

cs.DM math.CO ·2026-11-18 ·Shishuo Fu
Abstract · 11 pages, 2 figures

Nonplanar strict binary trees on $2n+1$ vertices are enumerated by the reduced tangent numbers $T_{2n+1}/2^n$, whose entries are refined by Poupard's triangle. Poupard defined the end of the minimal chain ($\mathrm{eoc}$) and the parent of the maximum leaf ($\mathrm{pom}$) on these trees, proving that $\mathrm{eoc}$ and $\mathrm{pom}+1$ share this triangular distribution. Foata and Han subsequently showed via tree calculus and partial difference equations that the joint distribution of $(\mathrm{eoc}, 2n+1-\mathrm{pom})$ is symmetric. By introducing an auxiliary tree statistic dual to $\mathrm{eoc}$, we give a bijective proof of this symmetry. Our proof composes a recursive bijection on strict binary trees, a bijection to alternating André permutations, and the reverse-complement involution on permutations.

0.42

An additive-square-free word over an alphabet of size 6

cs.DM math.CO ·2026-11-18 ·Jeffrey Shallit
Abstract

An additive square over $\mathbb{N}$ is two consecutive nonempty blocks of the same length and same sum. For example, 1423 is an additive square, since 14 and 23 both have length 2 and sum 5. Solving a problem that has been open for more than 50 years, we give an example of an infinite word over a 6-letter subset of N that avoids additive squares.

0.37

Faster polynomial-space algorithms for poset problems

cs.DS math.CO ·2026-11-18 ·László Kozma, Junqi Tan
Abstract

We give a polynomial-space, deterministic, exact algorithm for counting linear extensions of partial orders over $n$ elements, with running time $O^*((2\sqrt{2})^{n}) \subseteq O(2.829^n)$. This improves upon the long-standing bound of $O^*(4^{n})$ attainable by standard divide and conquer (Savitch 1970, Gurevich and Shelah 1987). Our algorithm uses a similar balanced splitting approach as the classical algorithm, but applies it only to the elements outside a largest antichain. For the elements of the antichain itself we develop a formula based on inclusion-exclusion that accounts for the ways in which they can appear in a linear extension. The technique is also applicable to other problems on posets, which we illustrate by solving the well-studied jump number problem in a similar running time of $O^*((2\sqrt{2})^{n})$ and polynomial space. To our knowledge, these are the first polynomial-space algorithms with a running time below $4^n$ for both problems.

0.35

A Well-Separated Pair Decomposition of Linear Size for Unit-Disk Graphs

cs.CG math.CO ·2026-11-18 ·Mark de Berg, Joachim Gudmundsson, Sampson Wong
theory
Abstract

We prove that every connected Euclidean-weighted unit-disk graph on $n$ vertices has a $(1/\varepsilon)$-well-separated pair decomposition of size $O(n\varepsilon^{-2}\log(1/\varepsilon))$. This resolves an open problem posed by Gao and Zhang in 2003. We also show that this bound is tight: there are connected unit-disk graphs for which any $(1/\varepsilon)$-well-separated pair decomposition has size $Ω(n\varepsilon^{-2}\log (1/\varepsilon))$.

0.27

The computational complexity of Undirected Vertex Geography with maximum height 3

cs.CC math.CO ·2026-11-18 ·Craig Tennenhouse, Kanae Yoshiwatari
Abstract · 13 pages

The impartial game Undirected Vertex Geography is known to be polynomial time solvable. The variant in which vertices are assigned heights with maximum value m that reduce by 1 whenever the token is moved from that vertex, denoted UIRm, is known to be polynomial time solvable when m=2 and PSPACE-complete when m=4. We solve the open question of the computational complexity of UIR3 by a reduction from Directed vertex geography, and show that the complexity holds when the underlying graph is planar and (a) has degree at most 3, (b) is bipartite with maximum degree 4, or (c) is bipartite with maximum degree 5 and only has heights of 1 and 3.

0.24

List packing for graphs with small arboricity

cs.DM math.CO ·2026-11-18 ·Stijn Cambie, Wouter Cames van Batenburg, Xuding Zhu
theory
Abstract · 10 pages (of which 2 for the main proofs)

We prove that every graph $G$ whose edge set is the union of $r$ forests has list packing number at most $2^r$. This means that for all $k\ge 2^r$ and every list-assignment $L$ with lists of size $k$, the graph $G$ admits $k$ disjoint proper $L$-colourings. While for large $r$ this bound is far from optimal, for $r\in\{1,2\}$ it is sharp. As a direct corollary of the case $r=2$, we obtain that every triangle-free planar graph has list packing number at most $4$, thus improving upon a result of Dvořák, Masařík, Musílek and Pangrác and providing the optimal answer to a question of Dvořák, Postle and Norin on (weighted) $ε$-flexibility of such graphs. As a corollary of the case $r=3$, we obtain a short alternative proof that every $K_5$-minor-free (and hence every planar) graph has list-packing number at most $8$, matching the state of the art. All results above also hold for the stronger notion of correspondence packing.

0.23

Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes

cs.DM math.CO ·2026-11-18 ·Vida Dujmović, Robert Hickingbotham, Pat Morin, David R. Wood
theory
Abstract · 28 pages, 4 figures, written by humans

We show that, for all positive integers $t$ and $Δ$, there exists an integer $c$ such that, for every $K_t$-minor-free graph $G$ with maximum degree at most $Δ$, there exists a graph $H$ of treewidth at most $3$ and a path $P$ such that $G$ is isomorphic to a subgraph of the strong product $H\boxtimes P\boxtimes K_c$. This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of $H$ independently of $t$ and $Δ$. As an immediate consequence we obtain a bound of $O(r^4)$ on the $r$-weak colouring number of bounded-degree graphs from any proper minor-closed graph class.

0.18

People & Society 1

Dessins d'Enfants as a Topological Lens on Temporal Hypergraphs

cs.SI math.ATmath.CO ·2026-11-18 ·Mehmet Emin Aktas, Esra Akbas
theory
Abstract

Hypergraphs are the natural language for group interactions, and topological data analysis has given us several ways to look at them: simplicial and cell complexes, persistent homology, and sheaves. All of these treat a hyperedge as an unordered set. In this paper, we introduce a different and, to our knowledge, new viewpoint that comes from Grothendieck's theory of dessins d'enfants and, unlike these approaches, takes into account the order in which vertices appear in each hyperedge and hyperedges appear around each vertex. A dessin is a bipartite graph drawn on a closed orientable surface. Through Walsh's classical correspondence between hypermaps and bipartite maps, every hypergraph equipped with a cyclic order of incidences at each vertex and inside each hyperedge is a dessin, and therefore determines a surface with faces and a genus. We develop this idea for temporal hypergraphs and build the surface by replaying history: incidences are added in the order in which they occurred, and each new incidence is inserted into the cyclic orders built so far, next to the earlier incidence to which it is related. We prove that every insertion either grows the hypergraph without creating a cycle, closes a cycle locally by splitting a face, or closes it globally by adding a handle; the number of independent cycles equals the number of local plus handle events, and the genus equals the number of handle events. These counts give interpretable, size-controlled measures of how a temporal hypergraph's cycles organize on a surface as it grows. We apply our method to five Stack Exchange communities and show that it separates communities that standard statistics cannot tell apart and quantifies how much the real order of interactions matters. We further discuss what the surface viewpoint adds to existing higher-order network analysis and how it opens a path toward dessin-based learning on hypergraphs.

0.34