Combinatorial Theory

A permutation \(\sigma \in S_n\) is a \(k\)-superpattern (or \(k\)-universal) if it contains each \({\tau \in S_k}\) as a pattern. This notion of "superpatterns" can be generalized to words on smaller alphabets, and several questions about superpatterns on small alphabets have recently been raised in the survey of Engen and Vatter. One of these questions concerned the length of the shortest \(k\)-superpattern on \([k+1]\). A construction by Miller gave an upper bound of \({(k^2+k)/2}\), which we show is optimal up to lower-order terms. This implies a weaker version of a conjecture by Eriksson, Eriksson, Linusson and Wastlund. Our results also refute a 40-year-old conjecture of Gupta.

Mathematics Subject Classifications: 05A05, 60C05

Keywords: Patterns, permutations, probabalistic method

A box-ball system is a discrete dynamical system whose dynamics come from the balls jumping according to certain rules. A permutation on \(n\) objects gives a box-ball system state by assigning its one-line notation to \(n\) consecutive boxes. After a finite number of steps, a box-ball system will reach a steady state. From any steady state, we can construct a tableau called the soliton decomposition of the box-ball system. We prove that if the soliton decomposition of a permutation \(w\) is a standard tableau or if its shape coincides with the Robinson-Schensted (RS) partition of \(w\), then the soliton decomposition of \(w\) and the RS insertion tableau of \(w\) are equal. We also use row reading words, Knuth moves, RS recording tableaux, and a localized version of Greene's theorem (proven recently by Lewis, Lyu, Pylyavskyy, and Sen) to study various properties of a box-ball system.

Mathematics Subject Classifications: 05A05, 05A17, 37B15

Keywords: Permutations, box-ball systems, soliton cellular automata, Young tableaux, Robinson-Schensted-Knuth correspondence, Greene's theorem, Knuth equivalence

We introduce a solvable lattice model for supersymmetric LLT polynomials, also known as super LLT polynomials, based upon particle interactions in super \(n\)-ribbon tableaux. Using related Heisenberg operators on a Fock space, we prove Cauchy and Pieri identities for super LLT polynomials, simultaneously generalizing the Cauchy, dual Cauchy, and Pieri identities for LLT polynomials. Lastly, we construct a solvable semi-infinite Cauchy lattice model with a surprising Yang-Baxter equation and examine its connections to the Pieri and Cauchy identities.

Mathematics Subject Classifications: 05E05, 82B20, 05E10

Keywords: Lattice models, super LLT polynomials

In this paper, we extend the rectangular side of the shuffle conjecture by stating a rectangular analogue of the square paths conjecture. In addition, we describe a set of combinatorial objects and one statistic that are a first step towards a rectangular extension of (the rise version of) the Delta conjecture, and of (the rise version of) the Delta square conjecture, corresponding to the case \(q=1\) of an expected general statement. We also prove our new rectangular paths conjecture in the special case when the sides of the rectangle are coprime.

Mathematics Subject Classifications: 05E05

Keywords: Macdonald polynomials, symmetric functions

We prove that every \(n\)-vertex tournament has at most \(n \left(\frac{n-1}{2} \right)^k\) walks of length \(k\).

Mathematics Subject Classifications: 05C38, 05D99

Keywords: Paths, tournaments

Work of Grantcharov et al. develops a theory of abstract crystals for the queer Lie superalgebra \(\mathfrak{q}_n\). Such \(\mathfrak{q}_n\)-crystals form a monoidal category in which the connected normal objects have unique highest weight elements and characters that are Schur \(P\)-polynomials. This article studies a modified form of this category, whose connected normal objects again have unique highest weight elements but now possess characters that are Schur \(Q\)-polynomials. The crystals in this category have some interesting features not present for ordinary \(\mathfrak{q}_n\)-crystals. For example, there is an extra crystal operator, a different tensor product, and an action of the hyperoctahedral group exchanging highest and lowest weight elements. There are natural examples of \(\mathfrak{q}_n\)-crystal structures on certain families of shifted tableaux and factorized reduced words. We describe extended forms of these structures that give similar examples in our new category.

Mathematics Subject Classifications: 05E05, 05E10

Keywords: Crystals, Schur \(Q\)-functions, queer Lie superalgebras, shifted tableaux, involution words

We obtain exact expressions counting the satisfiable 2-SAT formulae and describe the structure of associated implication digraphs. Our approach is based on generating function manipulations. To reflect the combinatorial specificities of the implication digraphs, we introduce a new kind of generating function, the Implication generating function, inspired by the Graphic generating function used in digraph enumeration. Using the underlying recurrences, we make accurate numerical predictions of the phase transition curve of the 2-SAT problem inside the critical window. We expect these exact formulae to be amenable to rigorous asymptotic analysis using complex analytic tools, leading to a more detailed picture of the 2-SAT phase transition in the future.

Mathematics Subject Classifications: 05A15, 68Q87, 68R95

Keywords: 2-CNF, exact enumeration, random graphs, phase transitions, strongly connected components, satisfiability, generating functions

