Combinatorial Theory

Editorial

We consider families of \(k\)-subsets of \(\{1, \dots, n\}\), where \(n\) is a multiple of \(k\), which have no perfect matching. An equivalent condition for a family \(\mathcal{F}\) to have no perfect matching is for there to be a blocking set, which is a set of \(b\) elements of \(\{1, \dots, n\}\) that cannot be covered by \(b\) disjoint sets in \(\mathcal{F}\). We are specifically interested in the largest possible size of a family \(\mathcal{F}\) with no perfect matching and no blocking set of size less than \(b\). Frankl resolved the case of families with no singleton blocking set (in other words, the \(b=2\) case) for sufficiently large \(n\) and conjectured an optimal construction for general \(b\). Though Frankl's construction fails to be optimal for \(k = 2, 3\), we show that the construction is optimal whenever \(k \ge 100\) and \(n\) is sufficiently large.

Mathematics Subject Classifications: 05D05

In the 1970s, William Tutte developed a clever algebraic approach, based on certain "invariants", to solve a functional equation that arises in the enumeration of properly colored triangulations. The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past 20 years to a rich collection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps, taken in \(\{-1, 0,1\}^2\).

We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic. This includes Gessel's famous model, and the first proof ever found for one model with weighted steps. To be applicable, the method requires the existence of two rational functions called invariant and decoupling function respectively. When they exist, algebraicity follows almost automatically.

Then, we move to a complex analytic viewpoint that has already proved very powerful, leading in particular to integral expressions for the generating function in the non-D-finite cases, as well as to proofs of non-D-finiteness. We develop in this context a weaker notion of invariant. Now all quadrant models have invariants, and for those that have in addition a decoupling function, we obtain integral-free expressions for the generating function, and a proof that this series is D-algebraic (that is, satisfies polynomial differential equations).

Keywords: Lattice walks, enumeration, differentially algebraic series, conformal mappings.

Mathematics Subject Classifications: 05A15, 34K06, 39A06, 30C20, 30D05

A Kakeya set \(S \subset (\mathbb{Z}/N\mathbb{Z})^n\) is a set containing a line in each direction. We show that, when \(N\) is any square-free integer, the size of the smallest Kakeya set in \((\mathbb{Z}/N\mathbb{Z})^n\) is at least \(C_{n,\epsilon} N^{n - \epsilon}\) for any \(\epsilon\) -- resolving a special case of a conjecture of Hickman and Wright. Previously, such bounds were only known for the case of prime \(N\). We also show that the case of general \(N\) can be reduced to lower bounding the \(\mathbb{F}_p\) rank of the incidence matrix of points and hyperplanes over \((\mathbb{Z}/p^k\mathbb{Z})^n\).

Mathematics Subject Classifications: 05B20, 05B25

We show that every structurally submodular separation system admits a canonical tree set which distinguishes its tangles.

Mathematics Subject Classifications: 05C40, 05C83, 06A07

