Skip to main content
eScholarship
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

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.

Research Articles

Locally uniform random permutations with large increasing subsequences

We investigate the maximal size of an increasing subset among points randomly sampled from certain probability densities. Kerov and Vershik's celebrated result states that the largest increasing subset among \(N\) uniformly random points on \([0,1]^2\) has size asymptotically \(2\sqrt{N}\). More generally, the order \(\Theta(\sqrt{N})\) still holds if the sampling density is continuous. In this paper we exhibit two sufficient conditions on the density to obtain a growth rate equivalent to any given power of \(N\) greater than \(\sqrt{N}\), up to logarithmic factors. Our proofs use methods of slicing the unit square into appropriate grids, and investigating sampled points appearing in each box.

Mathematics Subject Classifications: 60C05, 05A05

Keywords: Random permutations, longest increasing subsequences, permutons

  • 1 supplemental ZIP

Unimodular covers of \(3\)-dimensional parallelepipeds and Cayley sums

We show that the following classes of lattice polytopes have unimodular covers, in dimension three: parallelepipeds, smooth centrally symmetric polytopes, and Cayley sums \(\operatorname{Cay}(P,Q)\) where the normal fan of \(Q\) refines that of \(P\). This improves results of Beck et al. (2018) and Haase et al. (2008) where the last two classes were shown to be IDP.

Mathematics Subject Classifications: 52B10, 52B20, 52C17

Keywords: Lattice polytopes, unimodular covers, integer decomposition property

  • 1 supplemental ZIP

The monopole-dimer model on Cartesian products of plane graphs

The monopole-dimer model is a signed variant of the monomer-dimer model which has determinantal structure. We extend the monopole-dimer model for planar graphs (Math. Phys. Anal. Geom., 2015) to Cartesian products thereof and show that the partition function of this model can be expressed as a determinant of a generalised signed adjacency matrix. We then show that the partition function is independent of the orientations of the planar graphs so long as the orientations are Pfaffian. When these planar graphs are bipartite, we show that the computation of the partition function becomes especially simple. We then give an explicit product formula for the partition function of three-dimensional grid graphs a la Kasteleyn and Temperley-Fischer, which turns out to be fourth power of a polynomial when all grid lengths are even. Finally, we generalise this product formula to \(d\) dimensions, again obtaining an explicit product formula. We conclude with a discussion on asymptotic formulas for the free energy and monopole densities.

Mathematics Subject Classifications: 82B20, 05A15, 05C70

Keywords: Monopole-dimer model, cartesian products, determinantal formula, Kasteleyn orientation, bipartite, cycle decomposition, partition function, grid graphs, free energy

  • 1 supplemental ZIP

Covering grids with multiplicity

Given a finite grid in \(\mathbb{R}^2\), how many lines are needed to cover all but one point at least \(k\) times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball-Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball-Serra and provide an asymptotic answer for almost all grids. For the standard grid \(\{0,\ldots,n-1\} \times \{0,\ldots,n-1\}\), we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments.

 

Mathematics Subject Classifications: 05B40, 52C15, 05D40

Keywords: Grid covering, Alon-Füredi Theorem, combinatorial geometry, linear programming

  • 1 supplemental ZIP

On a common-extendable, non-Sidorenko linear system

A system of linear equations in \(\mathbb{F}_p^n\) is common if every two-colouring of \(\mathbb{F}_p^n\) yields at least as many monochromatic solutions as a random two-colouring, asymptotically as \(n \to \infty\). By analogy to the graph-theoretic setting, Alon has asked whether any (non-Sidorenko) system of linear equations can be made uncommon by adding sufficiently many free variables. Fox, Pham and Zhao answered this question in the affirmative among systems which consist of a single equation. We answer Alon's question in the negative.

We also observe that the property of remaining common despite that addition of arbitrarily many free variables is closely related to a notion of commonness in which one replaces the arithmetic mean of the number of monochromatic solutions with the geometric mean, and furthermore resolve questions of Kamčev-Liebenau-Morrison.

