Combinatorial Theory

We say that the families \(\mathcal{F}_1,\ldots, \mathcal{F}_{s+1}\) of \(k\)-element subsets of \([n]\) are cross-dependent if there are no pairwise disjoint sets \(F_1,\ldots, F_{s+1}\), where \(F_i\in \mathcal{F}_i\) for each \(i\). The rainbow version of the Erdős Matching Conjecture due to Aharoni and Howard and independently to Huang, Loh and Sudakov states that \(\min_{i} |\mathcal{F}_i|\le \max\big\{{n\choose k}-{n-s\choose k}, {(s+1)k-1\choose k}\big\}\) for \(n\ge (s+1)k\). In this paper, we prove this conjecture for \(n›3e(s+1)k\) and \(s›10^7\). One of the main tools in the proof is a concentration inequality due to Frankl and Kupavskii.

Mathematics Subject Classifications: 05D05

Keywords: Extremal set theory, Erdos matching conjecture, rainbow version

Let \(\Theta_n = (\theta_1, \dots, \theta_n)\) and \(\Xi_n = (\xi_1, \dots, \xi_n)\) be two lists of \(n\) variables and consider the diagonal action of \(\mathfrak{S}_n\) on the exterior algebra \(\wedge \{ \Theta_n, \Xi_n \}\) generated by these variables. Jongwon Kim and Rhoades defined and studied the fermionic diagonal coinvariant ring \(FDR_n\) obtained from \(\wedge \{ \Theta_n, \Xi_n \}\) by modding out by the \(\mathfrak{S}_n\)-invariants with vanishing constant term. The author and Rhoades gave a basis for the maximal degree components of this ring where the action of \(\mathfrak{S}_n\) could be interpreted combinatorially via noncrossing set partitions. This paper will do similarly for the entire ring, although the combinatorial interpretation will be limited to the action of \(\mathfrak{S}_{n-1} \subset \mathfrak{S}_n\). The basis will be indexed by a certain class of noncrossing partitions.

Mathematics Subject Classifications: 05E10, 05E18, 20C30

Keywords: Skein relation, coinvariant algebra, noncrossing set partition, cyclic sieving

We consider the (iterated) Kapranov embedding \(\Omega_n:\overline{M}_{0,n+3} \hookrightarrow \mathbb{P}^1 \times \cdots \times \mathbb{P}^n\), where \(\overline{M}_{0,n+3}\) is the moduli space of stable genus \(0\) curves with \(n+3\) marked points. In 2020, Gillespie, Cavalieri, and Monin gave a recursion satisfied by the multidegrees of \(\Omega_n\) and showed, using two combinatorial insertion algorithms on certain parking functions, that the total degree of \(\Omega_n\) is \((2n-1)!!=(2n-1)\cdot (2n-3) \cdots 5 \cdot 3 \cdot 1\). In this paper, we give a new proof of this fact by enumerating each multidegree by a set of boundary points of \(\overline{M}_{0,n+3}\), via an algorithm on trivalent trees that we call a lazy tournament. The advantages of this new interpretation are twofold: first, these sets project to one another under the forgetting maps used to derive the multidegree recursion. Second, these sets naturally partition the complete set of boundary points on \(\overline{M}_{0,n+2}\), of which there are \((2n-1)!!\), giving an immediate proof of the total degree formula.

Mathematics Subject Classifications: 05E14, 14N10, 05C05, 14H10, 05A19, 05C85

Keywords: Moduli spaces of curves, projective embeddings, multidegrees, trivalent trees

Given a function \(g=g(n)\) we let \(\mathcal{E}^g\) be the class of all graphs \(G\) such that if \(G\) has order \(n\) (that is, has \(n\) vertices) then it is embeddable in some surface of Euler genus at most \(g(n)\), and let \(\widetilde{\mathcal E}^g\) be the corresponding class of unlabelled graphs. We give estimates of the sizes of these classes. For example we show that if \(g(n)=o(n/\log^3n)\) then the class \(\mathcal{E}^{g}\) has growth constant \(\gamma_{\mathcal{P}}\), the (labelled) planar graph growth constant; and when \(g(n) = O(n)\) we estimate the number of n-vertex graphs in \(\mathcal{E}^{g}\) and \(\widetilde{\mathcal E}^g\) up to a factor exponential in \(n\). From these estimates we see that, if \(\mathcal{E}^g\) has growth constant \(\gamma_{\mathcal{P}}\) then we must have \(g(n)=o(n/\log n)\), and the generating functions for \(\mathcal{E}^g\) and \(\widetilde{\mathcal E}^g\) have strictly positive radius of convergence if and only if \(g(n)=O(n/\log n)\). Such results also hold when we consider orientable and non-orientable surfaces separately. We also investigate related classes of graphs where we insist that, as well as the graph itself, each subgraph is appropriately embeddable (according to its number of vertices); and classes of graphs where we insist that each minor is appropriately embeddable. In a companion paper, these results are used to investigate random \(n\)-vertex graphs sampled uniformly from \(\mathcal{E}^g\) or from similar classes.

