Combinatorial Theory

The classical hook length formula counts the number of standard tableaux of straight shapes. In 1996, Okounkov and Olshanski found a positive formula for the number of standard Young tableaux of a skew shape. We prove various properties of this formula, including three determinantal formulas for the number of nonzero terms, an equivalence between the Okounkov-Olshanski formula and another skew tableaux formula involving Knutson-Tao puzzles, and two $q$-analogues for reverse plane partitions, which complement work by Stanley and Chen for semistandard tableaux. We also give several reformulations of the formula, including two in terms of the excited diagrams appearing in a more recent skew tableaux formula by Naruse. Lastly, for thick zigzag shapes we show that the number of nonzero terms is given by a determinant of the Genocchi numbers and improve on known upper bounds by Morales-Pak-Panova on the number of standard tableaux of these shapes.

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

We study the intersection lattice of a hyperplane arrangement recently introduced by Hetyei who showed that the number of regions of the arrangement is a median Genocchi number. Using a different method, we refine Hetyei's result by providing a combinatorial interpretation of the coefficients of the characteristic polynomial of the intersection lattice of this arrangement. The Genocchi numbers count a class of permutations known as Dumont permutations and the median Genocchi numbers count the derangements in this class. We show that the signless coefficients of the characteristic polynomial count Dumont-like permutations with a given number of cycles. This enables us to derive formulas for the generating function of the characteristic polynomial, which reduce to known formulas for the generating functions of the Genocchi numbers and the median Genocchi numbers. As a byproduct of our work, we obtain new models for the Genocchi and median Genocchi numbers.

Mathematics Subject Classifications: 52C35 (Primary), 05A05, 05A15, 05B35, 06A07, 11B68 (Secondary)

In this paper we generalise the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. We define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then we show that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. Our main result is a precise characterisation of the class of non-even oriented cographic matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen.

Mathematics Subject Classifications: 05B35, 05C20, 05C70, 05C75, 05C83, 05C85, 52C40

Every nontrivial linear space embedded in a Pappian projective space such that the blocks of the linear space are projectively equivalent Baer sublines with respect to a separable quadratic field extension is either a Baer subspace, or a Hermitian unital.

Mathematics Subject Classifications: 51A45, 51E10

Kohnert proposed a formula for Schubert polynomials as the generating polynomial for certain unit cell diagrams obtained from the diagram of a permutation. Billey, Jockusch and Stanley proved a formula for Schubert polynomials as the generating polynomial for compatible sequences of reduced words. In this paper, we give an explicit bijection between these two models, thereby proving Kohnert's rule for Schubert polynomials.

Mathematics Subject Classifications: 05A05, 05A19, 14N10, 14N15

We introduce $\delta$-cliffs, a generalization of permutations and increasing trees depending on a range map $\delta$. We define a first lattice structure on these objects and we establish general results about its subposets. Among them, we describe sufficient conditions to have EL-shellable posets, lattices with algorithms to compute the meet and the join of two elements, and lattices constructible by interval doubling. Some of these subposets admit natural geometric realizations. Then, we introduce three families of subposets which, for some maps $\delta$, have underlying sets enumerated by the Fuss-Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. These three families of posets fit into a chain for the order extension relation and they share some properties. Finally, in the same way as the product of the Malvenuto-Reutenauer algebra forms intervals of the right weak Bruhat order of permutations, we construct algebras whose products form intervals of the lattices of $\delta$-cliff. We provide necessary and sufficient conditions on $\delta$ to have associative, finitely presented, or free algebras. We end this work by using the previous Fuss-Catalan posets to define quotients of our algebras of $\delta$-cliffs. In particular, one is a generalization of the Loday-Ronco algebra.

Mathematics Subject Classifications: 05E99, 06A07, 06A11, 16T30

The generating graph $\Gamma(G)$ of a finite group $G$ has vertex set the non-identity elements of $G$, with two elements adjacent exactly when they generate $G$. A coclique in a graph is an empty induced subgraph, so a coclique in $\Gamma(G)$ is a subset of $G$ such that no pair of elements generate $G$. A coclique is maximal if it is contained in no larger coclique. It is easy to see that the non-identity elements of a maximal subgroup of $G$ form a coclique in $\Gamma(G)$, but this coclique need not be maximal. In this paper we determine when the intransitive maximal subgroups of $\mathrm{S}_n$ and $\mathrm{A}_n$ are maximal cocliques in the generating graph. In addition, we prove a conjecture of Cameron, Lucchini, and Roney-Dougal in the case of $G = \mathrm{A}_n$ and $\mathrm{S}_n$, when $n$ is prime and ${n \neq \frac{q^d-1}{q-1}}$ for all prime powers $q$ and $d \geq 2$. Namely, we show that two elements of $G$ have identical sets of neighbours in $\Gamma(G)$ if and only if they belong to exactly the same maximal subgroups.

Mathematics Subject Classifications: 20D06, 05C25, 20B35