We develop a new approach for the computation of the Mullineux involution for the symmetric group and its Hecke algebra using the notion of crystal isomorphism and the Iwahori-Matsumoto involution for the affine Hecke algebra of type \(A\). As a consequence, we obtain several new elementary combinatorial algorithms for its computation, one of which is equivalent to Xu algorithm (and thus Mullineux original algorithm). We thus obtain a simple interpretation of these algorithms and a new elementary proof that they indeed compute the Mullineux involution.

Mathematics Subject Classifications: 20C08, 05E10

Keywords: Symmetric group, Mullineux involution, crystal graph

The families \(\mathcal{F}_0,\ldots,\mathcal{F}_s\) of \(k\)-element subsets of \([n]:=\{1,2,\ldots,n\}\) are called cross-union if there is no choice of \(F_0\in \mathcal{F}_0, \ldots, F_s\in \mathcal{F}_s\) such that \(F_0\cup\ldots\cup F_s=[n]\). A natural generalization of the celebrated Erdős-Ko-Rado theorem, due to Frankl and Tokushige, states that for \(n\le (s+1)k\) the geometric mean of \(\lvert\mathcal{F}_i\rvert\) is at most \(\binom{n-1}{k}\). Frankl conjectured that the same should hold for the arithmetic mean under some mild conditions. We prove Frankl's conjecture in a strong form by showing that the unique (up to isomorphism) maximizer for the arithmetic mean of cross-union families is the natural one \(\mathcal{F}_0=\ldots=\mathcal{F}_s={[n-1]\choose k}\).

Mathematics Subject Classifications: 05D05

Keywords: Extremal set theory, generalizations of Erdős-Ko-Rado, cross-union families, cross-intersecting families

In 2013, Zhai proved that most numerical semigroups of a given genus have depth at most \(3\) and that the number \(n_g\) of numerical semigroups of a genus \(g\) is asymptotic to \(S\varphi^g\), where \(S\) is some positive constant and \(\varphi \approx 1.61803\) is the golden ratio. In this paper, we prove exponential upper and lower bounds on the factors that cause \(n_g\) to deviate from a perfect exponential, including the number of semigroups with depth at least \(4\). Among other applications, these results imply the sharpest known asymptotic bounds on \(n_g\) and shed light on a conjecture by Bras-Amorós (2008) that \(n_g \geq n_{g-1} + n_{g-2}\). Our main tools are the use of Kunz coordinates, introduced by Kunz (1987), and a result by Zhao (2011) bounding weighted graph homomorphisms.

Mathematics Subject Classifications: 20M14, 05A15, 05A16

Keywords: Numerical semigroup, genus, Kunz coordinate, graph homomorphism

We develop an algebraic theory of supports for \(R\)-linear codes of fixed length, where \(R\) is a finite commutative unitary ring. A support naturally induces a notion of generalized weights and allows one to associate a monomial ideal to a code. Our main result states that, under suitable assumptions, the generalized weights of a code can be obtained from the graded Betti numbers of its associated monomial ideal. In the case of \(\mathbb{F}_q\)-linear codes endowed with the Hamming metric, the ideal coincides with the Stanley-Reisner ideal of the matroid associated to the code via its parity-check matrix. In this special setting, we recover the known result that the generalized weights of an \(\mathbb{F}_q\)-linear code can be obtained from the graded Betti numbers of the ideal of the matroid associated to the code. We also study subcodes and codewords of minimal support in a code, proving that a large class of \(R\)-linear codes is generated by its codewords of minimal support.

Mathematics Subject Classifications: 94B05, 13D02, 13F10

Keywords: Linear codes, codes over rings, supports, generalized weights, monomial ideal of a code, graded Betti numbers, matroid

Cluster integrable systems are a broad class of integrable systems modelled on bipartite dimer models on the torus. Many discrete integrable dynamics arise by applying sequences of local transformations, which form the cluster modular group of the cluster integrable system. This cluster modular group was recently characterized by the first author and Inchiostro. There exist some discrete integrable dynamics that make use of non-local transformations associated with geometric \(R\)-matrices. In this article we characterize the generalized cluster modular group - which includes both local and non-local transformations - in terms of extended affine symmetric groups. We also describe the action of the generalized cluster modular group on the spectral data associated with cluster integrable systems.

Mathematics Subject Classifications: 82B23, 13F60, 14H70, 20B35

Keywords: Bipartite dimer model, cluster algebras, geometric \(R\)-matrices, discrete integrable systems, extended affine symmetric group

A set system \({\mathcal F}\) is \(t\)-intersecting, if the size of the intersection of every pair of its elements has size at least \(t\). A set system \({\mathcal F}\) is \(k\)-Sperner, if it does not contain a chain of length \(k+1\). Our main result is the following: Suppose that \(k\) and \(t\) are fixed positive integers, where \(n+t\) is even and \(n\) is large enough. If \({\mathcal F}\subseteq 2^{[n]}\) is a \(t\)-intersecting \(k\)-Sperner family, then \(|{\mathcal F}|\) has size at most the size of the sum of \(k\) layers, of sizes \((n+t)/2,\ldots, (n+t)/2+k-1\). This bound is best possible. The case when \(n+t\) is odd remains open.

