Combinatorial Theory

The harmonic polytope and the bipermutahedron are two related polytopes that arose in the Lagrangian geometry of matroids. We study the bipermutahedron. We show that it is a simple polytope whose faces are in bijection with the vertex-labeled and edge-labeled multigraphs with no isolated vertices; the generating function for its \(f\)-vector is a simple evaluation of the three variable Rogers-Ramanujan function. We introduce the biEulerian polynomial, which counts bipermutations according to their number of descents, and equals the \(h\)-polynomial of the bipermutahedral fan. We construct a unimodular triangulation of the product \(\Delta \times \cdots \times \Delta\) of triangles that is combinatorially equivalent to (the triple cone over) the bipermutahedral fan. Ehrhart theory then gives us a formula for the biEulerian polynomial, which we use to show that this polynomial is real-rooted and that the \(h\)-vector of the bipermutahedral fan is log-concave and unimodal. We describe all the deformations of the bipermutahedron; that is, the ample cone of the bipermutahedral toric variety. We prove that among all polytopes in this family, the bipermutahedron has the largest possible symmetry group. Finally, we show that the Minkowski quotient of the bipermutahedron and the harmonic polytope equals 2.

Mathematics Subject Classifications: 52B20, 52B05, 05A15

Keywords: Polytope, bipermutahedron, bipermutations, descents, \(f\)-vector, \(h\)-vector, unimodular triangulation, Ehrhart polynomial, real-rooted polynomial, deformation cone

We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive \(\varepsilon_1\) and \(\varepsilon_2\) such that every tree that is neither a path nor a star has inducibility at most \(1-\varepsilon_1\), where the inducibility of a tree \(T\) is defined as the maximum limit density of \(T\), and that there are infinitely many trees with inducibility at least \(\varepsilon_2\). Finally, we construct a universal sequence of trees; that is, a sequence in which the limit density of any tree is positive.

Mathematics Subject Classifications: 05C05, 05C35

Keywords: Trees, inducibility, graph density

A recent result of Alon, Ben-Eliezer and Fischer establishes an induced removal lemma for ordered graphs. That is, if \(F\) is an ordered graph and \(\varepsilon›0\), then there exists \(\delta_{F}(\varepsilon)›0\) such that every \(n\)-vertex ordered graph \(G\) containing at most \(\delta_{F}(\varepsilon) n^{v(F)}\) induced copies of \(F\) can be made induced \(F\)-free by adding/deleting at most \(\varepsilon n^2\) edges. We prove that \(\delta_{F}(\varepsilon)\) can be chosen to be a polynomial function of \(\varepsilon\) if and only if \(|V(F)|=2\), or \(F\) is the ordered graph with vertices \(x‹y‹z\) and edges \(\{x,y\},\{x,z\}\) (up to complementation and reversing the vertex order). We also discuss similar problems in the non-induced case.

Mathematics Subject Classifications: 05C35, 05C75

Keywords: Ordered graph, removal lemma

Gelfand-Tsetlin polytopes are classical objects in algebraic combinatorics arising in the representation theory of \(\mathfrak{gl}_n(\mathbb{C})\). The integer point transform of the Gelfand-Tsetlin polytope \(\mathrm{GT}(\lambda)\) projects to the Schur function \(s_{\lambda}\). Schur functions form a distinguished basis of the ring of symmetric functions; they are also special cases of Schubert polynomials \(\mathfrak{S}_{w}\) corresponding to Grassmannian permutations. For any permutation \(w \in S_n\) with column-convex Rothe diagram, we construct a polytope \(\mathcal{P}_{w}\) whose integer point transform projects to the Schubert polynomial \(\mathfrak{S}_{w}\). Such a construction has been sought after at least since the construction of twisted cubes by Grossberg and Karshon in 1994, whose integer point transforms project to Schubert polynomials \(\mathfrak{S}_{w}\) for all \(w \in S_n\). However, twisted cubes are not honest polytopes; rather one can think of them as signed polytopal complexes. Our polytope \(\mathcal{P}_{w}\) is a convex polytope, namely it is a Minkowski sum of Gelfand-Tsetlin polytopes of varying sizes. When the permutation \(w\) is Grassmannian, the Gelfand-Tsetlin polytope is recovered. We conclude by showing that the Gelfand-Tsetlin polytope is a flow polytope.

Mathematics Subject Classifications: 05E05

Keywords: Schubert polynomials, Gelfand-Tsetlin polytopes, flow polytopes

Quasi-polar spaces are sets of points having the same intersection numbers with respect to hyperplanes as classical polar spaces. Non-classical examples of quasi-quadrics have been constructed using a technique called {\em pivoting} in a paper by De Clerck, Hamilton, O'Keefe and Penttila. We introduce a more general notion of pivoting, called switching, and also extend this notion to Hermitian polar spaces. The main result of this paper studies the switching technique in detail by showing that, for \(q\geq 4\), if we modify the points of a hyperplane of a polar space to create a quasi-polar space, the only thing that can be done is pivoting. The cases \(q=2\) and \(q=3\) play a special role for parabolic quadrics and are investigated in detail. Furthermore, we give a construction for quasi-polar spaces obtained from pivoting multiple times. Finally, we focus on the case of parabolic quadrics in even characteristic and determine under which hypotheses the existence of a nucleus (which was included in the definition given in the De Clerck-Hamilton-O'Keefe-Penttila paper) is guaranteed.

