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 2, 2026
Research Articles
- Triple exponential bounds for monochromatic sums equal to products
We show that any \(r\)-coloring of \(\{1,\dots,r^{r^{r^{2r}}}\}\) contains monochromatic sets \(\{a,b,a+b,x,y,xy\}\) with \(a+b=xy.\)
Mathematics Subject Classifications: 05D10
Keywords: Ramsey, sums equal to products
- Constructions of \(t\)-designs from weighing matrices and association schemes
We provide a method to construct \(t\)-designs from weighing matrices and association schemes. One instance of our method can produce a \(3\)-design from any (symmetric or skew-symmetric) conference matrix, thereby providing a partial answer to a question of Gunderson and Semeraro JCTB 2017. We explore variations of our method on some matrices that satisfy certain combinatorial restrictions. In particular, we show that there exist various infinite families of partially balanced incomplete block designs with block size four on the binary Hamming schemes and the \(3\)-class association schemes attached to symmetric designs, and regular pairwise balanced designs with block sizes three and four.
Mathematics Subject Classifications: 05B05, 05C50, 05E30
Keywords: \(t\)-design, characteristic polynomial, weighing matrix, Hadamard matrix, association scheme
- Marked bumpless pipedreams and compatible pairs
We construct a bijection between marked bumpless pipedreams with reverse compatible pairs, which are in bijection with not-necessarily-reduced pipedreams. This directly unifies various formulas for Grothendieck polynomials in the literature. Our bijection is a generalization of a variant of the bijection of Gao and Huang in the unmarked, reduced case.
Mathematics Subject Classifications: 05E05
Keywords: Bumpless pipedreams, Grothendieck polynomials
- Galoisian structure of large steps walks in the quadrant
The enumeration of walks confined to the first quadrant has attracted a lot of attention over the past fifteen years. The generating functions associated to small steps models satisfy a functional equation in two catalytic variables. For such models, Bousquet-Mélou and Mishna defined a group called the group of the walk which turned out to be central in the classification of small steps models. In particular, its action on the catalytic variables yields a set of change of variables compatible with the structure of the functional equation. This particular set called the orbit has been generalized to models with arbitrarily large steps by Bostan, Bousquet-Mélou and Melczer. However, the orbit had till now no underlying group.
In this article, we endow the orbit with the action of a Galois group, which extends the group of the walk to models with large steps. Within this Galoisian framework, we generalize the notions of invariants and decoupling. This enables us to develop a general strategy to prove the algebraicity of models with small backward steps. Our constructions lead to the first proofs of algebraicity of weighted models with large steps, proving in particular a conjecture of Bostan, Bousquet-Mélou and Melczer, and allowing us to find new algebraic models with large steps.
Mathematics Subject Classifications: 05A15, 11S20, 34K06, 39A06
Keywords: Galois theory, Enumeration, Quadrant walks, Catalytic variable equations
- Towards plethystic \(\mathfrak{sl}_2\) crystals
To find crystals of \(\mathfrak{sl}_2\) representations of the form \(\Lambda^n\operatorname{Sym}^r\mathbb{C}^2\) it suffices to solve the combinatorial problem of decomposing the Young lattice into symmetric, saturated chains. We review the literature on this latter problem, and present a strategy to solve it. For \(n \le 4\), the strategy recovers recently discovered solutions. We obtain (i) counting formulas for plethystic coefficients, (ii) new recursive formulas for plethysms of Schur functions, and (iii) formulas for the number of constituents of \(\Lambda^n\operatorname{Sym}^r\mathbb{C}^2\).
Mathematics Subject Classifications: 05E10, 17B10, 05A30
Keywords: Plethysm, crystals, symmetric chain decompositions, Young lattice, Gaussian coefficients
- Complexity measures on the symmetric group and beyond
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a few others. We show that these complexity measures are polynomially related for the symmetric group and for many other domains.
To show that all measures but sensitivity are polynomially related, we generalize classical arguments of Nisan and others. To add sensitivity to the mix, we reduce to Huang's sensitivity theorem using "pseudo-characters", which witness the degree of a function.
Using similar ideas, we extend the characterization of Boolean degree 1 functions on the symmetric group due to Ellis, Friedgut and Pilpel to the perfect matching scheme. As another application of our ideas, we simplify the characterization of maximum-size \(t\)-intersecting families in the symmetric group and the perfect matching scheme.
Mathematics Subject Classifications: 06E30, 94D10
Keywords: Boolean functions, complexity measures
- The overflow in the Katona Theorem
Let \(n›2r›0\) be integers. We consider families \(\mathcal{F}\) of subsets of an \(n\)-element set, in which the union of any two members has size at most \(2r\). One of our results states that for \(n\geq 8r\) the number of members of size exceeding \(r\) in \(\mathcal{F}\) is at most \(\binom{n-2}{r-1}\). Another result shows that for \(n›3.5r\) the number of sets of size at least \(r\) is at most \(\binom{n}{r}\). Both bounds are best possible and the latter sharpens the classical Katona Theorem. Similar results are proved for the odd case of the Katona Theorem as well.
Mathematics Subject Classifications: 05D05
Keywords: The Katona theorem, overflow, shifting, the random walk method
- Determinantal random subgraphs
We define two families of determinantal random spanning subgraphs of a finite connected graph, one supported by acyclic spanning subgraphs (spanning forests) with fixed number of connected components, the other by connected spanning subgraphs with fixed number of independent cycles. Each family generalizes the uniform spanning tree and the generating functions of these probability measures generalize the classical Kirchhoff and Symanzik polynomials.
We call Symanzik spanning forests the elements of the acyclic spanning subgraphs family, and single out a particular determinantal mixture of these, having as kernel a normalized Laplacian on \(1\)-forms, which we call the Laplacian spanning forest.
Our proofs rely on a set of integral and real or complex (which we call geometric) multilinear identies involving cycles, coboundaries, and forests on graphs. We prove these identities using classical pieces of the algebraic topology of graphs and the exterior calculus applied to finite determinantal point processes, both of which we treat in a self-contained way.
We emphasize the matroidal nature of our constructions, thereby showing how the above two families of random spanning subgraphs are dual to one another, as well as possible generalisations.
Mathematics Subject Classifications: 60C05, 05C31, 15A75, 05B35
Keywords: Determinantal probability measures, uniform spanning tree, cycle-rooted spanning forest, circular matroid, bicircular matroid, Laplacian determinant, matrix-tree theorem, Symanzik polynomials, Kirchhoff polynomials, graph polynomial, subgraph enumeration, measured matroid
- Monochromatic configurations on a circle
\enlargethispage{.2cm} If we two-colour a circle, we can always find an inscribed triangle with angles \((\frac{\pi}{7},\frac{2\pi}{7},\frac{4\pi}{7})\) whose three vertices have the same colour. In fact, Bialostocki and Nielsen showed that it is enough to consider the colours on the vertices of an inscribed heptagon. We prove that for every other triangle \(T\) there is a two-colouring of the circle without any monochromatic copy of \(T\).
More generally, for \(k\geq 3\), call a \(k\)-tuple \((d_1,d_2,\dots,d_k)\) with \(d_1\geq d_2\geq \dots \geq d_k›0\) and \(\sum_{i=1}^k d_i=1\) a Ramsey \(k\)-tuple if the following is true: in every two-colouring of the circle of unit perimeter, there is a monochromatic \(k\)-tuple of points in which the distances of cyclically consecutive points, measured along the arcs, are \(d_1,d_2,\dots,d_k\) in some order. By a conjecture of Stromquist, if \(d_i=\frac{2^{k-i}}{2^k-1}\), then \((d_1,\dots,d_k)\) is Ramsey.
Our main result is a proof of the converse of this conjecture. That is, we show that if \((d_1,\dots,d_k)\) is Ramsey, then \(d_i=\frac{2^{k-i}}{2^k-1}\). We do this by finding connections of the problem to certain questions from number theory about partitioning \(\mathbb{N}\) into so-called Beatty sequences. We also disprove a majority version of Stromquist's conjecture, study a robust version, and discuss a discrete version.
Mathematics Subject Classifications: 05C15, 05C55, 11B75
Keywords: Ramsey theory, balanced sequences
- Positively multiplicative graphs and homology rings of affine Grassmannians
Let \(\mathfrak{g}\) be an untwisted affine Lie algebra with associated Weyl group \(W_a\) and let \(W\) be the Weyl group of the corresponding simple Lie algebra. To any level-0 weight \(\gamma\) we associate a rooted weighted graph \(\Gamma_\gamma\) that encodes the orbit of \(\gamma\) under the action \(W_a\). From a combinatorial point of view, the graph \(\Gamma_{\gamma}\) is the weak version of the quantum Bruhat graph for the strong Bruhat order on either \(W\) or one of its parabolic quotients. We show that the graph \(\Gamma_\gamma\) encodes the periodic orientation of certain subsets of alcoves in \(W_a\) and therefore can be interpreted as an automaton determining the reduced expressions in these subsets. Then, by using some relevant quotients of the homology ring of affine Grassmannians, we show that the graph \(\Gamma_{\gamma}\) is positively multiplicative: there exists, in some sense, a maximal family of commuting adjacency matrices which also commute with the one of \(\Gamma_{\gamma}\). This yields the key ingredients to study a large class of random walks which can be either seen as random paths on alcoves or as interacting particle systems.
Mathematics Subject Classifications: 05E05, 05E10, 22E47, 57T15
Keywords: Root systems, affine Grassmannians, homology ring, oriented graphs, alcove walks
- Most \(q\)-matroids are not representable
A \(q\)-matroid is the analogue of a matroid which arises by replacing the finite ground set of a matroid with a finite-dimensional vector space over a finite field. These \(q\)-matroids are motivated by coding theory as the representable \(q\)-matroids are the ones that stem from rank-metric codes. In this note, we establish a \(q\)-analogue of Nelson's theorem in matroid theory by proving that asymptotically almost all \(q\)-matroids are not representable. This answers a question about representable \(q\)-matroids by Jurrius and Pellikaan strongly in the negative.
Mathematics Subject Classifications: 05B35, 05A30
Keywords: \(q\)-matroids, representability, rank-metric codes
- Infinite friezes of affine type D
In this article, we study infinite friezes arising from cluster categories of affine type \(D\) and determine the growth coefficients for these friezes. We prove that for each affine type \(D\), the friezes given by the non-homogeneous tubes all have the same growth behavior.
Mathematics Subject Classifications: 05E10, 16G20, 16G70, 13F60
Keywords: Friezes, cluster algebras, cluster character map, tame algebras
- On cycles in monotone grid classes of permutations
We undertake a detailed investigation into the structure of permutations in monotone grid classes whose row-column graphs do not contain components with more than one cycle. Central to this investigation is a new decomposition, called the \(M\)-sum, which generalises the well-known notions of direct sum and skew sum, and enables a deeper understanding of the structure of permutations in these grid classes. Permutations which are indecomposable with respect to the \(M\)-sum play a crucial role in the structure of a grid class and of its subclasses, and this leads us to identify coils, a certain kind of permutation which corresponds to repeatedly traversing a chosen cycle in a particular manner.
Harnessing this analysis, we give a precise characterisation for when a subclass of such a grid class is labelled well quasi-ordered, and we extend this to characterise (unlabelled) well quasi-ordering in certain cases. We prove that a large general family of these grid classes are finitely based, but we also exhibit other examples that are not, thereby disproving a conjecture from 2006 due to Huczynska and Vatter.
Mathematics Subject Classifications: 05A05, 06A07
Keywords: Permutation, permutation classes, grid classes, well quasi-order, labelled well quasi-order
- Thin simplices via modular arithmetic
The local \(h^*\)-polynomial is a natural invariant of a lattice polytope appearing in Ehrhart theory and Hodge theory. In this work, we study the question posed by Gelfand-Kapranov-Zelevinsky in 1994 concerning the classification of lattice simplices with vanishing local \(h^*\)-polynomial. Such simplices are called thin. We relate this question to linear codes and hyperplane arrangements over finite rings. This allows us to obtain a complete classification of the \(4\)-dimensional thin simplices, extending the previously known results in dimensions up to \(3\).
Mathematics Subject Classifications: 52B20, 94B05, 52C35
Keywords: Lattice simplex, Ehrhart theory, local \(h^*\)-polynomial, linear code, hyperplane arrangement
- A geometric realization of partially-symmetric Macdonald polynomials
We formulate a precise conjecture relating integral form partially-symmetric Macdonald polynomials and the parabolic flag Hilbert schemes of Carlsson, Gorsky, and Mellit. This extends, in an explicit fashion, Haiman's realization of modified Macdonald symmetric functions via Hilbert schemes of points in the plane. As evidence for our conjecture we prove that it is compatible with the action of certain elements in Carlsson and Mellit's algebra \(\mathbb{A}_{t,q}\), including degree \(1\) Pieri formulas.
Mathematics Subject Classifications: 05E10, 05E05
Keywords: Macdonald polynomials, Hilbert schemes, Hecke algebras
- Slit-slide-sew bijections for oriented planar maps
We construct growth bijections for bipolar oriented planar maps and for Schnyder woods. These give direct combinatorial proofs of several counting identities for these objects.
Our method mainly uses two ingredients. First, a slit-slide-sew operation, which consists in slightly sliding a map along a well-chosen path. Second, the study of the orbits of natural rerooting operations on the considered classes of oriented maps.
Mathematics Subject Classifications: 05A15, 05A19
Keywords: Bipolar orientations, Schnyder woods, combinatorial maps, enumeration, bijection, homomesy