Mathematics Subject Classifications: 05C10, 05C30

Keywords: Embeddable graphs, order-dependent surfaces, approximate counting, labelled graphs

It is well known since the seminal work by Bousquet-Mélou, Claesson, Dukes and Kitaev (2010) that certain refinements of the ascent sequences with respect to several natural statistics are in bijection with corresponding refinements of \(({\bf2+2})\)-free posets and permutations that avoid a bi-vincular pattern. Different multiply-refined enumerations of ascent sequences and other bijectively equivalent structures have subsequently been extensively studied by various authors. In this paper, our main contributions are

Mathematics Subject Classifications: 05A15, 05A19

Keywords: Ascent sequences, equidistributions, Euler-Stirling statistics, Fishburn numbers, basic hypergeometric series

The amplituhedron \(\mathcal{A}_{n,k,m}\) was introduced by Arkani-Hamed and Trnka (2014) in order to give a geometric basis for calculating scattering amplitudes in planar \(\mathcal{N}=4\) supersymmetric Yang-Mills theory. It is a projection inside the Grassmannian \(\text{Gr}_{k,k+m}\) of the totally nonnegative part of \(\text{Gr}_{k,n}\). Karp and Williams (2019) studied the \(m=1\) amplituhedron \(\mathcal{A}_{n,k,1}\), giving a regular CW decomposition of it. Its face poset \(R_{n,l}\) (with \(l := n-k-1\)) consists of all projective sign vectors of length \(n\) with exactly \(l\) sign changes. We show that \(R_{n,l}\) is EL-shellable, resolving a problem posed by Karp and Williams. This gives a new proof that \(\mathcal{A}_{n,k,1}\) is homeomorphic to a closed ball, which was originally proved by Karp and Williams. We also give explicit formulas for the \(f\)-vector and \(h\)-vector of \(R_{n,l}\), and show that it is rank-log-concave and strongly Sperner. Finally, we consider a related poset \(P_{n,l}\) introduced by Machacek (2019), consisting of all projective sign vectors of length \(n\) with at most \(l\) sign changes. We show that it is rank-log-concave, and conjecture that it is Sperner.

Mathematics Subject Classifications: 06A07, 14M15, 81T60, 05A19

Keywords: Amplituhedron, shellability, Eulerian number, log concavity, Sperner property

