Combinatorial Theory

The aim of this note is to give a simplified proof of the induced version of the Ramsey theorem for vector spaces first proved by H. J. Prömel in 1986.

Mathematics Subject Classifications: 05D10, 15A03

Keywords: Ramsey theory, vector spaces

Given simple graphs \(X\) and \(Y\) on the same number of vertices, the friends-and-strangers graph \(\operatorname{FS}(X, Y)\) has as its vertices all bijections from \(V(X)\) to \(V(Y)\), where two bijections are adjacent if and only if they differ on two adjacent elements of \(V(X)\) with images adjacent in \(Y\). We study the diameters of connected components of friends-and-strangers graphs: the diameter of a component of \(\operatorname{FS}(X,Y)\) corresponds to the largest number of swaps necessary to go from one configuration in the component to another. We show that any component of \(\operatorname{FS}(\operatorname{Path}_n, Y)\) has \(O(n^2)\) diameter and that any component of \(\operatorname{FS}(\operatorname{Cycle}_n, Y)\) has \(O(n^4)\) diameter, improvable to \(O(n^3)\) whenever \(\operatorname{FS}(\operatorname{Cycle}_n, Y)\) is connected. Answering a question raised by Alon, Defant, and Kravitz in the negative, we use an explicit construction to show that there exist \(n\)-vertex graphs \(X\) and \(Y\) such that \(\operatorname{FS}(X,Y)\) has a component with \(e^{\Omega(n)}\) diameter. We conclude with several suggestions for future research.

Mathematics Subject Classifications: 05C12, 05C35, 05C38

Keywords: Friends-and-strangers graphs, diameter, extremal combinatorics, lower bounds, paths, cycles, token swapping, interchange process

A graph \(G\) is said to be ubiquitous, if every graph \(\Gamma\) that contains arbitrarily many disjoint \(G\)-minors automatically contains infinitely many disjoint \(G\)-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite graph is ubiquitous. In this paper we show that locally finite graphs admitting a certain type of tree-decomposition, which we call an extensive tree-decomposition, are ubiquitous. In particular this includes all locally finite graphs of finite tree-width, and also all locally finite graphs with finitely many ends, all of which have finite degree. It remains an open question whether every locally finite graph admits an extensive tree-decomposition.

Mathematics Subject Classifications: 05C83, 05C63

Keywords: Graph minors, infinite graphs, ubiquity

Stanley's theory of \((P,\omega)\)-partitions is a standard tool in combinatorics. It can be extended to allow for the presence of a restriction, that is a given maximal value for partitions at each vertex of the poset, as was shown by Assaf and Bergeron. Here we present a variation on their approach, which applies more generally. The enumerative side of the theory is more naturally expressed in terms of back stable quasisymmetric functions. We study the space of such functions, following the work of Lam, Lee and Shimozono on back stable symmetric functions. As applications we describe a new basis for the ring of polynomials that we call forest polynomials. Additionally we give a signed multiplicity-free expansion for any monomial expressed in the basis of slide polynomials.

Mathematics Subject Classifications: 05E05, 06A07

Keywords: P-partitions, quasisymmetric functions, slide polynomials