The independence complex $\mathrm{Ind}(G)$ of a graph $G$ is the simplicial complex formed by its independent sets of vertices. We introduce a deformation of the simplicial chain complex of $\mathrm{Ind}(G)$ that gives rise to a spectral sequence which contains on its first page the homology groups of the independence complexes of $G$ and various subgraphs of $G$, obtained by removing independent sets together with their neighborhoods. We show how this can be used to study the homology of $\mathrm{Ind}(G)$. Furthermore, a careful investigation of the sequence's first page exhibits a relation between the cardinality of maximal independent sets in $G$ and the vanishing of certain homology groups of independence complexes of subgraphs of $G$. We show that it holds for all paths and cycles.

Mathematics Subject Classifications: 05C69, 55U10

The Markoff injectivity conjecture states that $w\mapsto\mu(w)_{12}$ is injective on the set of Christoffel words where $\mu:\{\mathtt{0},\mathtt{1}\}^*\to\mathrm{SL}_2(\mathbb{Z})$ is a certain homomorphism and $M_{12}$ is the entry above the diagonal of a $2\times2$ matrix $M$. Recently, Leclere and Morier-Genoud (2021) proposed a $q$-analog $\mu_q$ of $\mu$ such that $\mu_{q}(w)_{12}|_{q=1}=\mu(w)_{12}$ is the Markoff number associated to the Christoffel word $w$ when evaluated at $q=1$. We show that there exists an order $<_{radix}$ on $\{\mathtt{0},\mathtt{1}\}^*$ such that for every balanced sequence $s \in \{\mathtt{0},\mathtt{1}\}^\mathbb{Z}$ and for all factors $u, v$ in the language of $s$ with $u <_{radix} v$, the difference $\mu_q(v)_{12} - \mu_q(u)_{12}$ is a nonzero polynomial of indeterminate $q$ with nonnegative integer coefficients. Therefore, the map $u\mapsto\mu_q(u)_{12}$ is injective over the language of a balanced sequence. The proof uses an equivalence between balanced sequences satisfying some Markoff property and indistinguishable asymptotic pairs.

Mathematics Subject Classifications: 11J06, 68R15, 05A30

Recall that an excedance of a permutation $\pi$ is any position $i$ such that $\pi_i > i$. Inspired by the work of Hopkins, McConville and Propp (Elec. J. Comb., 2017) on sorting using toppling, we say that a permutation is toppleable if it gets sorted by a certain sequence of toppling moves. One of our main results is that the number of toppleable permutations on $n$ letters is the same as those for which excedances happen exactly at $\{1,\dots, \lfloor (n-1)/2 \rfloor\}$. Additionally, we show that the above is also the number of acyclic orientations with unique sink (AUSOs) of the complete bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor + 1}$. We also give a formula for the number of AUSOs of complete multipartite graphs. We conclude with observations on an extremal question of Cameron et al. concerning maximizers of (the number of) acyclic orientations, given a prescribed number of vertices and edges for the graph.

Mathematics Subject Classifications: 05A19, 05A05, 05C30

Let $q$ be a prime power and $V\cong\mathbb{F}_q^d$. A $t$-$(d,k,\lambda)_q$ design, or simply a subspace design, is a pair $\mathcal{D}=(V,\mathcal{B})$, where $\mathcal{B}$ is a subset of the set of all $k$-dimensional subspaces of $V$, with the property that each $t$-dimensional subspace of $V$ is contained in precisely $\lambda$ elements of $\mathcal{B}$. Subspace designs are the $q$-analogues of balanced incomplete block designs. Such a design is called block-transitive if its automorphism group $\mathrm{Aut}(\mathcal{D})$ acts transitively on $\mathcal{B}$. It is shown here that if $t\geq 2$ and $\mathcal{D}$ is a block-transitive $t$-$(d,k,\lambda)_q$ design then $\mathcal{D}$ is trivial, that is, $\mathcal{B}$ is the set of all $k$-dimensional subspaces of $V$.

Mathematics Subject Classifications: 05E18, 05B99

We enumerate Hurwitz orbits of shortest reflection factorizations of an arbitrary element in the infinite family $G(m, p, n)$ of complex reflection groups. As a consequence, we characterize the elements for which the action is transitive and give a simple criterion to tell when two shortest reflection factorizations belong to the same Hurwitz orbit. We also characterize the quasi-Coxeter elements (those with a shortest reflection factorization that generates the whole group) in $G(m, p, n)$.

Mathematics Subject Classifications: 05A05, 05A15, 05E18, 20F55

The odd diagram of a permutation is a subset of the classical diagram with additional parity conditions. In this paper, we study classes of permutations with the same odd diagram, which we call odd diagram classes. First, we prove a conjecture relating odd diagram classes and 213- and 312-avoiding permutations. Secondly, we show that each odd diagram class is a Bruhat interval. Instrumental to our proofs is an explicit description of the Bruhat edges that link permutations in a class.

