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 5, Issue 2, 2025
Research Articles
- Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
In this article, we study systems of \(n\geq 1\), not necessarily linear, discrete differential equations (DDEs) of order \(k\geq 1\) with one catalytic variable. We provide a constructive and elementary proof of algebraicity of the solutions of such equations. This part of the present article can be seen as a generalization of the pioneering work by Bousquet-Mélou and Jehanne (2006) who settled down the case \(n=1\). Moreover, we obtain effective bounds for the algebraicity degrees of the solutions and provide an algorithm for computing annihilating polynomials of the algebraic series. Finally, we compare three different strategies for solving systems of DDEs in view of practical applications.
Mathematics Subject Classifications: 05A99, 13A99, 14R15
Keywords: Catalytic variable, algebraic series, formal power series, discrete differential equations, polynomial systems
- 1 supplemental ZIP
- On the scaling of random Tamari intervals and Schnyder woods of random triangulations (with an asymptotic D-finite trick)
We consider a Tamari interval of size \(n\) (i.e., a pair of Dyck paths which are comparable for the Tamari relation) chosen uniformly at random. We show that the height of a uniformly chosen vertex on the upper or lower path scales as \(n^{3/4}\), and has an explicit limit law.
By the Bernardi-Bonichon bijection, this result also describes the height of points in the canonical Schnyder trees of a uniform random plane triangulation of size \(n\).
The exact solution of the model is based on polynomial equations with one and two catalytic variables. To prove the convergence from the exact solution, we use a version of moment pumping based on D-finiteness, which is essentially automatic and should apply to many other models. We are not sure to have seen this simple trick used before.
It would be interesting to study the universality of this convergence for decomposition trees associated to positive Bousquet-Mélou-Jehanne equations.
Mathematics Subject Classifications: 05A15, 05A16, 60F99
Keywords: Tamari lattice, interval, scaling limit, asymptotics, method of moments, algebraic functions, computer algebra, random triangulation, catalytic variables, discrete differential equation
- 1 supplemental ZIP
- Tutte polynomials of matroids as universal valuative invariants
We provide a full classification of all families of matroids that are closed under duality and minors, and for which the Tutte polynomial is a universal valuative invariant. There are four inclusion-wise maximal families, two of which are the class of elementary split matroids and the class of graphic Schubert matroids. As a consequence of our framework, we derive new relations among Tutte polynomials of matroids. For example, we show that the Tutte polynomial of every matroid can be expressed uniquely as an integral combination of Tutte polynomials of graphic Schubert matroids.
Mathematics Subject Classifications: 05B35, 05C31, 52B40, 52B45
Keywords: Tutte polynomials, matroids, geometric lattices, matroid polytopes, valuations
- 1 supplemental ZIP
- The probability that a random triple of dice is transitive
An \(n\)-sided die is an \(n\)-tuple of positive integers. We say that a die \((a_1,\dots,a_n)\) beats a die \((b_1,\dots,b_n)\) if the number of pairs \((i,j)\) such that \(a_i›b_j\) is greater than the number of pairs \((i,j)\) such that \(a_i‹b_j\). We show that for a natural model of random \(n\)-sided dice, if \(A, B\) and \(C\) are three random dice then the probability that \(A\) beats \(C\) given that \(A\) beats \(B\) and \(B\) beats \(C\) is approximately 1/2. In other words, the information that \(A\) beats \(B\) and \(B\) beats \(C\) has almost no effect on the probability that \(A\) beats \(C\). This proves a statement that was conjectured by Conrey, Gabbard, Grant, Liu and Morrison for a different model.
Mathematics Subject Classifications: 60C05
Keywords: Intransitive dice, central limit theorems
- 1 supplemental ZIP
- A realization of poset associahedra
Given any connected poset \(P\), we provide a simple realization of Galashin's \(P\)-associahedron \(\mathscr A(P)\) as a convex polytope in \(\mathbb R^P.\) This realization is inspired by the description of \(\mathscr A(P)\) as a compactification of the configuration space of order-preserving maps \(P \to \mathbb{R}.\) Additionally, we provide an analogous realization for Galashin's affine poset cyclohedra.
Mathematics Subject Classifications: 52B11, 06A07
Keywords: Poset, associahedron, cyclohedron, realization, configuration space, compactification
- 1 supplemental ZIP
- Upho lattices I: examples and non-examples of cores
A poset is called upper homogeneous, or "upho," if every principal order filter of the poset is isomorphic to the whole poset. We study (finite type \(\mathbb{N}\)-graded) upho lattices, with an eye towards their classification. Any upho lattice has associated to it a finite graded lattice called its core, which determines its rank generating function. We investigate which finite graded lattices arise as cores of upho lattices, providing both positive and negative results. On the one hand, we show that many well-studied finite lattices do arise as cores, and we present combinatorial and algebraic constructions of the upho lattices into which they embed. On the other hand, we show there are obstructions which prevent many finite lattices from being cores.
Mathematics Subject Classifications: 06A07, 05B35, 06C10, 20M32
Keywords: Upho posets, rank generating functions, characteristic polynomials, geometric lattices, supersolvable lattices, Dowling lattices, Garside monoids
- 1 supplemental ZIP
- Viennot shadows and graded module structure in colored permutation groups
Let \(\mathbf{x}_{n \times n}\) be a matrix of \(n \times n\) variables, and let \(\mathbb{C}[\mathbf{x}_{n \times n}]\) be the polynomial ring on these variables. Let \(\mathfrak{S}_{n,r}\) be the group of colored permutations, consisting of \({n \times n}\) complex matrices with exactly one nonzero entry in each row and column, where each nonzero entry is an \(r\)-th root of unity. We associate an ideal \(I_{\mathfrak{S}_{n,r}} \subseteq \mathbb{C}[\mathbf{x}_{n \times n}]\) with the group \(\mathfrak{S}_{n,r}\), and use orbit harmonics to give an ideal-theoretic extension of the Viennot shadow line construction to \(\mathfrak{S}_{n,r}\). This extension gives a standard monomial basis of \(\mathbb{C}[\mathbf{x}_{n \times n}]/I_{\mathfrak{S}_{n,r}}\), and introduces an analogous definition of "longest increasing subsequence" to the group \(\mathfrak{S}_{n,r}\). We examine the extension of Chen's conjecture to this analogy. We also study the structure of \(\mathbb{C}[\mathbf{x}_{n \times n}]/I_{\mathfrak{S}_{n,r}}\) as a graded \(\mathfrak{S}_{n,r} \times \mathfrak{S}_{n,r}\) module, which subsequently induces a graded \(\mathfrak{S}_{n,r} \times \mathfrak{S}_{n,r}\) module structure on the \(\mathbb{C}\)-algebra \(\mathbb{C}[\mathfrak{S}_{n,r}]\).
Mathematics Subject Classifications: 05E10, 05E16, 05E18, 05E14
Keywords: Viennot's shadow lines, orbit harmonics, ideals, graded modules
- 1 supplemental ZIP
- Maps related to polar spaces preserving an extremal Weyl distance
Let \(\Omega_i\) and \(\Omega_j\) be the sets of elements of respective types \(i\) and \(j\) of a polar space \(\Delta\) of rank at least \(3\). We show that a permutation \(\rho\) of \(\Omega_i \cup \Omega_j\) with the property that, for each \(I \in \Omega_i \) and \(J\in\Omega_j\), \(I\) and \(J\) generate a maximal singular subspace in \(\Delta\) if and only if \(\rho(I)\) and \(\rho(J)\) generate a maximal singular subspace in \(\Delta\), is induced by an automorphism of \(\Delta\). Building-theoretically, this means that if \(\rho\) preserves a certain Weyl distance in the Tits-building corresponding to \(\Delta\), then it preserves all Weyl-distances.
Mathematics Subject Classifications: 51E24, 51A50
Keywords: Polar spaces, Weyl distance
- 1 supplemental ZIP
- Combinatorics of \(m = 1\) grasstopes
A Grasstope is the image of the totally nonnegative Grassmannian \(\operatorname{Gr}_{\geq 0}(k,n)\) under a linear map \(\operatorname{Gr}(k,n)\dashrightarrow \operatorname{Gr}(k,k+m)\). This is a generalization of the amplituhedron, a geometric object of great importance to calculating scattering amplitudes in physics. The amplituhedron is a Grasstope arising from a totally positive linear map. While amplituhedra are relatively well-studied, much less is known about general Grasstopes. We study Grasstopes in the \(m=1\) case and show that they can be characterized as unions of cells of a hyperplane arrangement satisfying a certain sign variation condition, extending the work of Karp and Williams. Inspired by this characterization, we also suggest a notion of a Grasstope arising from an arbitrary oriented matroid.
Mathematics Subject Classifications: 05E14, 14N10, 14M15
Keywords: Grasstope, Grassmannian, amplituhedron, hyperplane arrangements, sign vectors, oriented matroids
- 1 supplemental ZIP
- A framework unifying some bijections for graphs and its connection to Lawrence polytopes
Let \(G\) be a connected graph. The Jacobian group (also known as the Picard group or sandpile group) of \(G\) is a finite abelian group whose cardinality equals the number of spanning trees of \(G\). The Jacobian group admits a canonical simply transitive action on the set \(\mathcal{R}(G)\) of cycle-cocycle reversal classes of orientations of \(G\). Hence one can construct combinatorial bijections between spanning trees of \(G\) and \(\mathcal{R}(G)\) to build connections between spanning trees and the Jacobian group. The BBY bijections and the Bernardi bijections are two important examples. In this paper, we construct a new family of such bijections that includes both. Our bijections depend on a pair of atlases (different from the ones in manifold theory) that abstract and generalize certain common features of the two known bijections. The definitions of these atlases are derived from triangulations and dissections of the Lawrence polytopes associated to \(G\). The acyclic cycle signatures and cocycle signatures used to define the BBY bijections correspond to regular triangulations. Our bijections can extend to subgraph-orientation correspondences. Most of our results hold for regular matroids. We present our work in the language of fourientations, which are a generalization of orientations.
Mathematics Subject Classifications: 05C30, 05C25, 52B05, 52C40
Keywords: Sandpile group, cycle-cocycle reversal class, Lawrence polytope, triangulation, dissection, fourientation
- 1 supplemental ZIP
- A signed \(e\)-expansion of the chromatic quasisymmetric function
We prove a new signed elementary symmetric function expansion of the chromatic quasisymmetric function of any natural unit interval graph. We then use a sign-reversing involution to prove a new combinatorial formula for \(K\)-chains, which are graphs formed by joining cliques at single vertices. This formula immediately implies \(e\)-positivity and \(e\)-unimodality for \(K\)-chains. We also prove a version of our signed \(e\)-expansion for the chromatic symmetric function for arbitrary graphs.
Mathematics Subject Classifications: 05E05, 05E10, 05C15
Keywords: Chromatic quasisymmetric function, elementary symmetric function, natural unit interval graph, proper colouring, Shareshian-Wachs conjecture, Stanley-Stembridge conjecture
- 1 supplemental ZIP
- Anzahl theorems for disjoint subspaces generating a non-degenerate subspace: quadratic forms
In this paper, we solve a classical counting problem for non-degenerate quadratic forms defined on a vector space in odd characteristic: given a subspace \(\pi\), we determine the number of non-singular subspaces that are trivially intersecting with \(\pi\) and span a nonsingular subspace with \(\pi\). Lower bounds for the quantity of such pairs where \(\pi\) is nonsingular were first studied in [S. P. Glasby, Alice C. Niemeyer, and Cheryl E. Praeger. The probability of spanning a classical space by two non-degenerate subspaces of complementary dimensions. Finite Fields Appl., 82:31, 2022], which was later improved for even-dimensional subspaces in [S. P. Glasby, F. Ihringer, and S. Mattheus. The proportion of non-degenerate complementary subspaces in classical spaces. Des. Codes Cryptography, 91(9):2879– 2891, 2023] and generalised in [S.P. Glasby, A.C. Niemeyer, and C.E. Praeger. Random generation of direct sums of finite non-degenerate subspaces. Linear Algebra Appl., 649:408–432, 2022]. The explicit formulae, which give the exact proportion and improve the known lower bounds were derived in the symplectic and Hermitian case in [M. De Boeck and G. Van de Voorde. Anzahl theorems for trivially intersecting subspaces generating a non-singular subspace. I: Symplectic and Hermitian forms. Linear Algebra and its Applications, 699:367–402, 2024]. This paper deals with the more complicated quadratic case.
Mathematics Subject Classifications: 51A50, 51E20
Keywords: Quadratic forms, counting, non-singular subspace
- 1 supplemental ZIP
- Asymptotic distribution of parameters in trivalent maps and linear lambda terms
In this work, we study the limit distributions of various combinatorial parameters in trivalent maps, linear \(\lambda\)-terms, and other related families of objects. We focus on parameters in maps which naturally correspond to parameters in \(\lambda\)-terms and vice versa, allowing us to employ techniques from map theory and the \(\lambda\)-calculus in a combinatorial interplay. Some examples of the parameters we study are: the number of bridges in rooted trivalent maps and of subterms in closed linear \(\lambda\)-terms as well as the number of vertices of degree 1 in \((1,3)\)-valent maps and of free variables in open linear \(\lambda\)-terms. To analyse their distributions, we introduce appropriate tools: a moment-pumping schema for differential equations and a composition schema inspired by Bender's theorem.
Mathematics Subject Classifications: 05A16, 05A19, 03B40, 05C30
Keywords: Random maps on surfaces, lambda calculus, analytic combinatorics, limit laws
- 1 supplemental ZIP
- Volume inequalities for flow polytopes of full directed acyclic graphs
Given a finite directed acyclic graph, the space of non-negative unit flows is a lattice polytope called the flow polytope of the graph. We consider the volumes of flow polytopes for directed acyclic graphs on \(n+1\) vertices with a fixed degree sequence, with a focus on graphs having in- and out-degree two on every internal vertex. When the out-degree of the source is three and the number of vertices is fixed, we prove that there is an interchange operation on the edge set of these graphs that induces a partial order on the graphs isomorphic to a Boolean algebra. Further, we prove that as we move up through this partial order, the volumes of the corresponding flow polytopes weakly decrease. Finally, we show that each such graph is strongly planar and we provide an alternative interpretation of our results in the context of linear extensions for posets that are bipartite non-crossing trees.
Mathematics Subject Classifications: 52B20, 05C20, 05C21, 52B05
Keywords: Flow polytopes, Volumes, Posets, Linear Extensions, Degree Sequence
- 1 supplemental ZIP
- Two constructions of quaternary Legendre pairs of even length
We give the first general constructions of even length quaternary Legendre pairs: there is a quaternary Legendre pair of length \((q-1)/2\) for every prime power \(q\) congruent to \(1\) modulo \(4\), and there is a quaternary Legendre pair of length \(2p\) for every odd prime \(p\) for which \(2p-1\) is a prime power.
Mathematics Subject Classifications: 05B20, 05B30
Keywords: Legendre pair, quaternary Legendre pair, Goethals-Seidel sequences, Hadamard matrix
- 1 supplemental ZIP
- The cyclicity rank of empty lattice simplices
We are interested in algebraic properties of empty lattice simplices \(\Delta\), that is, \(d\)-dimensional lattice polytopes containing exactly \(d+1\) points of the integer lattice \(\mathbb{Z}^d\). The cyclicity rank of \(\Delta\) is the minimal number of cyclic subgroups that the quotient group of \(\Delta\) splits into. It is known that up to dimension \(d \leq 4\), every empty lattice \(d\)-simplex is cyclic, meaning that its cyclicity rank is at most \(1\). We determine the maximal possible cyclicity rank of an empty lattice \(d\)-simplex for dimensions \(d \leq 8\), and determine the asymptotics of this number up to a logarithmic term.
Mathematics Subject Classifications: 52B20, 11H06, 14E30
Keywords: Empty lattice simplices, quotient groups, Hermite normal forms
- 1 supplemental ZIP
- Mixed radix numeration bases: Horner's rule, Yang-Baxter equation and Furstenberg's conjecture
Mixed radix bases in numeration is a very old notion but it is rarely studied on its own or in relation with concrete problems related to number theory. Starting from the natural question of the conversion of a basis to another for integers as well as polynomials, we use mixed radix bases to introduce two-dimensional arrays with suitable filling rules. These arrays provide algorithms of conversion which use only a finite number of Euclidean division to convert from one basis to another; it is interesting to note that these algorithms are generalizations of the well-known Horner's rule of quick evaluation of polynomials. The two-dimensional arrays with local transformations are reminiscent of statistical mechanics models: we show that changes between three numeration bases are related to the set-theoretical Yang-Baxter equation and this is, up to our knowledge, the first time that such a structure is described in number theory. As an illustration, we reinterpret well-known results around Furstenberg's conjecture in terms of Yang-Baxter transformations between mixed radix bases, hence opening the way to alternative approaches.
Mathematics Subject Classifications: 11A63, 11A67, 16T25
Keywords: Numeration basis, Yang-Baxter equation
- 1 supplemental ZIP