In this paper we consider a family of projective embeddings of the geometry \(A_{n,\{1,n\}}(\mathbb{F})\) of point-hyperplanes flags of \(\mathrm{PG}(n,\mathbb{F})\). The natural embedding \(\varepsilon_{\mathrm{nat}}\) is one of them. It maps every point-hyperplane flag \((p,H)\) onto the vector-line \(\langle {\bf x}\otimes\xi\rangle\), where \({\bf x}\) is a representative vector of \(p\) and \(\xi\) is a linear functional describing \(H\). The other embeddings have been discovered more than two decads ago by Thas and Van Maldeghem for the case \(n = 2\) and recently generalized to any \(n\) by De Schepper, Schillewaert and Van Maldeghem. They are obtained as twistings of \(\varepsilon_{\mathrm{nat}}\) by non-trivial automorphisms of \(\mathbb{F}\). Explicitly, for \(\sigma\in \mathrm{Aut}(\mathbb{F})\setminus\{\mathrm{id}_\mathbb{F}\}\), the twisting \(\varepsilon_\sigma\) of \(\varepsilon_{\mathrm{nat}}\) by \(\sigma\) maps \((p,H)\) onto \(\langle {\bf x}^\sigma\otimes \xi\rangle\). We shall prove that, when \(\mathrm{Aut}(\mathbb{F}) \neq \{\mathrm{id}_\mathbb{F}\}\), a geometric hyperplane \({\cal H}\) of \(A_{n,\{1,n\}}(\mathbb{F})\) arises from \(\varepsilon_{\mathrm{nat}}\) and at least one of its twistings or from at least two distinct twistings of \(\varepsilon_{\mathrm{nat}}\) if and only if \({\cal H} = \{(p,H)\in A_{n,\{1,n\}}(\mathbb{F}) \mid p\in A or a \in H\}\) for a possibly non-incident point-hyperplane pair \((a,A)\) of \(\mathrm{PG}(n,\mathbb{F})\). We call these hyperplanes quasi-singular hyperplanes. With the help of this result we shall prove that if \(|\mathrm{Aut}(\mathbb{F})| › 1\) then \(A_{n,\{1,n\}}(\mathbb{F})\) admits no absolutely universal embedding.

Mathematics Subject Classifications: 51A45, 20F40, 15A69

Keywords: Lie geometries, Segre varieties, embeddings, hyperplanes

We discover that tautological intersection numbers on \(\overline{\mathcal{M}}_{g, n}\), the moduli space of stable genus \(g\) curves with \(n\) marked points, are evaluations of Ehrhart polynomials of partial polytopal complexes. In order to prove this, we realize the Virasoro constraints for tautological intersection numbers as a recursion for integer-valued polynomials. Then we apply a theorem of Breuer that classifies Ehrhart polynomials of partial polytopal complexes by the nonnegativity of their \(f^*\)-vector. In dimensions 1 and 2, we show that the polytopal complexes that arise are inside-out polytopes i.e. polytopes that are dissected by a hyperplane arrangement.

Mathematics Subject Classifications: 14H10, 52B20

Keywords: Moduli of curves, Ehrhart polynomials

Let \(W\) be a Coxeter group and let \(\Phi^+\) be the positive roots. A subset \(B\) of \(\Phi^+\) is called "biclosed" if, whenever we have roots \(\alpha\), \(\beta\) and \(\gamma\) with \(\gamma \in \mathbb{R}_{›0} \alpha + \mathbb{R}_{›0} \beta\), if \(\alpha\) and \(\beta \in B\) then \(\gamma \in B\) and, if \(\alpha\) and \(\beta \not\in B\), then \(\gamma \not\in B\). The finite biclosed sets are the inversion sets of the elements of \(W\), and the containment between finite inversion sets is the weak order on \(W\). Dyer suggested studying the poset of all biclosed subsets of \(\Phi^+\), ordered by containment, and conjectured that it is a complete lattice. As progress towards Dyer's conjecture, we classify all biclosed sets in the affine root systems. We provide both a type uniform description, and concrete models in the classical types \(\widetilde{A}\), \(\widetilde{B}\), \(\widetilde{C}\), \(\widetilde{D}\). We use our models to prove that biclosed sets form a complete lattice in types \(\widetilde{A}\) and \(\widetilde{C}\), and we classify which biclosed sets are separable and which are weakly separable.

Mathematics Subject Classifications: 20F55, 17B22, 06B23

Keywords: Coxeter groups, root systems, affine Coxeter groups, lattice theory