Mathematics Subject Classifications: 05D10, 11B30

Keywords: Sidorenko's conjecture, Sidorenko and common linear patterns

  • 1 supplemental ZIP

Counting numerical semigroups by Frobenius number, multiplicity, and depth

In 1990, Backelin showed that the number of numerical semigroups with Frobenius number \(f\) approaches \(C_i \cdot 2^{f/2}\) for constants \(C_0\) and \(C_1\) depending on the parity of \(f\). In this paper, we generalize this result to semigroups of arbitrary depth by showing there are \(\lfloor (q+1)^2/4 \rfloor^{f/(2q-2)+o(f)}\) semigroups with Frobenius number \(f\) and depth \(q\). More generally, for fixed \(q \geq 3\), we show that, given \((q-1)m ‹ f ‹ qm\), the number of numerical semigroups with Frobenius number \(f\) and multiplicity \(m\) is \[\left(\left\lfloor \frac{(q+2)^2}{4} \right\rfloor^{\alpha/2} \left \lfloor \frac{(q+1)^2}{4} \right\rfloor^{(1-\alpha)/2}\right)^{m + o(m)}\] where \(\alpha = f/m - (q-1)\). Among other things, these results imply Backelin's result, strengthen bounds on \(C_i\), characterize the limiting distribution of multiplicity and genus with respect to Frobenius number, and resolve a recent conjecture of Singhal on the number of semigroups with fixed Frobenius number and maximal embedding dimension.

Mathematics Subject Classifications: 05A16, 20M14

Keywords: Numerical semigroups, Kunz coordinates, graph homomorphisms

  • 1 supplemental ZIP

Birational rowmotion on a rectangle over a noncommutative ring

We extend the periodicity of birational rowmotion for rectangular posets to the case when the base field is replaced by a noncommutative ring (under appropriate conditions). This resolves a conjecture from 2014. The proof uses a novel approach and is fully self-contained. Consider labelings of a finite poset \(P\) by \(\left\vert P\right\vert + 2\) elements of a ring \(\mathbb{K}\): one label associated with each poset element and two constant labels for the added top and bottom elements in \(\widehat{P}\). Birational rowmotion is a partial map on such labelings. It was originally defined by Einstein and Propp for \(\mathbb{K}=\mathbb{R}\) as a lifting (via detropicalization) of piecewise-linear rowmotion, a map on the order polytope \(\mathcal{O}(P) := \{\text{order-preserving } f: P \to[0,1]\}\). The latter, in turn, extends the well-studied rowmotion map on the set of order ideals (or more properly, the set of order filters) of \(P\), which correspond to the vertices of \(\mathcal{O}(P)\). Dynamical properties of these combinatorial maps sometimes (but not always) extend to the birational level, while results proven at the birational level always imply their combinatorial counterparts. Allowing \(\mathbb{K}\) to be noncommutative, we generalize the birational level even further, and some properties are in fact lost at this step.

In 2014, the authors gave the first proof of periodicity for birational rowmotion on rectangular posets (when \(P\) is a product of two chains) for \(\mathbb{K}\) a field, and conjectured that it survives (in an appropriately twisted form) in the noncommutative case. In this paper, we prove this noncommutative periodicity and a concomitant antipodal reciprocity formula. We end with some conjectures about periodicity for other posets, and the question of whether our results can be extended to (noncommutative) semirings.

It has been observed by Glick and Grinberg that, in the commutative case, periodicity of birational rowmotion can be used to derive Zamolodchikov periodicity in the type \(AA\) case, and vice-versa. However, for noncommutative \(\mathbb{K}\), Zamolodchikov periodicity fails even in small examples (no matter what order the factors are multiplied), while noncommutative birational rowmotion continues to exhibit periodicity. Thus, our result can be viewed as a lateral generalization of Zamolodchikov periodicity to the noncommutative setting.

Mathematics Subject Classifications: 06A07, 05E99

