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 4, 2025
Research Articles
- Subsets of free groups with distinct differences
Let \(F_n\) be a free group of rank \(n\), with free generating set \(X\). A subset \(D\) of \(F_n\) is a Distinct Difference Configuration if the differences \(g^{-1}h\) are distinct, where \(g\) and \(h\) range over all (ordered) pairs of distinct elements of \(D\). The subset \(D\) has diameter at most \(d\) if these differences all have word length at most \(d\). When \(n\) is fixed and \(d\) is large, the paper shows that the largest distinct difference configuration in \(F_n\) of diameter at most \(d\) has size approximately \((2n-1)^{d/3}\).
Mathematics Subject Classifications: 05B10, 20E05
Keywords: Difference sets, distinct difference configurations, free groups, combinatorial designs
- 1 supplemental ZIP
- An extension theorem for signotopes
In 1926, Levi showed that, for every pseudoline arrangement \(\mathcal{A}\) and two points in the plane, \(\mathcal{A}\) can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in \(\mathbb{R}^d\) with a hyperplane containing \(d\) prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in \(\mathbb{R}^3\) which cannot be extended with a pseudoplane containing two particular prescribed points. In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks \(r \geq 4\) there exist signotopes that are not extendable for two prescribed points. Our conjecture is supported by examples in ranks \(4\), \(6\), \(8\), \(10\), and \(12\) that were found with a SAT-based approach.
Mathematics Subject Classifications: 68R05, 51H99
Keywords: Arrangement of pseudolines, extendability, Levi's extension lemma, arrangement of pseudohyperplanes, signotope, oriented matroid, partial order, Boolean satisfiability (SAT)
- 1 supplemental ZIP
- On the face stratification of the \(m=2\) amplituhedron
We define and study the face stratification of the \(m=2\) amplituhedron. We show that the face poset is an upper order ideal in the face poset of the totally nonnegative Grassmannian. Our construction is consistent with earlier work of Lukowski, and we confirm various predictions of Lukowski.
Mathematics Subject Classifications: 05E14, 52B40
Keywords: Total positivity, amplituhedron, Grassmannian
- 1 supplemental ZIP
- The Ehrhart \(h^\ast\)-polynomials of positroid polytopes
A positroid is a matroid realized by a matrix such that all maximal minors are non-negative. Positroid polytopes are matroid polytopes of positroids. In particular, they are lattice polytopes. The Ehrhart polynomial of a lattice polytope counts the number of integer points in the dilation of that polytope. The Ehrhart series is the generating function of the Ehrhart polynomial, which is a rational function with the numerator called the \(h^\ast\)-polynomial. We compute the \(h^\ast\)-polynomials of an arbitrary positroid polytope by a family of shelling orders of it. We also compute the \(h^\ast\)-polynomial of any positroid polytope with some facets removed and we relate it to the descents of permutations. Our result generalizes that of Early, Kim, and Li for hypersimplices.
Mathematics Subject Classifications: 05B35
Keywords: Positroid, Ehrhart theory
- 1 supplemental ZIP
- Periodic colorings and orientations in infinite graphs
We study the existence of periodic colorings and orientations in locally finite graphs. A coloring or orientation of a graph \(G\) is periodic if the resulting colored or oriented graph is quasi-transitive, meaning that \(V(G)\) has finitely many orbits under the action of the group of automorphisms of \(G\) preserving the coloring or the orientation. When such a periodic coloring or orientation of \(G\) exists, \(G\) itself must be quasi-transitive and it is natural to investigate when quasi-transitive graphs have such periodic colorings or orientations. We provide examples of Cayley graphs with no periodic orientation or non-trivial coloring, and examples of quasi-transitive graphs of treewidth 2 without periodic orientation or proper coloring. On the other hand we show that every quasi-transitive graph \(G\) of bounded pathwidth has a periodic proper coloring with \(\chi(G)\) colors and a periodic orientation. We relate these problems with techniques and questions from symbolic dynamics and distributed computing and conclude with a number of open problems.
Mathematics Subject Classifications: 05C15, 05C25, 20F65
Keywords: Quasi-transitive graphs, periodic colorings, simple groups
- 1 supplemental ZIP
- Skeletal generalizations of chip-firing games, parking functions, and Dyck paths
For \(0\leq k\leq n-1\), we introduce a family of \(k\)-skeletal paths which are counted by the \(n\)th Catalan number for each \(k\), and specialize to Dyck paths when \(k=n-1\). We similarly introduce \(k\)-skeletal parking functions which are equinumerous with spanning trees on the complete graph with \(n+1\) vertices for each \(k\), and specialize to classical parking functions for \(k=n-1\). The preceding constructions are generalized to paths lying in a trapezoid with base \(c › 0\) and southeastern diagonal of slope \(1/m\); \(c\) and \(m\) need not be integers. We give bijections among these families when \(k\) varies with \(m\) and \(c\) fixed. Our constructions are motivated by chip firing and have connections to combinatorial representation theory and tropical geometry.
Mathematics Subject Classifications: 05A15, 05A19, 05C57
Keywords: Chip firing, skeletal objects, lattice paths, Dyck paths, parking functions, Catalan numbers, ballot numbers
- 1 supplemental ZIP
- Canonical theorems in geometric Ramsey theory
In Euclidean Ramsey Theory usually we are looking for monochromatic configurations in the Euclidean space, whose points are colored with a fixed number of colors. In the canonical version, the number of colors is arbitrary, and we are looking for an `unavoidable' set of colorings of a finite configuration, that is, a set of colorings with the property that one of them always appears in any coloring of the space. This set definitely includes the monochromatic and the rainbow colorings. In the present paper, we prove the following two results of this type. First, for any acute triangle \(T\), and any coloring of \(\mathbb{R}^3\), there is either a monochromatic or a rainbow copy of \(T\). Second, for every \(m\), there exists a sufficiently large \(n\) such that in any coloring of \(\mathbb{R}^n\), there exists either a monochromatic or a rainbow \(m\)-dimensional unit hypercube. In the maximum norm, \(\ell_{\infty}\), we have a much stronger statement. For every finite \(M\), there exits an \(n\) such that in any coloring of \(\mathbb{R}_\infty^n\), there is either a monochromatic or a rainbow isometric copy of \(M\).
Mathematics Subject Classifications: 05D10, 05C55
Keywords: Euclidean Ramsey theory, canonical Ramsey theorem, colorings of the space
- 1 supplemental ZIP
- A tower lower bound for the degree relaxation of the Regularity Lemma
It is well-known that if \((A,B)\) is an \(\tfrac{\varepsilon}{2}\)-regular pair (in the sense of Szemerédi) then there exist sets \(A'\subset A\) and \(B'\subset B\) with \(|A'|\le \varepsilon|A|\) and \(|B'|\le \varepsilon|B|\) so that the degrees of all vertices in \(A\setminus A'\) differ by at most \(\varepsilon|B|\) and the degrees of all vertices in \(B\setminus B'\) differ by at most \(\varepsilon|A|\). We call such a property \(\varepsilon\)-degularity. This leads to the notion of an \(\varepsilon\)-degular partition of a graph in the same way as the definition of \(\varepsilon\)-regular pairs leads to the notion of \(\varepsilon\)-regular partitions.
We show that there exist graphs in which any \(\varepsilon\)-degular partition requires the number of clusters to be \(\mathrm{tower}(\Theta(\varepsilon^{-1/3}))\). That is, even though degularity is a substantial relaxation of regularity, in general one cannot improve much on the bounds that come with Szemerédi's regularity lemma.
Mathematics Subject Classifications: 05C35
Keywords: Szemerédi's regularity lemma, degree
- 1 supplemental ZIP
- On a question of Gowers on clique differences
We solve a question of Gowers from 2009 on clique differences in chains, thus ruling out any Sperner-type proof of the polynomial density Hales-Jewett Theorem for alphabets of size 2.
Mathematics Subject Classifications: 05D10
Keywords: Hales-Jewett, Polynomial Hales-Jewett, Ramsey Theory
- 1 supplemental ZIP
- Sidorenko hypergraphs and random Turán numbers
Let \(\mathrm{ex}(G_{n,p}^r,F)\) denote the maximum number of edges in an \(F\)-free subgraph of the random \(r\)-uniform hypergraph \(G_{n,p}^r\), and let \[s(F):=\sup\{s: \exists H, t_F(H)=t_{K_r^r}(H)^{s+e(F)}›0\}.\] Following recent work of Conlon, Lee, and Sidorenko, we prove non-trivial lower bounds on \(\mathrm{ex}(G_{n,p}^r,F)\) whenever \(s(F)›0\), i.e. \(F\) is not Sidorenko. This connection between Sidorenko's conjecture and random Turán problems gives new lower bounds on \(\mathrm{ex}(G_{n,p}^r,F)\) whenever \(s(F)›0\), and further allows us to establish upper bounds for \(s(F)\) whenever upper bounds for \(\mathrm{ex}(G_{n,p}^r,F)\) are known. As a consequence, we prove that \(s(\mathrm{E}^r(K_{k+1}^k))=\frac{1}{r-k}\) where \(\mathrm{E}^r(K_{k+1}^k)\) is the \(r\)-expansion of \(K_{k+1}^k\).
Mathematics Subject Classifications: 05C65, 05C80, 05D05, 05D40
Keywords: Hypergraph, Sidorenko Conjecture, Random Turán Problem
- 1 supplemental ZIP
- Diagonal operators, \(q\)-Whittaker functions and rook theory
We discuss the problem posed by Bender, Coley, Robbins and Rumsey of enumerating the number of subspaces which have a given profile with respect to a linear operator over the finite field \(\mathbb{F}_q\). We solve this problem in the case where the operator is diagonalizable. The solution leads us to a new class of polynomials \(b_{\mu\nu}(q)\) indexed by pairs of integer partitions. These polynomials have several interesting specializations and can be expressed as positive sums over semistandard tableaux. We present a new correspondence between set partitions and semistandard tableaux. A close analysis of this correspondence reveals the existence of several new set partition statistics which generate the polynomials \(b_{\mu\nu}(q)\); each such statistic arises from a Mahonian statistic on multiset permutations. The polynomials \(b_{\mu\nu}(q)\) are also given a description in terms of coefficients in the monomial expansion of \(q\)-Whittaker symmetric functions which are specializations of Macdonald polynomials. We express the Touchard-Riordan generating polynomial for chord diagrams by number of crossings in terms of \(q\)-Whittaker functions. We also introduce a class of \(q\)-Stirling numbers defined in terms of the polynomials \(b_{\mu\nu}(q)\) and present connections with \(q\)-rook theory in the spirit of Garsia and Remmel.
Mathematics Subject Classifications: 15B33, 05A15, 05A18, 05A05, 05E05, 11B65
Keywords: Diagonal matrix, finite field, semistandard tableau, Mahonian statistic, \(q\)-Whittaker function, chord diagram, Touchard-Riordan formula, \(q\)-Stirling number, \(q\)-rook theory
- 1 supplemental ZIP
- The foundation of generalized parallel connections, 2-sums, and segment-cosegment exchanges of matroids
We show that, under suitable hypotheses, the foundation of a generalized parallel connection of matroids is the relative tensor product of the foundations. Using this result, we show that the foundation of a 2-sum of matroids is the absolute tensor product of the foundations, and that the foundation of a matroid is invariant under segment-cosegment exchange.
Mathematics Subject Classifications: 05B35, 20Axx
Keywords: Matroids, pastures, foundations, generalized parallel connection, 2-sum, segment-cosegment exchange
- 1 supplemental ZIP
- Some enumerative properties of parking functions
A parking function is a sequence \((\pi_1,\dots, \pi_n)\) of positive integers such that if \(\lambda_1\leq\cdots\leq \lambda_n\) is the increasing rearrangement of \(\pi_1,\dots,\pi_n\), then \(\lambda_i\leq i\) for \(1\leq i\leq n\). In this paper we obtain some new results on the enumeration of parking functions. We will consider the joint distribution of several sets of statistics on parking functions. The distribution of most of these individual statistics is known, but the joint distributions are new. Parking functions of length \(n\) are in bijection with labelled forests on the vertex set \([n]=\{1,2,\dots,n\}\) (or rooted trees on \([n]_0=\{0,1,\dots,n\}\) with root \(0\)), so our results can also be applied to labelled forests. Extensions of our techniques are discussed, including an extension to a probabilistic scenario.
Mathematics Subject Classifications: 05A15, 60C05, 05A19
Keywords: Parking function, labelled forest, generating function, recurrence, Pollak's circle argument
- 1 supplemental ZIP
- Ryser's Theorem for symmetric \(\rho\)-latin squares
Let \(L\) be an \(n\times n\) array whose top left \(r\times r\) subarray is filled with \(k\) different symbols, each occurring at most once in each row and at most once in each column. We establish necessary and sufficient conditions that ensure the remaining cells of \(L\) can be filled such that each symbol occurs at most once in each row and at most once in each column, \(L\) is symmetric with respect to the main diagonal, and each symbol occurs a prescribed number of times in \(L\). The case where the prescribed number of times each symbol occurs is \(n\) was solved by Cruse (J. Combin. Theory Ser. A 16 (1974), 18-22), and the case where the top left subarray is \(r\times n\) and the symmetry is not required, was settled by Goldwasser et al. (J. Combin. Theory Ser. A 130 (2015), 26-41). Our result allows the entries of the main diagonal to be specified as well, which leads to an extension of the Andersen-Hoffman Theorem (Annals of Disc. Math. 15 (1982) 9-26, European J. Combin. 4 (1983) 33-35).
Mathematics Subject Classifications: 05B15, 05C70, 05C15
Keywords: Latin square, embedding, \((g,f)\)-factors, Cruse's Theorem, Andersen-Hoffman's Theorem, Ryser's Theorem, amalgamation, detachment
- 1 supplemental ZIP
- Labeling regions in deformations of graphical arrangements
Combining Carver's variant of the Farkas' lemma with the Flow Decomposition Theorem we show that the regions of any deformation of a graphical arrangement may be bijectively labeled with a set of weighted digraphs containing directed cycles of negative weight only. Bounded regions correspond to strongly connected digraphs. The study of the resulting labelings allows us to add the omitted details in Stanley's proof on the injectivity of the Pak-Stanley labeling of the regions of the extended Shi arrangement, to generalize the ceiling diagrams in the deleted Shi and Ish arrangements studied by Armstrong and Rhoades and to introduce a new labeling of the regions in the Fuss-Catalan arrangement. We also point out that Athanasiadis-Linusson labelings may be used to directly count regions in a class of arrangements properly containing the extended Shi arrangement and the Fuss-Catalan arrangement.
Mathematics Subject Classifications: 52C35, 05A10, 05A15, 11B83
Keywords: Farkas' lemma, graphical arrangement, braid arrangement, Shi arrangement, Linial arrangement, semi-acyclic tournament
- 1 supplemental ZIP
- Poset polytopes and pipe dreams: types C and B
The first part of this paper concerns type C. We present new explicitly defined families of algebro-combinatorial structures of three kinds: combinatorial bases in representations, Newton-Okounkov bodies of flag varieties and toric degenerations of flag varieties. All three families are parametrized by the same family of polytopes: the marked chain-order polytopes of Fang and Fourier which interpolate between the type C Gelfand-Tsetlin and FFLV polytopes. Thus, in each case the obtained structures interpolate between the well-known bases, Newton-Okounkov bodies or degenerations associated with the latter two polytopes. We then obtain similar results for type B after introducing a new family of poset polytopes to be considered in place of marked chain-order polytopes. In both types our constructions and proofs rely crucially on a combinatorial connection between poset polytopes and pipe dreams.
Mathematics Subject Classifications: 14M15, 17B10, 05E14, 05E10, 52B20, 06A11
Keywords: Flag varieties, poset polytopes, pipe dreams, toric degenerations, Newton– Okounkov bodies
- 1 supplemental ZIP