We define a certain merging operation that given two \(d\)-polytopes \(P\) and \(Q\) such that \(P\) has a simplex facet and \(Q\) has a simple vertex produces a new \(d\)-polytope \(P \triangleright Q\) with \(f_0(P)+f_0(Q)-(d+1)\) vertices. We show that if for some \(1\leq i\leq d-1\), \(P\) and \(Q\) are \((d-i)\)-simplicial \(i\)-simple \(d\)-polytopes, then so is \(P \triangleright Q\). We then use this operation to construct new families of \((d-i)\)-simplicial \(i\)-simple \(d\)-polytopes. Specifically, we prove that for all \(2\leq i \leq d-2\leq 6\) with the exception of \((i,d)=(3,8)\) and \((5,8)\), there is an infinite family of \((d-i)\)-simplicial \(i\)-simple \(d\)-polytopes; furthermore, for all \(2\leq i\leq 4\), there is an infinite family of self-dual \(i\)-simplicial \(i\)-simple \(2i\)-polytopes. Finally, we show that for every \(d\geq 4\), there are \(2^{\Omega(N)}\) combinatorial types of \((d-2)\)-simplicial \(2\)-simple \(d\)-polytopes with at most \(N\) vertices.

Mathematics Subject Classifications: 52B05, 52B11

Keywords: Connected sums, face lattice, face numbers, Gosset-Elte polytopes, self-dual polytopes

The partition function of the Ising model of a graph \(G=(V,E)\) is defined as \(Z_{\operatorname{Ising}}(G;b)=\sum_{\sigma:V\to \{0,1\}} b^{m(\sigma)}\), where \(m(\sigma)\) denotes the number of edges \(e=\{u,v\}\) such that \(\sigma(u)=\sigma(v)\). We show that for any positive integer \(\Delta\) and any graph \(G\) of maximum degree at most \(\Delta\), \(Z_{\operatorname{Ising}}(G;b)\neq 0\) for all \(b\in \mathbb{C}\) satisfying \(|\frac{b-1}{b+1}| \leq \frac{1-o_\Delta(1)}{\Delta-1}\) (where \(o_\Delta(1) \to 0\) as \(\Delta\to \infty\)). This is optimal in the sense that \(\tfrac{1-o_\Delta(1)}{\Delta-1}\) cannot be replaced by \(\tfrac{c}{\Delta-1}\) for any constant \(c › 1\) subject to a complexity theoretic assumption.

To prove our result we use a standard reformulation of the partition function of the Ising model as the generating function of even sets. We establish a zero-free disk for this generating function inspired by techniques from statistical physics on partition functions of polymer models. Our approach is quite general and we discuss extensions of it to certain types of polymer models.

Mathematics Subject Classifications: 05C31, 82B20, 68W25

Keywords: Ising model, partition function, even set, polymer model, Fisher zeros, approximate counting

In a continuous-time quantum walk on a network of qubits, pretty good state transfer is the phenomenon of state transfer between two vertices with fidelity arbitrarily close to 1. We construct families of graphs to demonstrate that there is no bound on the size of a set of vertices that admits pretty good state transfer between any two vertices of the set.

Mathematics Subject Classifications: 05C50, 05C38

Keywords: Continuous-time quantum walks, pretty good state transfer

We introduce a new row insertion algorithm on decreasing tableaux and increasing tableaux, generalizing Edelman-Greene (EG) row insertion. Our row insertion algorithm is a nontrivial variation of Hecke column insertion which generalizes EG column insertion. Similar to Hecke column insertion, our row insertion is bijective and respects Hecke equivalence, and therefore recovers the expansions of stable Grothendieck functions into Grassmannian stable Grothendieck functions.

Mathematics Subject Classifications: 05E05

Keywords: Hecke insertion, Grothendieck polynomials

Generalizing results of Frucht and de Groot/Sabidussi, we demonstrate that every group-embeddable monoid is isomorphic to the bimorphism monoid of some graph.

Mathematics Subject Classifications: 05C63, 20M30

Keywords: Infinite graph theory, group-embeddable monoids, bimorphism monoids

The recently discovered "hat" aperiodic monotile mixes unreflected and reflected tiles in every tiling it admits, leaving open the question of whether a single shape can tile aperiodically using translations and rotations alone. We show that a close relative of the hat--the equilateral member of the continuum to which it belongs--is a weakly chiral aperiodic monotile: it admits only non-periodic tilings if we forbid reflections by fiat. Furthermore, by modifying this polygon's edges we obtain a family of shapes called Spectres that are strictly chiral aperiodic monotiles: they admit only homochiral non-periodic tilings based on a hierarchical substitution system.