Keywords: Rowmotion, posets, noncommutative rings, semirings, Zamolodchikov periodicity, root systems, promotion, trees, graded posets, Grassmannian, tropicalization

  • 1 supplemental ZIP

The combinatorics of a tree-like functional equation for connected chord diagrams

We build on recent work of Yeats, Courtiel, and others involving connected chord diagrams. We first derive from a Hopf-algebraic foundation a class of tree-like functional equations and prove that they are solved by weighted generating functions of two different subsets of weighted connected chord diagrams: arbitrary diagrams and diagrams forbidding so-called top cycle subdiagrams. These equations generalize the classic specification for increasing ordered trees and their solution uses a novel decomposition, simplifying and generalizing previous results. The resulting tree perspective on chord diagrams leads to new enumerative insights through the study of novel diagram classes. We present a recursive bijection between connected top-cycle-free diagrams with \(n\) chords and triangulations of a disk with \(n+1\) vertices, thereby counting the former. This connects to combinatorial maps, Catalan intervals, and uniquely sorted permutations, leading to new conjectured bijective relationships between diagram classes defined by forbidding graphical subdiagrams and imposing connectedness properties and a rich variety of other combinatorial objects. We conclude by exhibiting and studying a direct bijection between diagrams of size \(n\) with a single terminal chord and diagrams of size \(n-1\).

Mathematics Subject Classifications: 05A05, 05A10, 05A15, 05A18, 05A19

Keywords: Chord diagrams, perfect matchings, combinatorial classes, pattern avoidance, combinatorial maps, triangulations, Catalan posets, uniquely sorted permutations

  • 1 supplemental ZIP

The induced saturation problem for posets

For a fixed poset \(P\), a family \(\mathcal F\) of subsets of \([n]\) is induced \(P\)-saturated if \(\mathcal F\) does not contain an induced copy of \(P\), but for every subset \(S\) of \([n]\) such that \( S\not \in \mathcal F\), \(P\) is an induced subposet of \(\mathcal F \cup \{S\}\). The size of the smallest such family \(\mathcal F\) is denoted by \(\text{sat}^* (n,P)\). Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset \(P\), either \(\text{sat}^* (n,P)=O(1)\) or \(\text{sat}^* (n,P)\geq \log _2 n\). In this paper we improve this general result showing that either \(\text{sat}^* (n,P)=O(1)\) or \(\text{sat}^* (n,P) \geq \min\{ 2 \sqrt{n}, n/2+1\}\). Our proof makes use of a Turán-type result for digraphs.

Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states that for the so-called diamond poset \(\Diamond\) we have \(\text{sat}^* (n,\Diamond)=\Theta (\sqrt{n})\); so if true this conjecture implies our result is tight up to a multiplicative constant. On the other hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states that given any poset \(P\), either \(\text{sat}^* (n,P)=O(1)\) or \(\text{sat}^* (n,P)\geq n+1\). We prove that this latter conjecture is true for a certain class of posets \(P\).

Mathematics Subject Classifications: 06A07, 05D05

Keywords: Partially ordered sets, saturation, Turán-type problems

  • 1 supplemental ZIP

A horizontal-strip LLT polynomial is determined by its weighted graph

We prove that two horizontal-strip LLT polynomials are equal if the associated weighted graphs defined by the author in a previous paper are isomorphic. This provides a sufficient condition for equality of horizontal-strip LLT polynomials and yields a well-defined LLT polynomial indexed by a weighted graph. We use this to prove some new relations between LLT polynomials and we explore a connection with extended chromatic symmetric functions.

Mathematics Subject Classifications: 05E05, 05E10, 05C15

Keywords: Chromatic symmetric function, LLT polynomial, Hall-Littlewood polynomial, interval graph, Schur function, weighted graph

  • 1 supplemental ZIP

Webs and canonical bases in degree two

We show that Lusztig's canonical basis for the degree two part of the Grassmannian coordinate ring is given by \({\rm SL}_k\) web diagrams. Equivalently, we show that every \({\rm SL}_2\) web immanant of a plabic graph for \({\rm Gr}(k,n)\) is an \({\rm SL}_k\) web invariant.

