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 3, 2025
Research Articles
- Positroid envelopes and graphic positroids
Positroids are matroids realizable by real matrices with all nonnegative maximal minors. They partition the ordered matroids into equivalence classes, called positroid envelope classes, by their Grassmann necklaces. We give an explicit graph construction that shows that every positroid envelope class contains a graphic matroid. We prove that a graphic positroid is the unique matroid in its positroid envelope class. Finally, we show that every graphic positroid has an oriented graph representable by a signed incidence matrix with all nonnegative minors.
Mathematics Subject Classifications: 05B35
Keywords: Graphic positroids, positroids, decorated permutations
- 1 supplemental ZIP
- The critical group of a combinatorial map
Motivated by the appearance of embeddings in the theory of chip-firing and the critical group of a graph, we introduce a version of the critical group (or sandpile group) for combinatorial maps, that is, for graphs embedded in orientable surfaces. We provide several definitions of our critical group, by approaching it through analogues of the cycle-cocycle matrix, the Laplacian matrix, and as the group of critical states of a chip-firing game (or sandpile model) on the edges of a map.
Our group can be regarded as a perturbation of the classical critical group of its underlying graph by topological information, and it agrees with the classical critical group in the plane case. Its cardinality is equal to the number of spanning quasi-trees in a connected map, just as the cardinality of the classical critical group is equal to the number of spanning trees of a connected graph.
Our approach exploits the properties of principally unimodular matrices and the methods of delta-matroid theory.
Mathematics Subject Classifications: Primary 05C10, 05C25; Secondary 05C50, 05C57, 20K01, 91A43
Keywords: Chip-firing, critical group, embedded graph, sandpile group, sandpile model, Laplacian, map, Matrix–Tree Theorem, quasi-tree
- 1 supplemental ZIP
- Shortest paths on polymatroids and hypergraphic polytopes
Base polytopes of polymatroids, also known as generalized permutohedra, are polytopes whose edges are parallel to a vector of the form \(\mathbf{e}_i - \mathbf{e}_j\), where the \(\{\mathbf{e}_i\}_{i\in [n]}\) are the canonical basis vectors of \(\mathbb{R}^n\). We consider the following computational problem: Given two vertices of a generalized permutohedron \(P\), determine the length of a shortest path between them on the skeleton of \(P\), where the length of a path is its number of edges. This captures many known flip distance problems, such as computing the minimum number of exchanges between two spanning trees of a graph, the rotation distance between binary search trees, the flip distance between acyclic orientations of a graph, or rectangulations of a square. We prove that this general problem is \NP-hard, even when restricted to very simple polymatroids in \(\mathbb{R}^n\) defined by \(O(n)\) inequalities. Assuming \(\operatorname{P}\not= \operatorname{NP}\), this shows that even when maximizing a linear functional over a polymatroid, we cannot hope for the existence of a computationally efficient simplex pivoting rule that performs a minimum number of nondegenerate pivoting steps to an optimal solution. Such results have previously been shown only for other, arguably more complicated classes of polytopes. We also prove that the shortest path problem is inapproximable when the polymatroid is specified via an evaluation oracle for a corresponding submodular function, which strengthens a recent result by Ito, Kakimura, Kamiyama, Kobayashi, Maezawa, Nozaki, and Okamoto (ICALP'23). More precisely, we prove that it is \NP-hard to approximate the length of a shortest path to within a factor \((1+\varepsilon)\) for some absolute constant \(\varepsilon›0\), even when the polymatroid is a hypergraphic polytope, whose vertices are in bijection with acyclic orientations of a given hypergraph. The shortest path problem then amounts to computing the flip distance between two acyclic orientations of a hypergraph.
On the positive side, we provide a polynomial-time algorithm which, given any pair of acyclic orientations of a hypergraph, computes a connecting path whose length approximates the length of a shortest path to within a factor bounded by the maximum codegree of the hypergraph. Our result implies in particular an exact polynomial-time algorithm for computing shortest flip sequences between acyclic orientations of any linear hypergraph.
Mathematics Subject Classifications: 90C05, 90C08, 90C27, 90C35, 90C49, 90C57, 90C60, 05C50, 05C65, 05B35, 52B40
Keywords: Polymatroids, Generalized permutahedra, Hypergraphic polytopes, Simplex method, Shortest paths, Polytope diameter, Polytope skeleton, Flip distance, Combinatorial reconfiguration
- 1 supplemental ZIP
- A combinatorial skewing formula for the Rise Delta Theorem
We prove that the symmetric function \(\Delta'_{e_{k-1}}e_n\) appearing in the Delta Conjecture can be obtained from the symmetric function in the Rectangular Shuffle Theorem by applying a Schur skewing operator. This generalizes a formula by the first and third authors for the Delta Conjecture at \(t=0\), and follows from work of Blasiak, Haiman, Morse, Pun, and Seelinger. Our main result is that we also provide a purely combinatorial proof of this skewing identity, giving a new proof of the Rise Delta Theorem from the Rectangular Shuffle Theorem.
Mathematics Subject Classifications: 05E05
Keywords: Delta conjecture, parking functions, sign reversing involutions, skewing formula, Rectangular shuffle theorem, dinv, symmetric functions
- 1 supplemental ZIP
- On the determination of sets by their subset sums
Let \(A\) be a multiset with elements in an abelian group. Let \(\operatorname{FS}(A)\) be the multiset containing the \(2^{|A|}\) sums of all subsets of \(A\). We study the reconstruction problem "Given \(\operatorname{FS}(A)\), is it possible to identify \(A\)?". We prove that, up to identifying multisets through a natural equivalence relation, the function \(A \mapsto \operatorname{FS}(A)\) is injective (and thus the reconstruction problem is solvable) if and only if every order \(n\) of a torsion element of the abelian group satisfies a number-theoretical property related to the multiplicative group \((\mathbb{Z}/n \mathbb{Z})^*\). The core of the proof relies on a delicate study of the structure of cyclotomic units. Moreover, as a tool, we develop an inversion formula for a novel discrete Radon transform on finite abelian groups that might be of independent interest.
Mathematics Subject Classifications: 11P70, 05B10, 11R18, 44A12
Keywords: Subset sums, inverse problems, Radon transform, cyclotomic extension
- 1 supplemental ZIP
- Bounds on unique-neighbor codes
Recall that a binary linear code of length \(n\) is a linear subspace \(\mathcal{C} = \{x\in \mathbb{F}_2^n \mid Ax=0\}\). Here the parity check matrix \(A\) is a binary \(m\times n\) matrix of rank \(m\). We say that \(\mathcal{C}\) has rate \(R=1-\frac mn\). Its distance, denoted \(\delta n\) is the smallest Hamming weight of a non-zero vector in \(\mathcal{C}\). The rate vs. distance problem for binary linear codes is a fundamental open problem in coding theory, and a fascinating question in discrete mathematics. It concerns the function \(R_L(\delta)\), the largest possible rate \(R\) for given \(0\le\delta\le 1\) and arbitrarily large length \(n\). Here we investigate a variation of this fundamental question that we describe next. Clearly, \(\mathcal{C}\) has distance \(\delta n\), if and only if for every \(0‹n'‹\delta n\), every \(m\times n'\) submatrix of \(A\) has a row of odd weight. Motivated by several problems from coding theory, we say that \(A\) has the unique-neighbor property with parameter \(\delta n\), if every such submatrix has a row of weight \(1\). Let \(R_U(\delta)\) be the largest possible asymptotic rate of linear codes with a parity check matrix that has this stronger property. Clearly, \(R_U(\cdot), R_L(\cdot)\) are non-increasing functions, and \(R_U(\delta)\le R_L(\delta)\) for all \(\delta\). Also, \(R_U(0) = R_L(0) = 1\), and \({R_U(1) = R_L(1) = 0}\), so let \(0\le\delta_U \le\delta_L\le 1\) be the smallest values of \(\delta\) at which \(R_U\) resp. \(R_L\) vanish. It is well known that \(\delta_L=\frac{1}{2}\) and we conjecture that \(\delta_U\) is strictly smaller than \(\frac{1}{2}\), i.e., the rate of linear codes with the unique-neighbor property is more strictly bounded. While the conjecture remains open, we prove here several results supporting it. The reader is not assumed to have any specific background in coding theory, but we occasionally point out some relevant facts from that area.
Mathematics Subject Classifications: 05D99, 94B65
Keywords: Unique neighbor, linear code
- 1 supplemental ZIP
- Equivalences of biprojective almost perfect nonlinear functions
Two important problems on almost perfect nonlinear (APN) functions are the enumeration and equivalence problems. In this paper, we solve these two problems for any biprojective APN function family by introducing a group theoretic method for those functions. Roughly half of the known APN families of functions on even dimensions are biprojective. By our method, we settle the equivalence problem for all known biprojective APN functions. Furthermore, we give a new family of such functions. Using our method, we count the number of inequivalent APN functions in all known biprojective APN families and show that the new family found in this paper gives exponentially many new inequivalent APN functions. Quite recently, the Taniguchi family of APN functions was shown to contain an exponential number of inequivalent APN functions by Kaspers and Zhou (J. Cryptol. 34(1), 2021) which improved their previous count (J. Comb. Th. A 186, 2022) for the Zhou-Pott family. Our group theoretic method substantially simplifies the work required for proving those results and provides a generic natural method for every family in the large super-class of biprojective APN functions that contains these two family along with many others.
Mathematics Subject Classifications: 94A60, 06E30
Keywords: APN function, CCZ-equivalence, biprojective function
- 1 supplemental ZIP
- Harmonious sequences in groups with a unique involution
We study several combinatorial properties of finite groups that are related to the notions of sequenceability, R-sequenceability, and harmonious sequences. In particular, we show that in every abelian group \(G\) with a unique involution \(\imath_G\) there exists a permutation \(g_0,\ldots, g_{m}\) of elements of \(G \backslash \{\imath_G\}\) such that the consecutive sums \({g_0+g_1, g_1+g_2,\ldots, g_{m}+g_0}\) also form a permutation of elements of \(G\backslash \{\imath_G\}\). We also show that in every abelian group of order at least 4 there exists a sequence containing each non-identity element of \(G\) exactly twice such that the consecutive sums also contain each non-identity element of \(G\) twice. We apply several results to the existence of transversals in Latin squares.
Mathematics Subject Classifications: 05E16, 20D60, 05B15
Keywords: Sequenceable groups, Latin squares, harmonious groups, complete mappings
- 1 supplemental ZIP
- Piecewise-linear promotion and RSK in rectangles and moon polyominoes
We study piecewise-linear and birational lifts of Schützenberger promotion, evacuation, and the RSK correspondence defined in terms of toggles. Using this perspective, we prove that certain chain statistics in rectangles shift predictably under the action of these maps. We then use this to construct piecewise-linear and birational versions of Rubey's bijections between fillings of equivalent moon polyominoes that preserve these chain statistics, and we show that these maps form a commuting diagram. We also discuss how these results imply Ehrhart equivalence and Ehrhart quasi-polynomial period collapse of certain analogues of chain polytopes for moon polyominoes.
Mathematics Subject Classifications: 05E18, 05A05, 05A19, 52B05
Keywords: Birational rowmotion, Robinson-Schensted-Knuth correspondence, moon polyominoes, period collapse
- 1 supplemental ZIP
- The Newton polytope of the Kronecker product
We study the Kronecker product of two Schur functions \(s_\lambda\ast s_\mu\), defined as the image of the characteristic map of the product of two \(S_n\) irreducible characters. We prove special cases of a conjecture of Monical-Tokcan-Yong that its monomial expansion has a saturated Newton polytope. Our proofs employ the Horn inequalities for positivity of Littlewood-Richardson coefficients and imply necessary conditions for the positivity of Kronecker coefficients.
Mathematics Subject Classifications: 05E10, 20C30
Keywords: Kronecker coefficients, saturated Newton polytope, symmetric group representations
- 1 supplemental ZIP
- An explicit condition for boundedly supermultiplicative subshifts
We study some properties of the growth rate of \(\mathcal{L}(\mathcal{A},\mathcal{F})\), that is, the language of words over the alphabet \(\mathcal{A}\) avoiding the set of forbidden factors \(\mathcal{F}\). We first provide a sufficient condition on \(\mathcal{F}\) and \(\mathcal{A}\) for the growth of \(\mathcal{L}(\mathcal{A},\mathcal{F})\) to be boundedly supermultiplicative. That is, there exist constants \(C›0\) and \(\alpha\ge0\), such that for all \(n\), the number of words of length \(n\) in \(\mathcal{L}(\mathcal{A},\mathcal{F})\) is between \(\alpha^n\) and \(C\alpha^n\). In some settings, our condition provides a way to compute \(C\), which implies that \(\alpha\), the growth rate of the language, is also computable whenever our condition holds.
We also apply our technique to the specific setting of power-free words where the argument can be slightly refined to provide better bounds. Finally, we apply a similar idea to \(\mathcal{F}\)-free circular words and in particular we make progress toward a conjecture of Shur about the number of square-free circular words.
Mathematics Subject Classifications: 68R15
Keywords: Subshift, supermultiplicativity, growth of languages, circular word
- 1 supplemental ZIP
- Orthogonal webs and semisimplification
We define a diagrammatic category that is equivalent to tilting representations for the orthogonal group. Our construction works in characteristic not equal to two. We also describe the semisimplification of this category.
Mathematics Subject Classifications: Primary:18M05, 20G05; Secondary:18M30,~20J15
Keywords: Representations of linear algebraic groups, webs, Howe duality, diagrammatic presentation, positive characteristic, semisimplification
- 1 supplemental ZIP
- Boolean elements in the Bruhat order
We show that a Weyl group element is boolean if and only if it avoids a set of Billey-Postnikov patterns, which we describe explicitly. Our proof is based on analysis of inversion sets, and it is in large part type-uniform. We also introduce the notion of linear pattern avoidance, and show that boolean elements are characterized by avoiding just \(3\) linear patterns in types \(A_2\), \(A_3\), and \(D_4\), respectively.
We also consider the more general case of \(k\)-boolean Weyl group elements. We say that a Weyl group element \(w\) is \(k\)-boolean if every reduced expression for \(w\) contains at most \(k\) copies of each generator. We show that the \(2\)-boolean elements of the symmetric group are characterized by avoiding the patterns \(3421,4312,4321,\) and \(456123\), and obtain their generating function.
Mathematics Subject Classifications: 05A05, 20F55
Keywords: Boolean permutations, Bruhat orders, Billey-Postnikov patterns, Weyl groups
- 1 supplemental ZIP
- An upper bound on the per-tile entropy of ribbon tilings
This paper considers \(n\)-ribbon tilings of general regions and their per-tile entropy (the binary logarithm of the number of tilings divided by the number of tiles). We show that the per-tile entropy is bounded above by \(\log_2 n\). This bound improves the best previously known bounds of \(n-1\) for general regions, and the asymptotic upper bound of \(\log_2 (en)\) for growing rectangles, due to Chen and Kargin.
Mathematics Subject Classifications: 05B45, 52C20
Keywords: Ribbon tilings, domino tilings, dimer tilings
- 1 supplemental ZIP
- Equivalences of LLT polynomials via lattice paths
The LLT polynomials \(\mathcal{L}_{{{\beta}/{\gamma}}} (X;t)\) are a family of symmetric polynomials indexed by a tuple of (possibly skew-)partitions \({{\beta}/{\gamma}}= (\beta^{(1)}/\gamma^{(1)},\ldots,\beta^{(k)}/\gamma^{(k)})\). It has recently been shown that these polynomials can be seen as the partition function of a certain vertex model whose boundary condition is determined by \({{\beta}/{\gamma}}\). In this paper we describe an algorithm which gives a bijection between the configurations of the vertex model with boundary condition \({{\beta}/{\gamma}} = (\beta^{(1)}/\gamma^{(1)},\beta^{(2)}/\gamma^{(2)})\) and those with boundary condition \(({{\beta}/{\gamma}})_{swap} = (\beta^{(2)}/\gamma^{(2)},\beta^{(1)}/\gamma^{(1)})\). We prove a sufficient condition for when this bijection is weight-preserving up to an overall factor of \(t\), which in turn implies that the corresponding LLT polynomials are equal up to the same overall factor. Extending these techniques, we are able to systematically determine linear relations within families of LLT polynomials.Mathematics Subject Classifications: 05E05Keywords: LLT polynomials, vertex models
- 1 supplemental ZIP
- Improved stability for the size and structure of iterated sumsets in \(\mathbb{Z}^d\)
Let \(A \subset \mathbb{Z}^d\) be a finite set. It is known that the sumset \(NA\) has predictable size (\(\vert NA\vert = P_A(N)\) for some \(P_A(X) \in \mathbb{Q}[X]\)) and structure (all of the lattice points in some finite cone other than all of the lattice points in a finite collection of exceptional subcones), once \(N\) is larger than some threshold. In previous work, the first effective bounds for both of these thresholds were established, for an arbitrary set \(A\). In this article we substantially improve each of these bounds, coming much closer to the corresponding lower bounds known.
Mathematics Subject Classifications: 11P21, 05B10, 11B13, 11P70, 05A16
Keywords: Sumsets, Set addition, Khovanskii polynomial, Structure Theorem, Explicit Bounds
- 1 supplemental ZIP
- A degree bound for planar functions
Using Stickelberger's theorem on Gauss sums, we show that if \(F\) is a planar function on a finite field \(\mathbb{F}_q\), then for all non-zero functions \(G : \mathbb{F}_q \to \mathbb{F}_q\), we have \begin{equation*} d_{\mathsf{alg}}(G \circ F) - d_{\mathsf{alg}}(G) \le \frac{n(p-1)}{2}, \end{equation*} where \(q = p^n\) with \(p\) a prime and \(n\) a positive integer, and \(d_{\mathsf{alg}}(F)\) is the algebraic degree of \(F\), i.e., the maximum degree of the corresponding system of \(n\) lowest-degree interpolating polynomials for \(F\) considered as a function on \(\mathbb{F}_p^n\). This bound implies the (known) classification of planar polynomials over \(\mathbb{F}_p\) and planar monomials over \(\mathbb{F}_{p^2}\). As a new result, using the same degree bound, we complete the classification of planar monomials for all \(n = \smash{2^k}\) with \(p›5\) and \(k\) a non-negative integer. Finally, we state a conjecture on the sum of the base-\(p\) digits of integers modulo \(q-1\) that implies the complete classification of planar monomials over finite fields of characteristic \(p›5\).
Mathematics Subject Classifications: 05B25, 11T06, 11T24
Keywords: Planar function, algebraic degree, Stickelberger's theorem, digit sum
- 1 supplemental ZIP
- Cylindric \(P\)-tableaux for \((\mathbf{3}+\mathbf{1})\) -free posets
Tatsuyki Hikita recently proved the Stanley-Stembridge conjecture, showing that the \(e\)-coefficients of the chromatic symmetric function of an incomparability graph of a \((\mathbf{3}+\mathbf{1})\) -free poset are non-negative. It remains an open problem to find combinatorial interpretations of the \(e\)-coefficients. For a \((\mathbf{3}+\mathbf{1})\)-free \(P\), we define a hybrid of \(P\)-tableaux and cylindric tableaux called cylindric \(P\)-tableaux. The weight generating function of cylindric \(P\)-tableaux of shape \(\lambda/\mu/d\) are shown to be \(P\)-analogs of cylindric Schur functions defined by a determinantal formula. We deduce that certain sums of the \(e\)-expansion coefficients of the chromatic symmetric function \(X_{\operatorname{inc}(P)}\) are counted by the number of standard cylindric \(P\)-tableaux of the appropriate shape. We connect the \(P\)-analogs of symmetric functions to a theorem on Hecke algebra immanants due to Clearman-Hyatt-Shelton-Skandera.
Mathematics Subject Classifications: 05E05
Keywords: Symmetric Functions, \(e\)-Positivity
- 1 supplemental ZIP
- Dihedral tilings of the sphere by regular polygons and quadrilaterals I: squares and rhombi
We classify the edge-to-edge dihedral tilings of the sphere by squares and rhombi and develop a method that can be applied to future problems.
Mathematics Subject Classifications: 05B45, 52C20, 51M10, 51M20, 52B10
Keywords: Classification, spherical tilings, dihedral tilings, quadrangulations, division of spaces
- 1 supplemental ZIP