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 3, 2026
Research Articles
- Intersecting hypergraphs with large cover number
In their famous 1974 paper introducing the local lemma, Erdős and Lovász posed a question—later referred to by Erdős as one of his three favorite open problems: What is the minimum number of edges in an \( r \)-uniform, intersecting hypergraph with cover number \( r \)? This question was solved up to a constant factor in Kahn's remarkable 1994 paper. More recently, motivated by applications to Bollobás' "power of many colours" problem, Alon, Bucić, Christoph, and Krivelevich introduced a natural generalization by imposing a space constraint that limits the hypergraph to use only \(n\) vertices. In this note, we settle this question asymptotically, up to a logarithmic factor in \(n/r\) in the exponent, for the entire range.
Mathematics Subject Classifications: 05D05
Keywords: Hypergraphs, cover number, intersecting
- Partial permutations and character evaluations
Let \(I = (i_1, \dots, i_k)\) and \(J = (j_1, \dots, j_k)\) be two length \(k\) sequences drawn from \(\{1, \dots, n \}\). We have the group algebra element \([I,J] := \sum_{w(I) = J} w \in {\mathbb {C}}[{\mathfrak{S}}_n]\) where the sum is over permutations \(w \in {\mathfrak{S}}_n\) which satisfy \(w(i_p) = j_p\) for \(p = 1, \dots, k\). We give an algorithm for evaluating irreducible characters \(\chi^\lambda: {\mathbb {C}}[{\mathfrak{S}}_n] \to {\mathbb {C}}\) of the symmetric group on the elements \([I,J]\). This algorithm is a hybrid of the classical Murnaghan-Nakayama rule and a new path Murnaghan-Nakayama rule which reflects the decomposition of a partial permutation into paths and cycles.
These results first appeared in arXiv:2206.06567, which is no longer intended for publication. We originally used the character theoretic results in this paper to prove asymptotic results on moments of certain permutation statistics restricted to conjugacy classes. A referee generously shared a combinatorial argument which is strong enough to prove these results without recourse to character theory. These results now appear in our companion paper "Moments of permutation statistics by cycle type" (to appear in Forum Math. Sigma). However, the approach in this paper are more explicit, as we demonstrate with several examples.
Mathematics Subject Classifications: 05E05, 05E10
Keywords: Symmetric group, character, partial permutation
- Variations of \((\alpha,t)\)-Eulerian polynomials and their gamma positivity
In 1977, Carlitz and Scoville introduced the cycle \((\alpha,t)\)-Eulerian polynomials \(A^{\mathrm{cyc}}_n(x,y,t \mid \alpha)\) by enumerating permutations with respect to the number of excedances, drops, fixed points, and cycles. In this paper, we propose a nine-variable generalization of the Eulerian polynomials \(A_n(u_1,u_2,u_3,u_4,f,g,t \mid \alpha,\beta)\) defined in terms of descent-based statistics of permutations, and we establish a connection formula linking these two families of generalized Eulerian polynomials. By means of this connection formula, we derive explicit exponential generating functions and several \(\gamma\)-positive expressions for various Eulerian-type polynomials. In particular, our results unify and strengthen recent findings of Ji and Ji-Lin. In related work on the transition matrix between the Specht and web bases, Hwang, Jang, and Oh recently introduced the web permutations, which can be described in terms of cycle André permutations. We show that enumerating these permutations with respect to the numbers of drops, fixed points, and cycles yields the normalized \(\gamma\)-vectors of the \((\alpha,t)\)-Eulerian polynomials. Our results thus provide a unified framework encompassing and extending several known results in the literature.
Mathematics Subject Classifications: 05A05, 05A15, 05A19
Keywords: \((\alpha,t)\)-Eulerian polynomials, left-to-right maxima, cycle André permutations, cyclic valley-hopping, gamma-positivity
- Symmetric noncrossing partitions of an annulus with double points
For affine Coxeter groups of affine types \(\widetilde{\text{D}}\) and \(\widetilde{\text{B}}\), we model the interval \([1,c]_T\) in the absolute order by symmetric noncrossing partitions of an annulus with one or two double points. In type \(\widetilde{\text{B}}\) (and almost in type \(\widetilde{\text{D}}\)), the diagrams also model the larger lattice defined by McCammond and Sulway.
Mathematics Subject Classifications: Primary: 20F55, 05E16; Secondary: 20F36
Keywords: Absolute order, affine Coxeter group, marked surface, noncrossing partition
- Embedded metasymplectic spaces of type \(\mathsf{F_{4,4}}\)
We determine the generating and embedding rank of the metasymplectic spaces whose symplecta are either symplectic polar spaces in characteristic distinct from \(2\), or Hermitian polar spaces (including the quaternion case), and provide a characterisation of the associated projective varieties in the context of the Freudenthal-Tits magic square.
Mathematics Subject Classifications: 51E24, 51B25, 20E42
Keywords: Metasymplectic space, embedding, Freudenthal-Tits magic square
- Realizing resolutions of powers of extremal ideals
Extremal ideals are a class of square-free monomial ideals which dominate and determine many algebraic invariants of powers of all square-free monomial ideals. For example, the \(r^{th}\) power \({\mathcal{E}_q}^r\) of the extremal ideal on \(q\) generators has the maximum betti numbers among the \(r^{th}\) power of any square-free monomial ideal with \(q\) generators. In this paper we study the combinatorial and geometric structure of the (minimal) free resolutions of powers of square-free monomial ideals via the resolutions of powers of extremal ideals. Although the end results are algebraic, this problem has a natural interpretation in terms of polytopes and discrete geometry. Our guiding conjecture is that all powers \({\mathcal{E}_q}^r\) of extremal ideals have resolutions supported on their Scarf simplicial complexes, and thus their resolutions are as small as possible. This conjecture is known to hold for \(r \leq 2\) or \(q \leq 4\). In this paper we prove the conjecture holds for \(r=3\) and any \(q\geq 1\) by giving a complete description of the Scarf complex of \({\mathcal{E}_q}^3\). This effectively gives us a sharp bound on the betti numbers and projective dimension of the third power of any square-free monomial ideal. For large \(i\) and \(q\), our bounds on the \(i^{th}\) betti numbers are an exponential improvement over previously known bounds. We also describe a large number of faces of the Scarf complex of \({\mathcal{E}_q}^r\) for any \(r,q \geq 1\).
Mathematics Subject Classifications: 13D02, 13F55, 05E40, 52B20
Keywords: Free resolutions, bounds on Betti numbers, extremal ideals, monomial ideals, powers of ideals, Scarf complex, discrete Morse theory
- Strongly regular graphs with generalized Denniston and dual generalized Denniston parameters
We construct two families of strongly regular Cayley graphs, or equivalently, partial difference sets, based on elementary abelian groups. The parameters of these two families are generalizations of the Denniston and the dual Denniston parameters, in contrast to the well-known Latin square type and negative Latin square type parameters. The two families unify and subsume a number of existing constructions which have been presented in various contexts such as strongly regular graphs, partial difference sets, projective sets, and projective two-weight codes, notably including Denniston's seminal construction concerning maximal arcs in classical projective planes with even order. Our construction generates further momentum in this area, which recently saw exciting progress on the construction of the analogue of the famous Denniston partial difference sets in odd characteristic.
Mathematics Subject Classifications: 05E30, 05B10, 11T24, 51E20, 94B05
Keywords: Cyclotomy, Gauss sum, partial difference set, projective set, projective two-weight code, strongly regular Cayley graph
- Ramsey's witnesses
We introduce the notion of Ramsey partition regularity, a generalisation of partition regularity involving infinitary configurations. We provide characterisations of this notion in terms of certain ultrafilters related to tensor products and dubbed Ramsey's witnesses; and we also consider their nonstandard counterparts as pairs of hypernatural numbers, called Ramsey pairs. These characterisations are then used to determine whether various configurations involving polynomials and exponentials are Ramsey partition regular over the natural numbers. In particular, this provides negative answers to several questions recently posed by Kra, Moreira, Richter and Robertson.
Mathematics Subject Classifications: Primary: 05D10. Secondary: 26E35, 03H15, 11U10, 05A17, 54D80
Keywords: Arithmetic Ramsey theory, partition regularity, ultrafilter, nonstandard analysis, tensor pair, Ramsey's witness
- Splicing skew shaped positroids
Skew shaped positroids (or skew shaped positroid varieties) are certain Richardson varieties in the flag variety that admit a realization as explicit subvarieties of the Grassmannian \(\mathrm{Gr}(k,n)\). They are parametrized by a pair of Young diagrams \(\mu \subseteq \lambda\) fitting inside a \(k \times (n-k)\)-rectangle. For every \(a = 1, \dots, n-k\), we define an explicit open set \(U_a\) inside the skew shaped positroid \(S^{\circ}_{\lambda/\mu}\), and show that \(U_a\) is isomorphic to the product of two smaller skew shaped positroids. Moreover, \(U_a\) admits a natural cluster structure and the aforementioned isomorphism is quasi-cluster isomorphism in the sense of Fraser. Our methods depend on realizing the skew shaped positroid as an explicit braid variety, and generalize the work of the first and third authors for open positroid cells in the Grassmannian.
Mathematics Subject Classifications: 13F60, 14M15
Keywords: Cluster algebras, positroid varieties
- Super Markov numbers and signed double dimer covers
We provide a superalgebraic analogue of Markov numbers, which are defined as the Grassmann integer solutions to the equation \(x^2 + y^2 + z^2 + (xy + yz + xz)\epsilon = 3(1+\epsilon)xyz\), as well as applications to the decorated super Teichmüller spaces associated to the once-punctured torus and certain annuli. We conclude with further directions for study.
Mathematics Subject Classifications: 13F60, 17A70, 30F60, 11D25, 05C70
Keywords: Markov numbers, Super Teichmüller space, snake graphs, double dimer covers
- Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
We prove that for any graph \(G\) the (complex) zeros of its chromatic polynomial, \(\chi_G(x)\), lie inside the disk centered at \(0\) of radius \(4.25 \Delta(G)\), where \(\Delta(G)\) denotes the maximum degree of \(G\). This improves on a recent result of Jenssen, Patel and Regts, who proved a bound of \(5.94\Delta(G)\). Moreover, we show that for graphs of sufficiently large girth we can replace \(4.25\) by \(3.60\) and for claw-free graphs we can replace \(4.25\) by \(3.81\).
Our proofs add some substantially novel ideas to those developed by Jenssen, Patel, and Regts, while building on them. A key novel ingredient for claw-free graphs is to use a representation of the coefficients of the chromatic polynomial in terms of the number of certain partial acyclic orientations.
Mathematics Subject Classifications: 05C31, 68W25
Keywords: Chromatic polynomial, acyclic orientation, complex zeros, broken circuit, maximum degree, claw-free graphs
- Properties of LCM lattices of monomial ideals
LCM lattices were introduced by Gasharov, Peeva, and Welker as a way to study minimal free resolutions of monomial ideals. All LCM lattices are atomic and all atomic lattices arise as the LCM lattice of some monomial ideal. We systematically study other lattice properties of LCM lattices. For lattices associated to the edge ideal of a graph, we completely characterize the many standard lattice properties in terms of the associated graphs: Boolean, modular, upper semimodular, lower semimodular, supersolvable, coatomic, and complemented; edge ideals with graded LCM lattices were previously characterized by Nevo and Peeva as those associated to gap-free graphs. For arbitrary monomial ideals, we prove the Cohen-Macaulayness of minimal monomial ideals associated to modular lattices. We also prove separate necessary and sufficient lattice conditions for when the projective dimension of a monomial ideal matches the height of its LCM lattice. Finally, we show that LCM lattices of Gorenstein edge ideals are coatomic and raise questions about the lattice properties of arbitrary Gorenstein monomial ideals.
Mathematics Subject Classifications: Primary: 06B10, 13F55; Secondary: 06C05, 13D02, 13C70, 05E40
Keywords: Monomial ideal, free resolution, LCM lattice, Cohen-Macaulay ring, edge ideal, projective dimension
- Framing triangulations and framing posets of planar DAGs with nontrivial netflow vectors
The polyhedron of unit flows on a directed acyclic graph (DAG) with one source and one sink is known to admit regular unimodular triangulations induced by framings of the DAG. The dual graph of any of these triangulations may be given the structure of the Hasse diagram of a lattice, generalizing many variations of the Tamari lattice and the weak order. We extend this theory to flow polytopes of DAGs which may have multiple sources, multiple sinks, and nontrivial netflow vectors under certain planarity conditions. We construct a unimodular triangulation of such a flow polytope indexed by combinatorial data and give a poset structure on its maximal simplices generalizing the strongly planar one-source-one-sink case.
Mathematics Subject Classifications: 05C21, 05E45, 52B11
Keywords: Framing triangulations, flow polytopes
- Interpreting the (signed) chromatic polynomial coefficients via hyperplane arrangements
A recent result of Lofano and Paolini expresses the characteristic polynomial of a real hyperplane arrangement in terms of a projection statistic on the regions of the arrangement. We use this result to give an alternative proof for Greene and Zaslavsky's interpretation for the coefficients of the chromatic polynomial of a graph and further generalize this interpretation to signed graphs. We also show that this projection statistic has a nice combinatorial interpretation in the case of the braid arrangement, which generalizes to graphical arrangements of natural unit interval graphs.
Mathematics Subject Classifications: 52C35, 05A15, 05C15, 05C22
Keywords: Hyperplane arrangements, chromatic polynomials, signed graphs
- Graphs with large minimum degree and no short odd cycles are \(3\)-colourable
Answering a question by Letzter and Snyder, we prove that for large enough \(k\), any \(n\)-vertex graph \(G\) with minimum degree at least \(\frac{1}{2k-1}n\) and without odd cycles of length less than \(2k+1\) is \(3\)-colourable. In fact, we prove a stronger result that works with a slightly smaller minimum degree.
Mathematics Subject Classifications: 05C35, 05C15
Keywords: Chromatic profile, Minimum degree, Graph colouring
- Enumeration of planar bipartite tight irreducible maps
We consider planar bipartite maps which are both tight, i.e. without vertices of degree \(1\), and \(2b\)-irreducible, i.e. such that each cycle has length at least \(2b\) and such that any cycle of length exactly \(2b\) is the contour of a face. It was shown by Budd that the number \(\mathcal N_n^{(b)}\) of such maps made out of a fixed set of \(n\) faces with prescribed even degrees is a polynomial in both \(b\) and the face degrees. In this paper, we give an explicit expression for \(\mathcal N_n^{(b)}\) by a direct bijective approach based on the so-called slice decomposition. More precisely, we decompose any of the maps at hand into a collection of \(2b\)-irreducible tight slices and a suitable two-face map. We show how to bijectively encode each \(2b\)-irreducible slice via a \(b\)-decorated tree drawn on its derived map, and how to enumerate collections thereof. We then discuss the polynomial counting of two-face maps, and show how to combine it with the former enumeration to obtain \(\mathcal N_n^{(b)}\).
Mathematics Subject Classifications: 05A15, 05A19
Keywords: Planar maps, bijective enumeration, slice decomposition
- Smaller universal poset
We show that there is a constant \(C›0\) such that for each integer \(n\geq 1\), there is a poset on at most \(2^{2n/3+C\sqrt{n}}\) elements that contains each \(n\)-element poset as an (induced) subposet.
Mathematics Subject Classifications: 06A07, 06A06
Keywords: Universal Structure, Poset