Mathematics Subject Classifications: 05E10, 14M15, 20C30

Keywords: Grassmannians, webs, canonical basis, Catalan

  • 1 supplemental ZIP

A symmetric function lift of torus link homology

Suppose \(M\) and \(N\) are positive integers and let \(k = \gcd(M, N)\), \(m = M/k\), and \(n=N/k\). We define a symmetric function \(L_{M,N}\) as a weighted sum over certain tuples of lattice paths. We show that \(L_{M,N}\) satisfies a generalization of Hogancamp and Mellit's recursion for the triply-graded Khovanov-Rozansky homology of the \(M,N\)-torus link. As a corollary, we obtain the triply-graded Khovanov-Rozansky homology of the \(M,N\)-torus link as a specialization of \(L_{M,N}\). We conjecture that \(L_{M,N}\) is equal (up to a constant) to the elliptic Hall algebra operator \(\mathbf{Q}_{m,n}\) composed \(k\) times and applied to 1.

Mathematics Subject Classifications: 05E05, 57M27

Keywords: Lattice paths, Dyck paths, link homology, torus links, elliptic Hall algebra, LLT polynomials

  • 1 supplemental ZIP

Schubert matroids, Delannoy paths, and Speyer's invariant

We provide a combinatorial way of computing Speyer's \(g\)-polynomial on arbitrary Schubert matroids via the enumeration of certain Delannoy paths. We define a new statistic of a basis in a matroid, and express the \(g\)-polynomial of a Schubert matroid in terms of it and internal and external activities. Some surprising positivity properties of the \(g\)-polynomial of Schubert matroids are deduced from our expression. Finally, we combine our formulas with a fundamental result of Derksen and Fink to provide an algorithm for computing the \(g\)-polynomial of an arbitrary matroid.

Mathematics Subject Classifications: 05B35, 52B40, 14T15

Keywords: Schubert matroids, \(g\)-polynomial, matroid polytopes, series-parallel matroids, lattice path enumeration

  • 1 supplemental ZIP

Shifted insertion algorithms for primed words

This article studies some new insertion algorithms that associate pairs of shifted tableaux to finite integer sequences in which certain terms may be primed. When primes are ignored in the input word these algorithms reduce to known correspondences, namely, a shifted form of Edelman-Greene insertion, Sagan-Worley insertion, and Haiman's shifted mixed insertion. These maps have the property that when the input word varies such that one output tableau is fixed, the other output tableau ranges over all (semi)standard tableaux of a given shape with no primed diagonal entries. Our algorithms have the same feature, but now with primes allowed on the main diagonal. One application of this is to give another Littlewood-Richardson rule for products of Schur \(Q\)-functions. It is hoped that there will exist set-valued generalizations of our bijections that can be used to understand products of \(K\)-theoretic Schur \(Q\)-functions.

Mathematics Subject Classifications: 05A19, 05E05

Keywords: Shifted tableaux, Edelman-Greene insertion, Sagan-Worley insertion, shifted mixed insertion, Schur \(Q\)-functions

  • 1 supplemental ZIP

Unavoidable order-size pairs in hypergraphs -- positive forcing density

Erdős, Füredi, Rothschild and Sós initiated a study of classes of graphs that forbid every induced subgraph on a given number \(m\) of vertices and number \(f\) of edges. Extending their notation to \(r\)-graphs, we write \((n,e) \to_r (m,f)\) if every \(r\)-graph \(G\) on \(n\) vertices with \(e\) edges has an induced subgraph on \(m\) vertices and \(f\) edges. The forcing density of a pair \((m,f)\) is \[ \sigma_r(m,f) =\left. \limsup\limits_{n \to \infty} \frac{|\{e : (n,e) \to_r (m,f)\}|}{\binom{n}{r}} \right. .\] In the graph setting it is known that there are infinitely many pairs \((m, f)\) with positive forcing density. Weber asked if there is a pair of positive forcing density for \(r\geq 3\) apart from the trivial ones \((m, 0)\) and \((m, \binom{m}{r})\). Answering her question, we show that \((6,10)\) is such a pair for \(r=3\) and conjecture that it is the unique such pair. Further, we find necessary conditions for a pair to have positive forcing density, supporting this conjecture.

