About
Combinatorial Theory is a mathematician-run journal, owned by its Editorial Board.
It is dedicated to open access publishing with no fees (no APCs) for authors or readers.
Volume 2, Issue 3, 2022
Research Articles
The bipermutahedron
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
Mathematics Subject Classifications: 52B20, 52B05, 05A15
Keywords: Polytope, bipermutahedron, bipermutations, descents,
- 1 supplemental ZIP
Inducibility and universality for trees
We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive
Mathematics Subject Classifications: 05C05, 05C35
Keywords: Trees, inducibility, graph density
- 1 supplemental ZIP
Polynomial removal lemmas for ordered graphs
A recent result of Alon, Ben-Eliezer and Fischer establishes an induced removal lemma for ordered graphs. That is, if
Mathematics Subject Classifications: 05C35, 05C75
Keywords: Ordered graph, removal lemma
- 1 supplemental ZIP
Schubert polynomials as projections of Minkowski sums of Gelfand-Tsetlin polytopes
Gelfand-Tsetlin polytopes are classical objects in algebraic combinatorics arising in the representation theory of
Mathematics Subject Classifications: 05E05
Keywords: Schubert polynomials, Gelfand-Tsetlin polytopes, flow polytopes
- 1 supplemental ZIP
Quasi-polar spaces
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
Mathematics Subject Classifications: 51E20
Keywords: Projective geometry, quadrics, hyperplanes, quasi-quadrics, intersection numbers
- 1 supplemental ZIP
Minimizing cycles in tournaments and normalized -norms
Akin to the Erdős-Rademacher problem, Linial and Morgenstern made the following conjecture in tournaments: for any
Mathematics Subject Classifications: 05C20, 05C35, 05C38
Keywords: Tournaments, cycles, spectrum
- 1 supplemental ZIP
Large expanders in high genus unicellular maps
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
- 1 supplemental ZIP
The polyhedral tree complex
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
- 1 supplemental ZIP
Intersecting psi-classes on tropical Hassett spaces
We study the intersection of tropical
Mathematics Subject Classifications: 14T90, 14N35
Keywords: Tropical intersection theory, Hassett spaces,
- 1 supplemental ZIP
Triangulations, Order Polytopes, and Generalized Snake Posets
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
- 1 supplemental ZIP
Pop-stack-sorting for Coxeter groups
Let
Mathematics Subject Classifications: 05E16, 37E15, 05A05
Keywords: Pop-stack-sorting, Coxeter group, weak order, Coxeter number, compulsive map, regular language
- 1 supplemental ZIP
Period collapse in Ehrhart quasi-polynomials of -graphs
A graph whose nodes have degree
Mathematics Subject Classifications: 05C30, 05C76, 52B20
Keywords: Ehrhart polynomials, period collapse
- 1 supplemental ZIP
Convex subspaces of Lie incidence geometries
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
- 1 supplemental ZIP
Labelled well-quasi-order for permutation classes
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
- 1 supplemental ZIP
Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
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
Mathematics Subject Classifications: 60C05, 05C80, 05C69, 05A05
Keywords: Combinatorial graph theory, combinatorial probability, cographs, random graphs, graphons, self-similarity
- 1 supplemental ZIP
Disjoint dijoins for classes of dicuts in finite and infinite digraphs
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
Mathematics Subject Classifications: 05C20, 05C70 (primary); 05C65, 05C63 (secondary)
Keywords: Woodall's conjecture, digraphs, directed cuts, dijoins, dijoin packing
- 1 supplemental ZIP