Mathematics Subject Classifications: 51E20

Keywords: Projective geometry, quadrics, hyperplanes, quasi-quadrics, intersection numbers

Akin to the Erdős-Rademacher problem, Linial and Morgenstern made the following conjecture in tournaments: for any \(d\in (0,1]\), among all \(n\)-vertex tournaments with \(d\binom{n}{3}\) many 3-cycles, the number of 4-cycles is asymptotically minimized by a special random blow-up of a transitive tournament. Recently, Chan, Grzesik, Král' and Noel introduced spectrum analysis of adjacency matrices of tournaments in this study, and confirmed this for \(d\geq 1/36\). In this paper, we investigate the analogous problem of minimizing the number of cycles of a given length. We prove that for integers \(\ell\not\equiv 2\mod 4\), there exists some constant \(c_\ell>0\) such that if \(d\geq 1-c_\ell\), then the number of \(\ell\)-cycles is also asymptotically minimized by the same extremal examples. In doing so, we answer a question of Linial and Morgenstern about minimizing the \(q\)-norm of a probabilistic vector with given \(p\)-norm for integers \(q>p>1\). For integers \(\ell\equiv 2\mod 4\), however the same phenomena do not hold for \(\ell\)-cycles, for which we can construct an explicit family of tournaments containing fewer \(\ell\)-cycles for any given number of \(3\)-cycles. We propose two conjectures concerning the minimization problem for general cycles.

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

Keywords: Tournaments, cycles, spectrum

We study large uniform random maps with one face whose genus grows linearly with the number of edges. They can be seen as a model of discrete hyperbolic geometry. In the past, several of these hyperbolic geometric features have been discovered, such as their local limit or their logarithmic diameter. In this work, we show that with high probability such a map contains a very large induced subgraph that is an expander.

Mathematics Subject Classifications: 05C10, 05C48, 60C05, 60D05

Keywords: Combinatorial maps, high genus, expander graphs

The tree complex is a simplicial complex defined in recent work of Belk, Lanier, Margalit, and Winarski with applications to mapping class groups and complex dynamics. This article introduces a connection between this setting and the convex polytopes known as associahedra and cyclohedra. Specifically, we describe a characterization of these polytopes using planar embeddings of trees and show that the tree complex is the barycentric subdivision of a polyhedral cell complex for which the cells are products of associahedra and cyclohedra.

Mathematics Subject Classifications: 05C05, 05C10, 20F65, 52B11

Keywords: Associahedra, cyclohedra, planar trees, mapping class groups

We study the intersection of tropical \(\psi\)-classes on tropical heavy/light Hassett spaces, generalising a result of Kerber-Markwig for \(M^{\operatorname{trop}}_{0, n}\). Our computation reveals that the weight of a maximal cone in an intersection has a combinatorial intepretation in terms of the underlying tropical curve and it is always nonnegative. In particular, our result specialises to that, in top dimension, the tropical intersection product coincides with its classical counterpart.

Mathematics Subject Classifications: 14T90, 14N35

Keywords: Tropical intersection theory, Hassett spaces, \(\psi\)-classes

This work regards the order polytopes arising from the class of generalized snake posets and their posets of meet-irreducible elements. Among generalized snake posets of the same rank, we characterize those whose order polytopes have minimal and maximal volume. We give a combinatorial characterization of the circuits in related order polytopes and then conclude that all of their triangulations are unimodular. For a generalized snake word, we count the number of flips for the canonical triangulation of these order polytopes. We determine that the flip graph of the order polytope of the poset whose lattice of upper order ideals comes from a ladder is the Cayley graph of a symmetric group. Lastly, we introduce an operation on triangulations called twists and prove that twists preserve regular triangulations.

Mathematics Subject Classifications: 52B20, 52B05, 52B12, 06A07

Keywords: Order polytopes, triangulations, flow polytopes, circuits

Let \(W\) be an irreducible Coxeter group. We define the Coxeter pop-stack-sorting operator \(\mathsf{Pop}:W\to W\) to be the map that fixes the identity element and sends each nonidentity element \(w\) to the meet of the elements covered by \(w\) in the right weak order. When \(W\) is the symmetric group \(S_n\), \(\mathsf{Pop}\) coincides with the pop-stack-sorting map. Generalizing a theorem about the pop-stack-sorting map due to Ungar, we prove that \[\sup\limits_{w\in W}\left|O_{\mathsf{Pop}}(w)\right|=h,\] where \(h\) is the Coxeter number of \(W\) (with \(h=\infty\) if \(W\) is infinite) and \(O_f(w)\) denotes the forward orbit of \(w\) under a map \(f\). When \(W\) is finite, this result is equivalent to the statement that the maximum number of terms appearing in the Brieskorn normal form of an element of \(W\) is \(h-1\). More generally, we define a map \(f:W\to W\) to be compulsive if for every \(w\in W\), \(f(w)\) is less than or equal to \(\mathsf{Pop}(w)\) in the right weak order. We prove that if \(f\) is compulsive, then \(\sup\limits_{w\in W}|O_f(w)|\leq h\). This result is new even for symmetric groups. We prove that \(2\)-pop-stack-sortable elements in type \(B\) are in bijection with \(2\)-pop-stack-sortable permutations in type \(A\), which were enumerated by Pudwell and Smith. Claesson and Gu{\dh}mundsson proved that for each fixed nonnegative integer \(t\), the generating function that counts \(t\)-pop-stack-sortable permutations in type \(A\) is rational; we establish analogous results in types \(B\) and \(\widetilde A\).