Given graphs \(X\) and \(Y\) with vertex sets \(V(X)\) and \(V(Y)\) of the same cardinality, we define a graph \(\mathsf{FS}(X,Y)\) whose vertex set consists of all bijections \(\sigma\colon V(X)\to V(Y)\), where two bijections \(\sigma\) and \(\sigma'\) are adjacent if they agree everywhere except for two adjacent vertices \(a,b \in V(X)\) such that \(\sigma(a)\) and \(\sigma(b)\) are adjacent in \(Y\). This setup, which has a natural interpretation in terms of friends and strangers walking on graphs, provides a common generalization of Cayley graphs of symmetric groups generated by transpositions, the famous \(15\)-puzzle, generalizations of the \(15\)-puzzle as studied by Wilson, and work of Stanley related to flag \(h\)-vectors. We derive several general results about the graphs \(\mathsf{FS}(X,Y)\) before focusing our attention on some specific choices of \(X\). When \(X\) is a path graph, we show that the connected components of \(\mathsf{FS}(X,Y)\) correspond to the acyclic orientations of the complement of \(Y\). When \(X\) is a cycle, we obtain a full description of the connected components of \(\mathsf{FS}(X,Y)\) in terms of toric acyclic orientations of the complement of \(Y\). We then derive various necessary and/or sufficient conditions on the graphs \(X\) and \(Y\) that guarantee the connectedness of \(\mathsf{FS}(X,Y)\). Finally, we raise several promising further questions.

Mathematics Subject Classifications: 05C40, 05C38, 05A05

We prove several new instances of the cyclic sieving phenomenon (CSP) on Catalan objects of type \(A\) and type \(B\). Moreover, we refine many of the known instances of the CSP on Catalan objects. For example, we consider triangulations refined by the number of "ears", non-crossing matchings with a fixed number of short edges, and non-crossing configurations with a fixed number of loops and edges.

Keywords: Dyck paths, cyclic sieving, Narayana numbers, major index, q-analog.

Mathematics Subject Classifications: 05E18, 05A19, 05A30

We define \(P\)-strict labelings for a finite poset \(P\) as a generalization of semistandard Young tableaux and show that promotion on these objects is in equivariant bijection with a toggle action on \(B\)-bounded \(Q\)-partitions of an associated poset \(Q\). In many nice cases, this toggle action is conjugate to rowmotion. We apply this result to flagged tableaux, Gelfand--Tsetlin patterns, and symplectic tableaux, obtaining new cyclic sieving and homomesy conjectures. We also show \(P\)-strict promotion can be equivalently defined using Bender--Knuth and jeu de taquin perspectives.

Mathematics Subject Classifications: 05A19, 05E18

Symmetric edge polytopes \(\mathcal{A}_G\) of type A are lattice polytopes arising from the root system \(A_n\) and finite simple graphs \(G\). There is a connection between \(\mathcal{A}_G\) and the Kuramoto synchronization model in physics. In particular, the normalized volume of \(\mathcal{A}_G\) plays a central role. In the present paper, we focus on a particular class of graphs. In fact, for any cactus graph \(G\), we give a formula for the \(h^*\)-polynomial of \(\mathcal{A}_{\widehat{G}}\) by using matching generating polynomials, where \(\widehat{G}\) is the suspension of \(G\). This gives also a formula for the normalized volume of \(\mathcal{A}_{\widehat{G}}\). Moreover, via methods from chemical graph theory, we show that for any cactus graph \(G\), the \(h^*\)-polynomial of \(\mathcal{A}_{\widehat{G}}\) is real-rooted. Finally, we extend the discussion to symmetric edge polytopes of type \(B\), which are lattice polytopes arising from the root system \(B_n\) and finite simple graphs.

Keywords: Symmetric edge polytope, \(h^*\)-polynomial, interior polynomial, matching generating polynomial, \(\mu\)-polynomial, real-rooted, \(\gamma\)-positive.

Mathematics Subject Classifications: 05A15, 05C31, 13P10, 52B12, 52B20

We use intermediate symplectic characters to give a proof and variations of Hopkins' conjecture, now proved by Hopkins and Lai, on the number of shifted plane partitions of shifted double staircase shape with bounded entries. In fact, we prove some character identities involving intermediate symplectic characters, and find generating functions for such shifted plane partitions. The key ingredients of the proof are a bialternant formula for intermediate symplectic characters, which interpolates between those for Schur functions and symplectic characters, and the Ishikawa--Wakayama minor-summation formula.

Keywords: Intermediate symplectic characters, shifted plane partitions, minor-summation formula, Pfaffian .

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

In this paper we formulate a conjecture about the crystal structures on Feigin--Fourier--Littelmann--Vinberg (FFLV) polytopes and prove it in small rank examples. In the case of multiples of a fundamental weight this approach recovers the crystal structures defined by Kus. A key step in this approach is the realisation of FFLV polytopes as Minkowski sums of Lusztig polytopes associated to different reduced words.

Keywords: Crystal structure, Lusztig polytope, FFLV polytope.

Mathematics Subject Classifications: 05E10, 17B10

An \(r\)-uniform tight cycle of length \(\ell>r\) is a hypergraph with vertices \(v_1,\dots,v_\ell\) and edges \(\{v_i,v_{i+1},\dots,v_{i+r-1}\}\) (for all \(i\)), with the indices taken modulo \(\ell\). It was shown by Sudakov and Tomon that for each fixed \(r\geq 3\), an \(r\)-uniform hypergraph on \(n\) vertices which does not contain a tight cycle of any length has at most \(n^{r-1+o(1)}\) hyperedges, but the best known construction (with the largest number of edges) only gives \(\Omega(n^{r-1})\) edges. In this note we prove that, for each fixed \(r\geq 3\), there are \(r\)-uniform hypergraphs with \(\Omega(n^{r-1}\log n/\log\log n)\) edges which contain no tight cycles, showing that the \(o(1)\) term in the exponent of the upper bound is necessary.

Mathematics Subject Classifications: 05C65, 05C38

In 1993 Stanley showed that if a simplicial complex is acyclic over some field, then its face poset can be decomposed into disjoint rank \(1\) boolean intervals whose minimal faces together form a subcomplex. Stanley further conjectured that complexes with a higher notion of acyclicity could be decomposed in a similar way using boolean intervals of higher rank. We provide an explicit counterexample to this conjecture. We also prove a version of the conjecture for boolean trees and show that the original conjecture holds when this notion of acyclicity is as high as possible.

Mathematics Subject Classifications: 05E45, 55U10

In recent years, Alexandersson and others proved combinatorial formulas for the Schur function expansion of the horizontal-strip LLT polynomial \(G_{\boldsymbol\lambda}(\boldsymbol x;q)\) in some special cases. We associate a weighted graph \(\Pi\) to \(\boldsymbol\lambda\) and we use it to express a linear relation among LLT polynomials. We apply this relation to prove an explicit combinatorial Schur-positive expansion of \(G_{\boldsymbol\lambda}(\boldsymbol x;q)\) whenever \(\Pi\) is triangle-free. We also prove that the largest power of \(q\) in the LLT polynomial is the total edge weight of our graph.

Keywords: Charge, chromatic symmetric function, cocharge, Hall--Littlewood polynomial, jeu de taquin, LLT polynomial, interval graph, Schur function, Schur-positive, symmetric function.

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

Uniformly describing the conjugacy classes of the unipotent upper triangular groups \(\mathrm{UT}_{n}(\mathbb{F}_{q})\) (for all or many values of \(n\) and \(q\)) is a nearly impossible task. This paper takes on the related problem of describing the normal subgroups of \(\mathrm{UT}_{n}(\mathbb{F}_{q})\). For \(q\) a prime, a bijection will be established between these subgroups and pairs of combinatorial objects with labels from \(\mathbb{F}_{q}^{\times}\). Each pair comprises a loopless binary matroid and a tight splice, an apparently new kind of combinatorial object which interpolates between nonnesting set partitions and shortened polyominoes. For arbitrary \(q\), the same approach describes a natural subset of normal subgroups: those which correspond to the ideals of the Lie algebra \(\mathfrak{ut}_{n}(\mathbb{F}_{q})\) under an approximation of the exponential map.

Keywords: Unipotent group, normal subgroup, Lie algebra ideal, nonnesting set partition, matroid, q-Stirling number.

Mathematics Subject Classifications: 05E16, 20G40, 17B45, 20E15

We prove an identity for Littlewood--Richardson coefficients conjectured by Pelletier and Ressayre. The proof relies on a novel birational involution defined over any semifield.

Keywords: Symmetric functions, Littlewood--Richardson coefficients, partitions, Schur functions, Schur polynomials, birational combinatorics, detropicalization, partitions.

Mathematics Subject Classifications: 05E05

We introduce a sharpened version of the well-known Lonely Runner Conjecture of Wills and Cusick. Given a real number \(x\), let \(\Vert x \Vert\) denote the distance from \(x\) to the nearest integer. For each set of positive integer speeds \(v_1, \dots, v_n\), we define the associated maximum loneliness to be $$\operatorname{ML}(v_1, \dots, v_n)=\max_{t \in \mathbb{R}}\min_{1 \leq i \leq n} \Vert tv_i \Vert.$$

The Lonely Runner Conjecture asserts that \(\operatorname{ML}(v_1, \dots, v_n) \geq 1/(n+1)\) for all choices of \(v_1, \dots, v_n\). We make the stronger conjecture that for each choice of \(v_1, \dots, v_n\), we have either \(\operatorname{ML}(v_1, \dots, v_n)=s/(ns+1)\) for some \(s \in \mathbb{N}\) or \(\operatorname{ML}(v_1, \dots, v_n) \geq 1/n\). This view reflects a surprising underlying rigidity of the Lonely Runner Problem. Our main results are: confirming our stronger conjecture for \(n \leq 3\); and confirming it for \(n=4\) and \(n=6\) in the case where one speed is much faster than the rest.

Mathematics Subject Classifications: 11K60 (primary), 11J13, 11J71, 52C07

A packing of partial difference sets is a collection of disjoint partial difference sets in a finite group \(G\). This configuration has received considerable attention in design theory, finite geometry, coding theory, and graph theory over many years, although often only implicitly. We consider packings of certain Latin square type partial difference sets in abelian groups having identical parameters, the size of the collection being either the maximum possible or one smaller. We unify and extend numerous previous results in a common framework, recognizing that a particular subgroup reveals important structural information about the packing. Identifying this subgroup allows us to formulate a recursive lifting construction of packings in abelian groups of increasing exponent, as well as a product construction yielding packings in the direct product of the starting groups. We also study packings of certain negative Latin square type partial difference sets of maximum possible size in abelian groups, all but one of which have identical parameters, and show how to produce such collections using packings of Latin square type partial difference sets.

Keywords: Finite abelian group, packing, partial difference set.

Mathematics Subject Classifications: 05B10, 20K01

Several recent papers have explored families of rational polyhedra whose integer points are in bijection with certain families of numerical semigroups. One such family, first introduced by Kunz, has integer points in bijection with numerical semigroups of fixed multiplicity, and another, introduced by Hellus and Waldi, has integer points corresponding to oversemigroups of numerical semigroups with two generators. In this paper, we provide a combinatorial framework from which to study both families of polyhedra. We introduce a new family of polyhedra called group cones, each constructed from some finite abelian group, from which both of the aforementioned families of polyhedra are directly determined but that are more natural to study from a standpoint of polyhedral geometry. We prove that the faces of group cones are naturally indexed by a family of finite posets, and illustrate how this combinatorial data relates to semigroups living in the corresponding faces of the other two families of polyhedra.

Keywords: Polyhedron, numerical semigroup.

Mathematics Subject Classifications: 52B05, 20M14

An automatic sequence is a letter-to-letter coding of a fixed point of a uniform morphism. More generally, morphic sequences are letter-to-letter codings of fixed points of arbitrary morphisms. There are many examples where an, a priori, morphic sequence with a non-uniform morphism happens to be an automatic sequence. An example is the Lysënok morphism \(a \to aca\), \(b \to d\), \(c \to b\), \(d \to c\), the fixed point of which is also a \(2\)-automatic sequence. Such an identification is useful for describing the dynamical systems generated by the fixed point. We give several ways to uncover such hidden automatic sequences, and present many examples. We focus in particular on morphisms associated with Grigorchuk groups.

Keywords: Morphic sequences, automatic sequences, Grigorchuk groups.

Mathematics Subject Classifications: 11B85, 68R15, 37B10