About
Combinatorial Theory is a mathematician-run journal, owned by its Editorial Board.
It is dedicated to open access publishing with no fees (no APCs) for authors or readers.
Volume 6, Issue 1, 2026
Untitled Issue
Research Articles
- Relative Lonely Runner spectra
For a subtorus \(T \subseteq (\mathbb{R}/\mathbb{Z})^n\), let \(D(T)\) denote the \(L^\infty\)-distance from \(T\) to the point \((1/2, \ldots, 1/2)\). For a subtorus \(U \subseteq (\mathbb{R}/\mathbb{Z})^n\), define \(\mathcal{S}_1(U)\), the Lonely Runner spectrum relative to \(U\), to be the set of all values of \(D(T)\) as \(T\) ranges over the \(1\)-dimensional subtori of \(U\) not contained in the union of the coordinate hyperplanes of \((\mathbb{R}/\mathbb{Z})^n\). The relative spectrum \(\mathcal{S}_1((\mathbb{R}/\mathbb{Z})^n)\) is the ordinary Lonely Runner spectrum that has been studied previously. Giri and the second author recently showed that the relative spectra \(\mathcal{S}_1(U)\) for two-dimensional subtori \(U \subseteq (\mathbb{R}/\mathbb{Z})^n\) essentially govern the accumulation points of the Lonely Runner spectrum \(\mathcal{S}_1((\mathbb{R}/\mathbb{Z})^n)\). In the present work, we prove that such relative spectra \(\mathcal{S}_1(U)\) have a very rigid arithmetic structure, and that one can explicitly find a complete characterization of each such relative spectrum with a finite calculation; carrying out this calculation for a few specific examples sheds light on previous constructions in the literature on the Lonely Runner Problem.
Mathematics Subject Classifications: 11J13, 52C07, 11J06, 11B75
Keywords: Lonely Runner conjecture, Diophantine approximation, spectra, combinatorial number theory
- 1 supplemental ZIP
- Branching rules of minuscule representations via a new partial order
We introduce a new partial order on the set of all antichains of a fixed size in any poset. When applied to minuscule posets, these partial orders give rise to distributive lattices that appear in the branching rules for minuscule representations of complex simple Lie algebras.
Mathematics Subject Classifications: 06A07, 05E10, 06A11
Keywords: Antichain, distributive lattice, minuscule representation, branching rule
- 1 supplemental ZIP
- Sperner systems with restricted differences
Let \(\mathcal{F}\) be a family of subsets of \([n]\) and \(L\) be a subset of \([n]\). We say \(\mathcal{F}\) is an \(L\)-differencing Sperner system if \(|A\setminus B|\in L\) for any distinct \(A,B\in\mathcal{F}\). Let \(p\) be a prime and \(q\) be a power of \(p\). Frankl first studied \(p\)-modular \(L\)-differencing Sperner systems and showed an upper bound of the form \(\sum_{i=0}^{|L|}\binom{n}{i}\). In this paper, we obtain new upper bounds on \(q\)-modular \(L\)-differencing Sperner systems using elementary \(p\)-adic analysis and polynomial method, extending and improving existing results substantially. Moreover, our techniques can be used to derive new upper bounds on subsets of the hypercube with restricted Hamming distances. One highlight of the paper is the first analogue of the celebrated Snevily's theorem in the \(q\)-modular setting, which results in several new upper bounds on \(q\)-modular \(L\)-avoiding \(L\)-intersecting systems. In particular, we improve a result of Felszeghy, Heged\H{u}s, and Rónyai, and give a partial answer to a question posed by Babai, Frankl, Kutin, and \v{S}tefankovič.
Mathematics Subject Classifications: 05D05, 11B75
Keywords: Sperner theorem, separating polynomial, intersecting family, Hamming distance
- 1 supplemental ZIP
- Representability of the direct sum of uniform \(q\)-matroids
There are many similarities between the theories of matroids and \(q\)-matroids. However, when dealing with the direct sum of \(q\)-matroids many differences arise. Most notably, it has recently been shown that the direct sum of representable \(q\)-matroids is not necessarily representable. In this work, we focus on the direct sum of uniform \(q\)-matroids. Using algebraic and geometric tools, together with the notion of cyclic flats of \(q\)-matroids, we show that this is always representable, by providing a representation over a sufficiently large field.
Mathematics Subject Classifications: 05B35, 94B05, 51E20
Keywords: \(q\)-matroids, representability, evasive subspaces, rank-metric codes, linear sets
- 1 supplemental ZIP
- Order and inverses in the monoid of misère blocking games
This paper considers combinatorial games with the last move losing (misère play) instead of winning (normal play). Misère games form a pomonoid in which no non-zero elements are invertible; normal-play games, however, form a group with a much richer partial order. To compensate, misère researchers typically weaken the comparison relation by restricting to a subset of games, especially to a "universe" (closed under addition, conjugation, and options). For some well-studied universes (like the dicot and dead-ending universes), there exist finite comparison tests and also complete characterisations of their invertible elements; more recently, the invertible elements of every "parental" universe have been characterised. In this paper, we study the recently-defined universe of "blocking games" (containing both dicots and dead-ending games): we develop a finite comparison test, and we improve on the general invertibility characterisation by showing that, as in dead-ending, a game is invertible modulo blocking if and only if it is free of previous-win subpositions (or is equal to such a form).
Mathematics Subject Classifications: 91A46, 06F05, 20M14, 20K27
Keywords: Combinatorial Game Theory, Ordered semigroups
- 1 supplemental ZIP
- Colorful intersections and Tverberg partitions
We prove an extension of Tverberg's classical result on partitioning a point set in \(\mathbb{R}^d\) by replacing the point set with families of convex sets which satisfy the colorful Helly hypothesis. In particular, we show the following for any integers \(d \geq m \geq 1\) and \(r\) a prime power. Suppose \(F_1, F_2, \dots, F_m\) are families of convex sets in \(\mathbb{R}^d\), each of size \({n › (\frac{d}{m}+1)(r-1)}\), such that for every choice \(C_1\in F_1, C_2\in F_2, \dots,C_m \in F_m\) we have \(\bigcap_{i=1}^mC_i\neq \varnothing\). Then, one of the families \(F_i\) admits a Tverberg \(r\)-partition. That is, one of the families \(F_i\) can be partitioned into \(r\) nonempty parts such that the convex hulls of the parts have nonempty intersection. As a corollary, we extend the work of Karasev and Montejano concerning geometric transversals to families of convex sets in \(\mathbb{R}^d\) that satisfy the colorful Helly hypothesis.
Mathematics Subject Classifications: 52A35, 57Q70
Keywords: Tverberg's theorem, geometric transversals, topological combinatorics, configuration space/test map, discrete Morse theory
- 1 supplemental ZIP
- Structure of quasi-crystal graphs and applications to the combinatorics of quasi-symmetric functions
Crystal graphs are powerful combinatorial tools for working with the plactic monoid and symmetric functions. Quasi-crystal graphs are an analogous concept for the hypoplactic monoid and quasi-symmetric functions. This paper makes a combinatorial study of these objects. We explain a previously-observed isomorphism of components of the quasi-crystal graph, and provide an explicit description using a new combinatorial structure called a quasi-array. Then two conjectures of Maas-Gariépy on the interaction of fundamental quasi-symmetric functions and Schur functions and on the arrangement of quasi-crystal components within crystal components are answered, the former positively, the latter negatively.
Mathematics Subject Classifications: 05E05, 05E99
Keywords: Crystal graphs, quasi-crystal graphs, quasi-symmetric functions
- 1 supplemental ZIP
- Growth diagram proofs for the Littlewood identities
The (dual) Cauchy identity has an easy algebraic proof utilising a commutation relation between the up and (dual) down operators. By using Fomin's growth diagrams, a bijective proof of the commutation relation can be "bijectivised" to obtain RSK like correspondences. In this paper we give a concise overview of this machinery and extend it to Littlewood type identities by introducing a new family of relations between these operators, called projection identities. Thereby we obtain infinite families of bijections for the Littlewood identities generalising the classical ones. We believe that this approach will be useful for finding bijective proofs for Littlewood type identities in other settings such as for Macdonald polynomials and their specialisations, alternating sign matrices or vertex models.
Mathematics Subject Classifications: 05E05, 05A19
Keywords: Littlewood identity, growth diagrams, Robinson-Schensted-Knuth correspondence, RSK, Schur polynomials
- 1 supplemental ZIP
- Shuffle bases and quasisymmetric power sums
The algebra of quasisymmetric functions QSym and the shuffle algebra of compositions Sh are isomorphic as graded Hopf algebras (in characteristic zero), and isomorphisms between them can be specified via shuffle bases of QSym. We use the notion of infinitesimal characters to characterize shuffle bases, and we establish a universal property for Sh in the category of connected graded Hopf algebras equipped with an infinitesimal character, analogous to the universal property of QSym as a combinatorial Hopf algebra described by Aguiar, Bergeron, and Sottile. We then use these results to give general constructions for quasisymmetric power sums, recovering four previous constructions from the literature, and study their properties.
Mathematics Subject Classifications: 05E05, 16T30
Keywords: Quasisymmetric functions, quasisymmetric power sums, shuffle algebra, compositions, infinitesimal characters
- 1 supplemental ZIP
- Colored multiset Eulerian polynomials
Colored multiset Eulerian polynomials are a common generalization of MacMahon's multiset Eulerian polynomials and the colored Eulerian polynomials, both of which are known to satisfy well-studied distributional properties including real-rootedness, log-concavity and unimodality. The symmetric colored multiset Eulerian polynomials are characterized and used to prove sufficient conditions for a colored multiset Eulerian polynomial to be self-interlacing. The latter property implies the aforementioned distributional properties as well as others, including the alternatingly increasing property and bi-\(\gamma\)-positivity. To derive these results, multivariate generalizations of an identity due to MacMahon are deduced. The results are applied to a pair of questions, both previously studied in several special cases, that are seen to admit more general answers when framed in the context of colored multiset Eulerian polynomials. The first question pertains to \(s\)-Eulerian polynomials, and the second to interpretations of \(\gamma\)-coefficients.
Mathematics Subject Classifications: 05A05, 05A15, 05A19, 52B20, 52C07
Keywords: Colored permutation, multiset permutation, Eulerian polynomial, real-rooted polynomial, alternatingly increasing, self-interlacing, gamma positivity, Ehrhart theory
- 1 supplemental ZIP
- High-dimensional envy-free partitions
A vast array of envy-free results have been found for the subdivision of one-dimensional resources, such as the interval \([0,1]\). The goal is to divide the space into \(n\) pieces and distribute them among \(n\) guests such that each receives their favorite pieces. We study high-dimensional versions of these results. We prove that several spaces of convex partitions of \(\mathbb{R}^d\) allow for envy-free division among any \(n\) guests. We also prove the existence of convex partitions of \(\mathbb{R}^d\) which allow envy-free divisions among several groups of \(n\) guests simultaneously.
Mathematics Subject Classifications: 91B32, 52A37, 55M20, 28A75
Keywords: Mass partition, KKM cover, Envy-free partition, Equivariant topology, Voronoi diagram
- 1 supplemental ZIP
- The intersection density of cubic arc-transitive graphs with \(2\)-arc-regular full automorphism group equal to \( \operatorname{PGL}_{2}(q)\)
The intersection density of a transitive permutation group \(G\leq \operatorname{Sym}(V)\) is the ratio between the largest size of a subset of \(G\) in which any two agree on at least one element of \(V\), and the order of a point-stabilizer of \(G\). In this paper, we determine the intersection densities of the automorphism groups of the arc-transitive graphs admitting a \(2\)-arc-regular full automorphism group \(G^* = \operatorname{PGL}_{2}(q)\) and an arc-regular subgroup of automorphism \(G = \operatorname{PSL}_{2}(q)\).
Mathematics Subject Classifications: 05C35, 05C69, 20B05
Keywords: Derangement graphs, cocliques, projective special linear groups
- 1 supplemental ZIP
- Two gluing methods for string C-group representations of the symmetric groups
The study of string C-group representations of rank at least \(n/2\) for the symmetric group \(S_n\) has gained a lot of attention in the last fifteen years. In a recent paper, Cameron et al. gave a list of permutation representation graphs of rank \(r\geq n/2\) for \(S_n\), having a fracture graph and a non-perfect split. They conjecture that these graphs are permutation representation graphs of string C-groups. In trying to prove this conjecture, we discovered two new techniques to glue two CPR graphs for symmetric groups together. We discuss the cases in which they yield new CPR graphs. By doing so, we invalidate the conjecture of Cameron et al. We believe our gluing techniques will be useful in the study of string C-group representations of high ranks for the symmetric groups.
Mathematics Subject Classifications: 20B30, 05C25, 52B15
Keywords: String C-group representations, symmetric groups, permutation representation graphs, CPR graphs
- 1 supplemental ZIP
- Quotients of M-convex sets and M-convex functions
We unify the study of quotients of matroids, polymatroids, valuated matroids and strong maps of submodular functions in the framework of Murota's discrete convex analysis. As a main result, we compile a list of ten equivalent characterizations of quotients for M-convex sets, generalizing existing formulations for (poly)matroids and submodular functions. We also initiate the study of quotients of M-convex functions, constructing a hierarchy of four separate characterizations. Our investigations yield new insights into the fundamental operation of induction, as well as the structure of linking sets and linking functions, which are generalizations of linking systems and bimatroids.
Mathematics Subject Classifications: 05B35, 14T15, 52B20, 52B40, 14M15, 90C25, 90C27
Keywords: Discrete convex functions, flag matroids, discrete convex analysis, matroid theory, matroid quotients, polymatroids
- 1 supplemental ZIP
- Chow polynomials of uniform matroids are real-rooted
June Huh and Matthew Stevens conjectured that the Hilbert-Poincaré series of the Chow ring of any matroid is a polynomial with only real zeros. We prove this conjecture for the class of uniform matroids. We also prove that the Chow polynomial and the augmented Chow polynomial of any maximal ranked poset have only real zeros. Mathematics Subject Classifications: 05E14, 05B35, 06A07, 26C10 Keywords: Chow polynomials, real-rooted polynomials, partially ordered sets, geometric lattices
- 1 supplemental ZIP
- Uncountably many enumerations of well-quasi-ordered permutation classes
We construct an uncountable family of well-quasi-ordered permutation classes, each with a distinct enumeration sequence. This disproves a conjecture that all well-quasi-ordered permutation classes have algebraic generating functions, and in fact shows that many such classes lack D-finite or D-algebraic generating functions. Our construction is based on an uncountably large collection of factor-closed, well-quasi-ordered binary languages due to Pouzet.
Mathematics Subject Classifications: 05A05, 05A15, 06A07
Keywords: Generating functions, permutation classes, well-quasi-order
- 1 supplemental ZIP
- Improved bound on the number of cycle sets
The cycle set of a graph \(G\) is the set consisting of all sizes of cycles in \(G\). Answering a conjecture of Erdős and Faudree, Verstraëte showed that there are at most \(2^{n - n^{1/10}}\) different cycle sets of graphs with \(n\) vertices. We improve this bound to \(2^{n - n^{1/2 - o(1)}}\). Our proof follows the general strategy of Verstraëte of reducing the problem to counting cycle sets of Hamiltonian graphs with many chords or a large maximum degree. The key new ingredients are near-optimal container lemmata for cycle sets of such graphs.
Mathematics Subject Classifications: 05C30, 05C38
Keywords: Cycle sets, container method
- 1 supplemental ZIP
- Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction-based approach
By a classic result of Gessel, the exponential generating functions for \(k\)-regular graphs are D-finite. Using Gröbner bases in Weyl algebras, we compute the linear differential equations satisfied by the generating function for 5-, 6-, and 7- regular graphs. The method is sufficiently robust to consider variants such as graphs with multiple edges, loops, and graphs whose degrees are limited to fixed sets of values.
Mathematics Subject Classifications: 05C30, 12H05
Keywords: Regular graph, enumeration, Weyl algebra, reduction-based integration
- 1 supplemental ZIP