Mathematics Subject Classifications: 05B45, 52C20, 05B50

Keywords: Tilings, aperiodic order, polyforms

We solve a conjecture from the first and third authors that claims that fully simple maps, which are maps with non self-intersecting disjoint boundaries, satisfy topological recursion for the exchanged spectral curve \((y, x)\), making use of the topological recursion for ciliated maps (building on a result from Belliard, Eynard, and the second and third authors).

Mathematics Subject Classifications: 05A15, 05A19, 46L54

Keywords: Maps, fully simple maps, enumeration, topological recursion

We introduce fluctuating tableaux, which subsume many classes of tableaux that have been previously studied, including (generalized) oscillating, vacillating, rational, alternating, standard, and transpose semistandard tableaux. Our main contribution is the introduction of promotion permutations and promotion matrices, which are new even for standard tableaux. We provide characterizations in terms of Bender-Knuth involutions, jeu de taquin, and crystals. We prove key properties in the rectangular case about the behavior of promotion permutations under promotion and evacuation. We also give a full development of the basic combinatorics and representation theory of fluctuating tableaux.

Our motivation comes from our companion paper, where we use these results in the development of a new rotation-invariant \(\operatorname{SL}_4\)-web basis. Basis elements are given by certain planar graphs and are constructed so that important algebraic operations can be performed diagrammatically. These planar graphs are indexed by fluctuating tableaux, tableau promotion corresponds to graph rotation, and promotion permutations correspond to key graphical information.

Mathematics Subject Classifications: 05E10, 05E18

Keywords: Tableaux, promotion, jeu de taquin, Bender-Knuth involutions, growth diagrams, crystals

We study the maximum multiplicity \(\mathcal{M}(k,n)\) of a simple transposition \(s_k=(k \: k+1)\) in a reduced word for the longest permutation \(w_0=n \: n-1 \: \cdots \: 2 \: 1\), a problem closely related to much previous work on sorting networks and on the "\(k\)-set" problem. After reinterpreting the problem in terms of monotone weakly separated paths, we show that, for fixed \(k\) and sufficiently large \(n\), the optimal density is realized by paths which are periodic in a precise sense, so that \[ \mathcal{M}(k,n)=c_k n + p_k(n) \] for a periodic function \(p_k\) and constant \(c_k\). In fact we show that \(c_k\) is always rational, and compute several bounds and exact values for this quantity with repeatable patterns, which we introduce.

Mathematics Subject Classifications: 05A05, 05A16, 05E99

Keywords: Reduced words, permutations, \(k\)-sets, wiring diagram, weakly separated

Defant recently introduced toric promotion, an operator that acts on the labelings of a graph \(G\) and serves as a cyclic analogue of Schützenberger's promotion operator. Toric promotion is defined as the composition of certain toggle operators, listed in a natural cyclic order. We consider more general permutoric promotion operators, which are defined as compositions of the same toggles, but in permuted orders. We settle a conjecture of Defant by determining the orders of all permutoric promotion operators when \(G\) is a path graph. In fact, we completely characterize the orbit structures of these operators, showing that they satisfy the cyclic sieving phenomenon. The first half of our proof requires us to introduce and analyze new broken promotion operators, which can be interpreted via globs of liquid gliding on a path graph. For the latter half of our proof, we reformulate the dynamics of permutoric promotion via stones sliding along a cycle graph and coins colliding with each other on a path graph.

Mathematics Subject Classifications: 05E18

Keywords: Promotion, toric promotion, Coxeter element, cyclic sieving phenomenon

Given a lattice path \(\nu\), the \(\nu\)-Tamari lattice and the \(\nu\)-Dyck lattice are two natural examples of partial order structures on the set of lattice paths that lie weakly above \(\nu\). In this paper, we introduce a more general family of lattices, called alt \(\nu\)-Tamari lattices, which contains these two examples as particular cases. Unexpectedly, we show that all these lattices have the same number of linear intervals.

Mathematics Subject Classifications: 06A07, 06B05, 05A19

Keywords: Lattices, intervals, Tamari