Mathematics Subject Classifications: 05A05, 05A15

We prove that the grades of simple modules indexed by boolean permutations, over the incidence algebra of the symmetric group with respect to the Bruhat order, are given by Lusztig's $\mathbf{a}$-function. Our arguments are combinatorial, and include a description of the intersection of two principal order ideals when at least one permutation is boolean. An important object in our work is a reduced word written as minimally many runs of consecutive integers, and one step of our argument shows that this minimal quantity is equal to the length of the second row in the permutation's shape under the Robinson-Schensted correspondence. We also prove that a simple module over the above-mentioned incidence algebra is perfect if and only if its index is the longest element of a parabolic subgroup.

Mathematics Subject Classifications: 20F55, 06A07, 05E15

Let $P$ be a graded poset of rank $r$ and let $\mathbf{c}$ be a $c$-element chain. A plane partition on $P$ is an order ideal of $P \times \mathbf{c}$. For an order ideal $I$ of $P \times \mathbf{c}$, its rowmotion $\psi(I)$ is the smallest ideal containing the minimal elements of the complementary filter of $I$. The map $\psi$ defines invertible dynamics on the set of plane partitions. We say that $P$ has NRP (`not relatively prime') rowmotion if no $\psi$-orbit has cardinality relatively prime to $r+c+1$. In recent work, R. Patrias and the author (2020) proved a 1995 conjecture of P. Cameron and D. Fon-Der-Flaass by establishing NRP rowmotion for the product $P = \mathbf{a} \times \mathbf{b}$ of two chains, the poset whose order ideals correspond to the Schubert varieties of a Grassmann variety $\mathrm{Gr}_a(\mathbb{C}^{a+b})$ under containment. Here, we initiate the general study of posets with NRP rowmotion. Our first main result establishes NRP rowmotion for all minuscule posets $P$, posets whose order ideals reflect the Schubert stratification of minuscule flag varieties. Our second main result is that NRP rowmotion depends only on the isomorphism class of the comparability graph of $P$.

Mathematics Subject Classifications: 05E18, 06A07, 06D99

Motivated by the study of singular values of random rectangular matrices, we define and study the rectangular additive convolution of polynomials with nonnegative real roots. Our definition directly generalizes the asymmetric additive convolution introduced by Marcus, Spielman and Srivastava (2015), and our main theorem gives the corresponding generalization of the bound on the largest root from that paper. The main tool used in the analysis is a differential operator derived from the "rectangular Cauchy transform" introduced by Benaych-Georges (2009). The proof is inductive, with the base case requiring a new nonasymptotic bound on the Cauchy transform of Gegenbauer polynomials which may be of independent interest.

Mathematics Subject Classifications: 26C10, 33C45

A word is square-free if it does not contain any square (a word of the form $XX$), and is extremal square-free if it cannot be extended to a new square-free word by inserting a single letter at any position. Grytczuk, Kordulewski, and Niewiadomski proved that there exist infinitely many ternary extremal square-free words. We establish that there are no extremal square-free words over any alphabet of size at least $17$.

Mathematics Subject Classifications: 05A05, 05D10, 68R15

Given an essential semilattice congruence $\equiv$ on the left weak order of a \linebreak Coxeter group $W$, we define the Coxeter stack-sorting operator ${\bf S}_\equiv:W\to W$ by ${{\bf S}_\equiv(w)=w\big(\pi_\downarrow^\equiv(w)\big)^{-1}}$, where $\pi_\downarrow^\equiv(w)$ is the unique minimal element of the congruence class of $\equiv$ containing $w$. When $\equiv$ is the sylvester congruence on the symmetric group $S_n$, the operator ${\bf S}_\equiv$ is West's stack-sorting map. When $\equiv$ is the descent congruence on $S_n$, the operator ${\bf S}_\equiv$ is the pop-stack-sorting map. We establish several general results about Coxeter stack-sorting operators, especially those acting on symmetric groups. For example, we prove that if $\equiv$ is an essential lattice congruence on $S_n$, then every permutation in the image of ${\bf S}_\equiv$ has at most $\left\lfloor\frac{2(n-1)}{3}\right\rfloor$ right descents; we also show that this bound is tight. We then introduce analogues of permutree congruences in types $B$ and $\widetilde A$ and use them to isolate Coxeter stack-sorting operators $\mathtt{s}_B$ and $\widetilde{\mathtt{s}}$ that serve as canonical type-$B$ and type-$\widetilde A$ counterparts of West's stack-sorting map. We prove analogues of many known results about West's stack-sorting map for the new operators $\mathtt{s}_B$ and $\widetilde{\mathtt{s}}$. For example, in type $\widetilde A$, we obtain an analogue of Zeilberger's classical formula for the number of $2$-stack-sortable permutations in $S_n$.

Mathematics Subject Classifications: 06A12, 06B10, 37E15, 05A05, 05E16