Mathematics Subject Classifications: 05D05

Keywords: Extremal set theory, Sperner families, intersection theorems

The rowmotion operator acting on the set of order ideals of a finite poset has been the focus of a significant amount of recent research. One of the major goals has been to exhibit homomesies: statistics that have the same average along every orbit of the action. We systematize a technique for proving that various statistics of interest are homomesic by writing these statistics as linear combinations of "toggleability statistics" (originally introduced by Striker) plus a constant. We show that this technique recaptures most of the known homomesies for the posets on which rowmotion has been most studied. We also show that the technique continues to work in modified contexts. For instance, this technique also yields homomesies for the piecewise-linear and birational extensions of rowmotion; furthermore, we introduce a \(q\)-analogue of rowmotion and show that the technique yields homomesies for "\(q\)-rowmotion" as well.

Mathematics Subject Classifications: 06A07, 05E18, 05A30, 52B05

Keywords: Homomesy, rowmotion, toggling, piecewise-linear & birational lift, \(q\)-analogue

We prove an explicit expression for the solutions of the discrete Schwarzian octahedron recurrence, also known as the discrete Schwarzian KP equation (dSKP), as the ratio of two partition functions. Each one counts weighted oriented dimer configurations of an associated bipartite graph, and is equal to the determinant of a Kasteleyn matrix. This is in the spirit of Speyer's result on the dKP equation, or octahedron recurrence (Journal of Alg. Comb. 2007). One consequence is that dSKP has zero algebraic entropy, meaning that the growth of the degrees of the polynomials involved is only polynomial. There are cancellations in the partition function, and we prove an alternative, cancellation free explicit expression involving complementary trees and forests. Using all of the above, we show several instances of the Devron property for dSKP, i.e., that certain singularities in initial data repeat after a finite number of steps. This has many applications for discrete geometric systems and is the subject of a companion paper (preprint 2022, Affolter, de Tillière, and Melotti). We also find limit shape results analogous to the arctic circle of the Aztec diamond. Finally, we discuss the combinatorics of all the other octahedral equations in the classification of Adler, Bobenko and Suris (IMRN 2012).

Mathematics Subject Classifications: 05A15, 37K10, 37K60, 82B20, 82B23

Keywords: Dimer model, octahedron recurrence, discrete KP equation, integrable system, spanning forests, algebraic entropy, discrete geometry, projective geometry, Aztec diamond, limit shapes

Propp recently introduced regions in the hexagonal grid called benzels and stated several enumerative conjectures about the tilings of benzels using two types of prototiles called stones and bones. We resolve two of his conjectures and prove some additional results that he left tacit. In order to solve these problems, we first transfer benzels into the square grid. One of our primary tools, which we combine with several new ideas, is a bijection (rediscovered by Stanton and White and often attributed to them although it is considerably older) between \(k\)-ribbon tableaux of certain skew shapes and certain \(k\)-tuples of Young tableaux.

Mathematics Subject Classifications: 05B45, 05A15, 05A17

Keywords: Tiling, benzel, abacus bijection, core partition, domino, stone, bone

This paper investigates isomorphisms of Bergman fans of matroids respecting different fan structures, which we regard as matroid analogs of birational maps. We show that isomorphisms respecting the fine fan structure are induced by matroid isomorphisms.

We introduce Cremona automorphisms of the coarse structure of Bergman fans, which are not induced by matroid automorphisms. We show that the automorphism group of the coarse fan structure is generated by matroid automorphisms and Cremona maps in the case of rank \(3\) matroids which are not parallel connections and for modularly complemented matroids.

Mathematics Subject Classifications: 14T20, 52B40, 14E07

Keywords: Matroids, birational geometry

A query game is a pair of a set \(Q\) of queries and a set \(\mathcal{F}\) of functions, or codewords \(f:Q\rightarrow \mathbb{Z}.\) We think of this as a two-player game. One player, Codemaker, picks a hidden codeword \(f\in \mathcal{F}\). The other player, Codebreaker, then tries to determine \(f\) by asking a sequence of queries \(q\in Q\), after each of which Codemaker must respond with the value \(f(q)\). The goal of Codebreaker is to uniquely determine \(f\) using as few queries as possible. Two classical examples of such games are coin-weighing with a spring scale, and Mastermind, which are of interest both as recreational games and for their connection to information theory.

In this paper, we will present a general framework for finding short solutions to query games. As applications, we give new self-contained proofs of the query complexity of variations of the coin-weighing problems, and prove new results that the deterministic query complexity of Mastermind with \(n\) positions and \(k\) colors is \(\Theta(n \log k/ \log n + k)\) if only black-peg information is provided, and \(\Theta(n \log k / \log n + k/n)\) if both black- and white-peg information is provided. In the deterministic setting, these are the first up to constant factor optimal solutions to Mastermind known for any \(k\geq n^{1-o(1)}\).

Mathematics Subject Classifications: 91A46, 68Q11, 05B99

Keywords: Combinatorial games, query complexity, Mastermind, coin-weighing