We derive asymptotic formulas for the number of integer partitions with given sums of \(j\)th powers of the parts for \(j\) belonging to a finite, non-empty set \(J \subset \mathbb N\). The method we use is based on the `principle of maximum entropy' of Jaynes. This principle leads to an intuitive variational formula for the asymptotics of the logarithm of the number of constrained partitions as the solution to a convex optimization problem over real-valued functions. Finding the polynomial corrections and leading constant involves two steps: quantifying the error in approximating a discrete optimization problem by a continuous one and proving a multivariate local central limit theorem.

Mathematics Subject Classifications: 05A17, 05A16, 60F05

Keywords: Integer partitions, maximum entropy, asymptotic enumeration, local central limit theorem, limit shape

The Kahn-Saks inequality is a classical result on the number of linear extensions of finite posets. We give a new proof of this inequality for posets of width two and both elements in the same chain using explicit injections of lattice paths. As a consequence we obtain a \(q\)-analogue, a multivariate generalization and an equality condition in this case. We also discuss the equality conditions of the Kahn-Saks inequality for general posets and prove several implications between conditions conjectured to be equivalent.

Mathematics Subject Classifications: 05A15, 05A19, 05A20, 05A30, 06A07

Keywords: Poset inequality, Stanley's inequality, Kahn-Saks inequality, log-concavity, q-analogues, equality conditions, lattice paths

Given a polygon \(P\) in the triangular grid, we obtain a permutation \(\pi_P\) via a natural billiards system in which beams of light bounce around inside of \(P\). The different cycles in \(\pi_P\) correspond to the different trajectories of light beams. We prove that \[\operatorname{area}(P)\geq 6\operatorname{cyc}(P)-6\quad\text{and}\quad\operatorname{perim}(P)\geq\frac{7}{2}\operatorname{cyc}(P)-\frac{3}{2},\] where \(\operatorname{area}(P)\) and \(\operatorname{perim}(P)\) are the (appropriately normalized) area and perimeter of \(P\), respectively, and \(\operatorname{cyc}(P)\) is the number of cycles in \(\pi_P\). The inequality concerning \(\operatorname{area}(P)\) is tight, and we characterize the polygons \(P\) satisfying \(\operatorname{area}(P)=6\operatorname{cyc}(P)-6\). These results can be reformulated in the language of Postnikov's plabic graphs as follows. Let \(G\) be a connected reduced plabic graph with essential dimension \(2\). Suppose \(G\) has \(n\) marked boundary points and \(v\) (internal) vertices, and let \(c\) be the number of cycles in the trip permutation of \(G\). Then we have \[v\geq 6c-6\quad\text{and}\quad n\geq\frac{7}{2}c-\frac{3}{2}.\]

Mathematics Subject Classifications: 05D99, 51M04

Keywords: Triangular grid, billiards, plabic graph, membrane

The Exponential Formula allows one to enumerate any class of combinatorial objects built by choosing a set of connected components and placing a structure on each connected component which depends only on its size. There are multiple variants of this result, including Speicher's result for noncrossing partitions, as well as analogues of the Exponential Formula for series-reduced planar trees and forests. In this paper we use these formulae to give generating functions for contracted Grassmannian trees and forests, certain graphs whose vertices are decorated with a helicity. Along the way we enumerate bipartite planar trees and forests, and we apply our results to enumerate various families of permutations: for example, bipartite planar trees are in bijection with separable permutations. It is postulated by Livia Ferro, Tomasz Łukowski and Robert Moerman (2020) that contracted Grassmannian forests are in bijection with boundary strata of the momentum amplituhedron, an object encoding the tree-level S-matrix of maximally supersymmetric Yang-Mills theory. With this assumption, our results give a rank generating function for the boundary strata of the momentum amplituhedron, and imply that the Euler characteristic of the momentum amplituhedron is \(1\).

Mathematics Subject Classifications: 05A05, 05A15, 05C10

Keywords: Generating functions, permutations, planar forests

A finite classical polar space of rank \(n\) consists of the totally isotropic subspaces of a finite vector space equipped with a nondegenerate form such that \(n\) is the maximal dimension of such a subspace. A \(t\)-Steiner system in a finite classical polar space of rank \(n\) is a collection \(Y\) of totally isotropic \(n\)-spaces such that each totally isotropic \(t\)-space is contained in exactly one member of \(Y\). Nontrivial examples are known only for \(t=1\) and \(t=n-1\). We give an almost complete classification of such \(t\)-Steiner systems, showing that such objects can only exist in some corner cases. This classification result arises from a more general result on packings in polar spaces.

Mathematics Subject Classifications: 51E23, 05E30, 33C80

Keywords: Association schemes, codes, polar spaces, Steiner systems

The coefficients of the chain polynomial of a finite poset enumerate chains in the poset by their number of elements. The chain polynomials of the partition lattices and their standard type \(B\) analogues are shown to have only real roots. The real-rootedness of the chain polynomial is conjectured for all geometric lattices and is shown to be preserved by the pyramid and the prism operations on Cohen-Macaulay posets. As a result, new families of convex polytopes whose barycentric subdivisions have real-rooted \(f\)-polynomials are presented. An application to the face enumeration of the second barycentric subdivision of the boundary complex of the simplex is also included.

Mathematics Subject Classifications: 05A05, 05A18, 05E45, 06A07, 26C10

Keywords: Chain polynomial, geometric lattice, partition lattice, real-rooted polynomial, flag \(h\)-vector, convex polytope, barycentric subdivision

Lascoux polynomials generalize Grassmannian stable Grothendieck polynomials and may be viewed as K-theoretic analogs of key polynomials. The latter two polynomials have combinatorial formulas involving tableaux: Lascoux and Schützenberger gave a combinatorial formula for key polynomials using right keys; Buch gave a set-valued tableau formula for Grassmannian stable Grothendieck polynomials. We establish a novel combinatorial description for Lascoux polynomials involving right keys and set-valued tableaux. Our description generalizes the tableaux formulas of key polynomials and Grassmannian stable Grothendieck polynomials. To prove our description, we construct a new abstract Kashiwara crystal structure on set-valued tableaux. This construction answers an open problem of Monical, Pechenik and Scrimshaw.

Mathematics Subject Classifications: 05E05

Keywords: Lascoux polynomials, set-valued tableaux, crystal operators

A combinatorial neural code \({\mathscr C}\subseteq 2^{[n]}\) is called convex if it arises as the intersection pattern of convex open subsets of \(\mathbb{R}^d\). We relate the emerging theory of convex neural codes to the established theory of oriented matroids, both with respect to geometry and computational complexity and categorically. For geometry and computational complexity, we show that a code has a realization with convex polytopes if and only if it lies below the code of a representable oriented matroid in the partial order of codes introduced by Jeffs. We show that previously published examples of non-convex codes do not lie below any oriented matroids, and we construct examples of non-convex codes lying below non-representable oriented matroids. By way of this construction, we can apply Mnëv-Sturmfels universality to show that deciding whether a combinatorial code is convex is NP-hard.

On the categorical side, we show that the map taking an acyclic oriented matroid to the code of positive parts of its topes is a faithful functor. We adapt the oriented matroid ideal introduced by Novik, Postnikov, and Sturmfels into a functor from the category of oriented matroids to the category of rings; then, we show that the resulting ring maps naturally to the neural ring of the matroid's neural code.

Mathematics Subject Classifications: 52C40, 13P25

Keywords: Oriented matroids, convex neural codes, hyperplane arrangements

We show that, for points along the moment curve, the bar-and-joint rigidity matroid and the hyperconnectivity matroid coincide, and that both coincide with the \(C^{d-2}_{d-1}\)-cofactor rigidity of points along any (non-degenerate) conic in the plane. For hyperconnectivity in dimension two, having the points in the moment curve is no loss of generality. We also show that, restricted to bipartite graphs, the bar-and-joint rigidity matroid is freer than the hyperconnectivity matroid.

Mathematics Subject Classifications: 52C25, 52B40

Keywords: Rigidity, hyperconnectivity, moment curve, cofactor rigidity

This paper compares skew-linear and multilinear matroid representations. These are matroids that are representable over division rings and (roughly speaking) invertible matrices, respectively. The main tool is the von Staudt construction, by which we translate our problems to algebra. After giving an exposition of a simple variant of the von Staudt construction we present the following results:

Mathematics Subject Classifications: 05B35, 52B40, 14N20, 52C35, 20F10, 03D40

Keywords: Matroids, division ring representations, subspace arrangements, \(c\)-arrange\-ments, multilinear matroids, von Staudt constructions, word problem, Weyl algebra, Baumslag-Solitar group

A 0-1 matrix \(M\) contains a 0-1 matrix pattern \(P\) if we can obtain \(P\) from \(M\) by deleting rows and/or columns and turning arbitrary 1-entries into 0s. The saturation function \(\mathrm{sat}(P,n)\) for a 0-1 matrix pattern \(P\) indicates the minimum number of 1s in an \(n \times n\) 0-1 matrix that does not contain \(P\), but changing any 0-entry into a 1-entry creates an occurrence of \(P\). Fulek and Keszegh recently showed that each pattern has a saturation function either in \(\mathcal{O}(1)\) or in \(\Theta(n)\). We fully classify the saturation functions of permutation matrices.

Mathematics Subject Classifications: 05D99

Keywords: Forbidden submatrices, saturation

Let \(G\) be a quasi-transitive, locally finite, connected graph rooted at a vertex \(o\), and let \(c_n(o)\) be the number of self-avoiding walks of length \(n\) on \(G\) starting at \(o\). We show that if \(G\) has only thin ends, then the generating function \(F_{\mathrm{SAW},o}(z)=\sum_{n \geq 1} c_n(o) z^n\) is an algebraic function. In particular, the connective constant of such a graph is an algebraic number.

If \(G\) is deterministically edge-labelled, that is, every (directed) edge carries a label such that no two edges starting at the same vertex have the same label, then the set of all words which can be read along the edges of self-avoiding walks starting at \(o\) forms a language denoted by \(L_{\mathrm{SAW},o}\). Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that \(L_{\mathrm{SAW},o}\) is a \(k\)-multiple context-free language if and only if the size of all ends of \(G\) is at most \(2k\). Applied to Cayley graphs of finitely generated groups this says that \(L_{\mathrm{SAW},o}\) is multiple context-free if and only if the group is virtually free.

Mathematics Subject Classifications: 20F10, 68Q45, 05C25

Keywords: Self avoiding walk, formal language, multiple context free language, Cayley graph, virtually free group