Mathematics Subject Classifications: 05C35, 05C65

Keywords: Induced hypergraphs, forcing density

  • 1 supplemental ZIP

Minimum degrees of finite rectangular bands, null semigroups, and variants of full transformation semigroups

For a positive integer \(n\), the full transformation semigroup \({\mathcal T}_n\) consists of all self maps of the set \(\{1,\ldots,n\}\) under composition. Any finite semigroup \(S\) embeds in some \({\mathcal T}_n\), and the least such \(n\) is called the (minimum transformation) degree of \(S\) and denoted \(\mu(S)\). We find degrees for various classes of finite semigroups, including rectangular bands, rectangular groups and null semigroups. The formulae we give involve natural parameters associated to integer compositions. Our results on rectangular bands answer a question of Easdown from 1992, and our approach utilises some results of independent interest concerning partitions/colourings of hypergraphs.

As an application, we prove some results on the degree of a variant \({\mathcal T}_n^a\). (The variant \(S^a=(S,\star)\) of a semigroup \(S\), with respect to a fixed element \(a\in S\), has underlying set \(S\) and operation \(x\star y=xay\).) It has been previously shown that \(n\leq \mu({\mathcal T}_n^a)\leq 2n-r\) if the sandwich element \(a\) has rank \(r\), and the upper bound of \(2n-r\) is known to be sharp if \(r\geq n-1\). Here we show that \(\mu({\mathcal T}_n^a)=2n-r\) for \(r\geq n-6\). In stark contrast to this, when \(r=1\), and the above inequality says \(n\leq\mu({\mathcal T}_n^a)\leq 2n-1\), we show that \(\mu({\mathcal T}_n^a)/n\to1\) and \(\mu({\mathcal T}_n^a)-n\to\infty\) as \(n\to\infty\).

Among other results, we also classify the \(3\)-nilpotent subsemigroups of \({\mathcal T}_n\), and calculate the maximum size of such a subsemigroup.

Mathematics Subject Classifications: 20M20, 20M15, 20M30, 05E16, 05C65

Keywords: Transformation semigroup, transformation representation, semigroup variant, rectangular band, nilpotent semigroup, hypergraph

  • 1 supplemental ZIP

Harmonic differential forms for pseudo-reflection groups II. Bi-degree bounds

This paper studies three results that describe the structure of the super-coinvariant algebra of pseudo-reflection groups over a field of characteristic \(0\). Our most general result determines the top component in total degree, which we prove for all Shephard-Todd groups \(G(m, p, n)\) with \(m \neq p\) or \(m=1\). Our strongest result gives tight bi-degree bounds and is proven for all \(G(m, 1, n)\), which includes the Weyl groups of types \(A\) and \(B\)/\(C\). For symmetric groups (i.e. type \(A\)), this provides new evidence for a recent conjecture of Zabrocki related to the Delta Conjecture of Haglund-Remmel-Wilson. Finally, we examine analogues of a classic theorem of Steinberg and the Operator Theorem of Haiman.

Our arguments build on the type-independent classification of semi-invariant harmonic differential forms carried out in the first paper in this sequence. In this paper we use concrete constructions including Gröbner and Artin bases for the classical coinvariant algebras of the pseudo-reflection groups \(G(m, p, n)\), which we describe in detail. We also prove that exterior differentiation is exact on the super-coinvariant algebra of a general pseudo-reflection group. Finally, we discuss related conjectures and enumerative consequences.

 

 

Mathematics Subject Classifications: 05E16 (Primary), 20F55, 05A15 (Secondary)

Keywords: Coinvariant algebras, pseudo-reflection groups, Gröbner basis, Artin basis, differential forms, exterior derivatives

  • 1 supplemental ZIP