Mathematics Subject Classifications: 05E16, 37E15, 05A05

Keywords: Pop-stack-sorting, Coxeter group, weak order, Coxeter number, compulsive map, regular language

A graph whose nodes have degree \(1\) or \(3\) is called a \(\{1,3\}\)-graph. Liu and Osserman associated a polytope to each \(\{1,3\}\)-graph and studied the Ehrhart quasi-polynomials of these polytopes. They showed that the vertices of these polytopes have coordinates in the set \(\{0,\frac14,\frac12,1\}\), which implies that the period of their Ehrhart quasi-polynomials is either \(1, 2\), or \(4\). We show that the period of the Ehrhart quasi-polynomial of these polytopes is 2 if the graph is a tree, the period is at most 2 if the graph is cubic, and the period is \(4\) otherwise. In the process of proving this theorem, several interesting combinatorial and geometric properties of these polytopes were uncovered, arising from the structure of their associated graphs. The tools developed here may find other applications in the study of Ehrhart quasi-polynomials and enumeration problems for other polytopes that arise from graphs. Additionally, we have identified some interesting connections with triangulations of 3-manifolds.

Mathematics Subject Classifications: 05C30, 05C76, 52B20

Keywords: Ehrhart polynomials, period collapse

We classify the convex subspaces of all hexagonic Lie incidence geometries (among which all long root geometries of spherical Tits-buildings). We perform a similar classification for most other Lie incidence geometries of spherical Tits-buildings, in particular for all projective and polar Grassmannians, and for exceptional Grassmannians of diameter at most 3.

Mathematics Subject Classifications: 51E24

Keywords: Buildings, parapolar spaces, long root geometries, hexagonal Lie incidence geometries

While the theory of labelled well-quasi-order has received significant attention in the graph setting, it has not yet been considered in the context of permutation patterns. We initiate this study here, and show how labelled well quasi order provides a lens through which to view and extend previous well-quasi-order results in the permutation patterns literature. Connections to the graph setting are emphasised throughout. In particular, we establish that a permutation class is labelled well-quasi-ordered if and only if its corresponding graph class is also labelled well-quasi-ordered.

Mathematics Subject Classifications: 05A05, 06A07

Keywords: Labelled well-quasi-order, permutation patterns, well-quasi-order

This paper is interested in independent sets (or equivalently, cliques) in uniform random cographs. We also study their permutation analogs, namely, increasing subsequences in uniform random separable permutations. First, we prove that, with high probability as \(n\) gets large, the largest independent set in a uniform random cograph with \(n\) vertices has size \(o(n)\). This answers a question of Kang, McDiarmid, Reed and Scott. Using the connection between graphs and permutations via inversion graphs, we also give a similar result for the longest increasing subsequence in separable permutations. These results are proved using the self-similarity of the Brownian limits of random cographs and random separable permutations, and actually apply more generally to all families of graphs and permutations with the same limit. Second, and unexpectedly given the above results, we show that for \(\beta >0\) sufficiently small, the expected number of independent sets of size \(\beta n\) in a uniform random cograph with \(n\) vertices grows exponentially fast with \(n\). We also prove a permutation analog of this result. This time the proofs rely on singularity analysis of the associated bivariate generating functions.

Mathematics Subject Classifications: 60C05, 05C80, 05C69, 05A05

Keywords: Combinatorial graph theory, combinatorial probability, cographs, random graphs, graphons, self-similarity

A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of a set of edges meeting every non-empty dicut equals the maximum number of disjoint dicuts in that digraph. Such sets are called dijoins. Woodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a directed graph equals the minimum size of a non-empty dicut. We study a modification of this question where we restrict our attention to certain classes of non-empty dicuts, i.e. whether for a class \(\mathfrak{B}\) of dicuts of a directed graph the maximum number of disjoint sets of edges meeting every dicut in \(\mathfrak{B}\) equals the size of a minimum dicut in \(\mathfrak{B}\). In particular, we verify this questions for nested classes of finite dicuts, for the class of dicuts of minimum size, and for classes of infinite dibonds, and we investigate how this generalised setting relates to a capacitated version of this question.

Mathematics Subject Classifications: 05C20, 05C70 (primary); 05C65, 05C63 (secondary)

Keywords: Woodall's conjecture, digraphs, directed cuts, dijoins, dijoin packing