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 3, Issue 1, 2023
Research Articles
Rainbow version of the Erdős Matching Conjecture via concentration
We say that the families
Mathematics Subject Classifications: 05D05
Keywords: Extremal set theory, Erdos matching conjecture, rainbow version
- 1 supplemental ZIP
A combinatorial basis for the fermionic diagonal coinvariant ring
Let
Mathematics Subject Classifications: 05E10, 05E18, 20C30
Keywords: Skein relation, coinvariant algebra, noncrossing set partition, cyclic sieving
- 1 supplemental ZIP
Lazy tournaments and multidegrees of a projective embedding of
We consider the (iterated) Kapranov embedding
Mathematics Subject Classifications: 05E14, 14N10, 05C05, 14H10, 05A19, 05C85
Keywords: Moduli spaces of curves, projective embeddings, multidegrees, trivalent trees
- 1 supplemental ZIP
Classes of graphs embeddable in order-dependent surfaces
Given a function
Mathematics Subject Classifications: 05C10, 05C30
Keywords: Embeddable graphs, order-dependent surfaces, approximate counting, labelled graphs
- 1 supplemental ZIP
Proof of a bi-symmetric septuple equidistribution on ascent sequences
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
Mathematics Subject Classifications: 05A15, 05A19
Keywords: Ascent sequences, equidistributions, Euler-Stirling statistics, Fishburn numbers, basic hypergeometric series
- 1 supplemental ZIP
Shelling the amplituhedron
The amplituhedron
Mathematics Subject Classifications: 06A07, 14M15, 81T60, 05A19
Keywords: Amplituhedron, shellability, Eulerian number, log concavity, Sperner property
- 1 supplemental ZIP
Maximum entropy and integer partitions
We derive asymptotic formulas for the number of integer partitions with given sums of
Mathematics Subject Classifications: 05A17, 05A16, 60F05
Keywords: Integer partitions, maximum entropy, asymptotic enumeration, local central limit theorem, limit shape
- 1 supplemental ZIP
Extensions of the Kahn-Saks inequality for posets of width two
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
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
- 1 supplemental ZIP
Triangular-grid billiards and plabic graphs
Given a polygon
Mathematics Subject Classifications: 05D99, 51M04
Keywords: Triangular grid, billiards, plabic graph, membrane
- 1 supplemental ZIP
Grass(mannian) trees and forests: Variations of the exponential formula, with applications to the momentum amplituhedron
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
Mathematics Subject Classifications: 05A05, 05A15, 05C10
Keywords: Generating functions, permutations, planar forests
- 1 supplemental ZIP
Packings and Steiner systems in polar spaces
A finite classical polar space of rank
Mathematics Subject Classifications: 51E23, 05E30, 33C80
Keywords: Association schemes, codes, polar spaces, Steiner systems
- 1 supplemental ZIP
Chain enumeration, partition lattices and polynomials with only real roots
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
Mathematics Subject Classifications: 05A05, 05A18, 05E45, 06A07, 26C10
Keywords: Chain polynomial, geometric lattice, partition lattice, real-rooted polynomial, flag
- 1 supplemental ZIP
Set-valued tableaux rule for Lascoux polynomials
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
- 1 supplemental ZIP
Oriented matroids and combinatorial neural codes
A combinatorial neural code
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
- 1 supplemental ZIP
Bar-and-joint rigidity on the moment curve coincides with cofactor rigidity on a conic
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
Mathematics Subject Classifications: 52C25, 52B40
Keywords: Rigidity, hyperconnectivity, moment curve, cofactor rigidity
- 1 supplemental ZIP
Von Staudt constructions for skew-linear and multilinear matroids
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:
Undecidability of several matroid representation problems over division rings. An example of a matroid with an infinite multilinear characteristic set, but which is not multilinear in characteristic
Mathematics Subject Classifications: 05B35, 52B40, 14N20, 52C35, 20F10, 03D40
Keywords: Matroids, division ring representations, subspace arrangements,
- 1 supplemental ZIP
An exact characterization of saturation for permutation matrices
A 0-1 matrix
Mathematics Subject Classifications: 05D99
Keywords: Forbidden submatrices, saturation
- 1 supplemental ZIP
Self-avoiding walks and multiple context-free languages
Let
If
Mathematics Subject Classifications: 20F10, 68Q45, 05C25
Keywords: Self avoiding walk, formal language, multiple context free language, Cayley graph, virtually free group
- 1 supplemental ZIP