Combinatorial Theory

By Foissy's work, the bidendriform structure of the Word Quasisymmetric Functions Hopf algebra (WQSym) implies that it is isomorphic to its dual. However, the only known explicit isomorphism due to Vargas does not respect the bidendriform structure. This structure is entirely determined by so-called totally primitive elements (elements such that the two half-coproducts vanish). In this paper, we construct two bases indexed by two new combinatorial families called red (dual side) and blue (primal side) biplane forests in bijection with packed words. In those bases, primitive elements are indexed by biplane trees and totally primitive elements by a certain subset of trees. We carefully combine red and blue forests to get bicolored forests. A simple recoloring of the edges allows us to obtain the first explicit bidendriform automorphism of WQSym.

Mathematics Subject Classifications: 05A05, 05A19, 05E05, 05E18

Keywords: Bidendriform Hopf algebras, Word Quasisymmetric Functions, packed words, permutation, primitive elements, duality, tree, forest, global descents

The torus $T$ of projective space also acts on the Hilbert scheme of subschemes of projective space. The $T$-graph of the Hilbert scheme has vertices the fixed points of this action, and edges connecting pairs of fixed points in the closure of a one-dimensional orbit. In general this graph depends on the underlying field. We construct a subgraph, which we call the spine, of the $T$-graph of ${\mathrm{Hilb}}^m({\mathbb{A}}^2)$ that is independent of the choice of infinite field. For certain edges in the spine we also give a description of the tropical ideal, in the sense of tropical scheme theory, of a general ideal in the edge. This gives a more refined understanding of these edges, and of the tropical stratification of the Hilbert scheme.

Mathematics Subject Classifications: 14C05, 14T10, 14L30

Keywords: Hilbert scheme, $T$-graph, tropical ideal

We give a complete combinatorial characterization of weakly $d$-Tverberg complexes. These complexes record which intersection combinatorics of convex hulls necessarily arise in any sufficiently large general position point set in ${\mathbb{R}}^d$. This strengthens the concept of $d$-representable complexes, which describe intersection combinatorics that arise in at least one point set. Our characterization allows us to construct for every fixed $d$ a graph that is not weakly $d^{\prime }$-Tverberg for any $d^{\prime }\le d$, answering a question of De Loera, Hogan, Oliveros, and Yang.

Mathematics Subject Classifications: 52A35, 52C45

Keywords: Tverberg's theorem, word representable, $d$-representable, nerve, general position, strong general position, fully independent

In this note, we give short proofs of three theorems about intersection problems. The first one is a determination of the maximum size of a nontrivial $k$-uniform, $d$-wise intersecting family for $n\ge (1+\frac{d}{2})(k-d+2)$, which improves the range of $n$ of a recent result of O'Neill and Verstraëte. Our proof also extends to $d$-wise, $t$-intersecting families, and from this result we obtain a version of the Erdős-Ko-Rado theorem for $d$-wise, $t$-intersecting families.

Our second result partially proves a conjecture of Frankl and Tokushige about $k$-uniform families with restricted pairwise intersection sizes.

Our third result is about intersecting families of graphs. Answering a question of Ellis, we construct $K_{s,t}$-intersecting families of graphs which have size larger than the Erdős-Ko-Rado-type construction, whenever $t$ is sufficiently large in terms of $s$. The construction is based on nontrivial $(2s)$-wise $t$-intersecting families of sets.

Mathematics Subject Classifications: 05D05, 05D99

Keywords: Nontrivial intersecting family, Hilton-Milner, forbidden intersection, graph intersection

We consider a greedy version of the $m$-Tamari order defined on $m$-Dyck paths, recently introduced by Dermenjian. Inspired by intriguing connections between intervals in the ordinary {1-}Tamari order and planar triangulations, and more generally by the existence of simple formulas counting intervals in the ordinary $m$-Tamari orders, we investigate the number of intervals in the greedy order on $m$-Dyck paths of fixed size. We find again a simple formula, which also counts certain planar maps (of prescribed size) called $(m+1)$-constellations.

For instance, when $m=1$ the number of intervals in the greedy order on {1-}Dyck paths of length $2n$ is proved to be $\frac{3\cdot 2^{n-1}}{(n+1)(n+2)}(\genfrac{}{}{0ex}{}{2n}{n})$, which is also the number of bipartite maps with $n$ edges.

Our approach is recursive, and uses a "catalytic" parameter, namely the length of the final descent of the upper path of the interval. The resulting bivariate generating function is algebraic for all $m$. We show that the same approach can be used to count intervals in the ordinary $m$-Tamari lattices as well. We thus recover the earlier result of Bousquet-Mélou, Fusy and Préville-Ratelle, who were using a different catalytic parameter.

Mathematics Subject Classifications: 05A15, 06A07, 06A11

Keywords: Tamari posets, planar maps, enumeration, algebraic generating functions

A longstanding open problem asks for an aperiodic monotile, also known as an "einstein": a shape that admits tilings of the plane, but never periodic tilings. We answer this problem for topological disk tiles by exhibiting a continuum of combinatorially equivalent aperiodic polygons. We first show that a representative example, the "hat" polykite, can form clusters called "metatiles", for which substitution rules can be defined. Because the metatiles admit tilings of the plane, so too does the hat. We then prove that generic members of our continuum of polygons are aperiodic, through a new kind of geometric incommensurability argument. Separately, we give a combinatorial, computer-assisted proof that the hat must form hierarchical--and hence aperiodic--tilings.

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

Keywords: Tilings, aperiodic order, polyforms

We address the maximum size of binary codes and binary constant weight codes with few distances. Previous works established a number of bounds for these quantities as well as the exact values for a range of small code lengths. As our main results, we determine the exact size of maximal binary codes with two distances for all lengths $n\ge 6$ as well as the exact size of maximal binary constant weight codes with $2$, $3$, and $4$ distances for several values of the weight and for all but small lengths.

Mathematics Subject Classifications: 52C10, 05D05, 94B65

Keywords: Johnson space, Erdös-Ko-Rado, Delsarte inequalities

A pair of planes, both projective or both affine, of the same order and on the same point set are orthogoval if each line of one plane intersects each line of the other plane in at most two points. In this paper we prove new constructions for sets of mutually orthogoval planes, both projective and affine, and review known results that are equivalent to sets of more than two mutually orthogoval planes. We also discuss the connection between sets of mutually orthogoval planes and covering arrays.

Mathematics Subject Classifications: 05B25, 05B40, 51E20, 51E21

Keywords: Finite geometry, projective planes, affine planes, covering arrays, orthogoval planes

We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. Specifically, for any $\gamma ›0$ and $k\ge 3$, we show that asymptotically almost surely, every subgraph of the binomial random $k$-uniform hypergraph $G^{(k)}(n,n^{\gamma -1})$ in which all $(k-1)$-sets are contained in at least $(\frac{1}{2}+2\gamma )pn$ edges has a tight Hamilton cycle. This is a cyclic ordering of the $n$ vertices such that each consecutive $k$ vertices forms an edge.

Mathematics Subject Classifications: 05C80, 05C35

Keywords: Random graphs, hypergraphs, tight Hamilton cycles, resilience

In this paper, we study the maximum adjacency spectral radii of graphs of large order that do not contain an even cycle of given length. For $n›k$, let $S_{n,k}$ be the join of a clique on $k$ vertices with an independent set of $n-k$ vertices and denote by $S_{n,k}^{+}$ the graph obtained from $S_{n,k}$ by adding one edge. In 2010, Nikiforov conjectured that for $n$ large enough, the $C_{2k+2}$-free graph of maximum spectral radius is $S_{n,k}^{+}$ and that the $\{C_{2k+1},C_{2k+2}\}$-free graph of maximum spectral radius is $S_{n,k}$. We solve this two-part conjecture.

Mathematics Subject Classifications: 05C35, 05C50

Keywords: Spectral Turán number, even-cycle problem, Brualdi-Solheid problem

For given positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots ,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$, but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use sat${}^{\ast }(n,k)$ to denote the smallest size of such a family. For all $k$ and sufficiently large $n$, we determine the exact value of sat${}^{\ast }(n,k)$. Our result implies that sat${}^{\ast }(n,k)=n(k-1)-\mathrm{\Theta }(k\log k)$, which confirms several conjectures on antichain saturation. Previously, exact values for sat${}^{\ast }(n,k)$ were only known for $k$ up to $6$.

We also prove a strengthening of a result of Lehman-Ron which may be of independent interest. We show that given $m$ disjoint chains $C^1,\dots ,C^m$ in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the elements from ${\cup }_{i=1}^m{C}^i$ (where we call a chain skipless if any two consecutive elements differ in size by exactly one).

Mathematics Subject Classifications: 06A07, 05D99

Keywords: Skipless chains, poset saturation, antichain saturation, Boolean lattice

A tight map is a map with some of its vertices marked, such that every vertex of degree $1$ is marked. We give an explicit formula for the number $N_{0,n}(d_1,\dots ,d_n)$ of planar tight maps with $n$ labeled faces of prescribed degrees $d_1,\dots ,d_n$, where a marked vertex is seen as a face of degree $0$. It is a quasi-polynomial in $(d_1,\dots ,d_n)$, as shown previously by Norbury. Our derivation is bijective and based on the slice decomposition of planar maps. In the non-bipartite case, we also rely on enumeration results for two-type forests. We discuss the connection with the enumeration of non necessarily tight maps. In particular, we provide a generalization of Tutte's classical slicings formula to all non-bipartite maps.

Mathematics Subject Classifications: 05A15, 05A19

Keywords: Planar maps, bijective enumeration, slice decomposition

This paper continues the study of two numbers that are associated with Lie groups. The first number is $N(G,m)$, the number of conjugacy classes of elements in $G$ whose order divides $m$. The second number is $N(G,m,s)$, the number of conjugacy classes of elements in $G$ whose order divides $m$ and which have $s$ distinct eigenvalues, where we view $G$ as a matrix group in its smallest-degree faithful representation. We describe systematic algorithms for computing both numbers for $G$ a connected and simply-connected exceptional Lie group. We also provide explicit results for all of $N(G,m)$, $N(G_2,m,s)$, and $N(F_4,m,s)$. The numbers $N(G,m,s)$ were previously known only for the classical Lie groups; our results for $N(G,m)$ agree with those already in the literature but are obtained differently.

Mathematics Subject Classifications: 05A15, 05E16, 22E40, 22E10, 22E15

Keywords: Lie groups, conjugacy classes, element of finite order, Burnside's lemma

We prove a conjectured asymptotic formula of Kuperberg from the representation theory of the Lie algebra $G_2$. Given two non-negative integer sequences $(a_n{)}_{n\ge 0}$ and $(b_n{)}_{n\ge 0}$, with $a_0=b_0=1$, it is well-known that if the identity $B(x)=A(xB(x))$ holds for the generating functions $A(x)=1+\sum _{n\ge 1}{a}_n{x}^n$ and $B(x)=1+\sum _{n\ge 1}{b}_n{x}^n$, then $b_n$ is the number of rooted planar trees with $n+1$ vertices such that each vertex having $i$ children may be colored with any one of $a_i$ distinct colors. Kuperberg proved a specific case when this identity holds, namely when $b_n=\dim {\mathrm{Inv}}_{G_2}(V({\lambda }_1{)}^{\otimes n})$, where $V({\lambda }_1)$ is the 7-dimensional fundamental representation of $G_2$, and $a_n$ is the number of triangulations of a regular $n$-gon such that each internal vertex has degree at least $6$. He also observed that $\underset{n\to \mathrm{\infty }}{lim sup}\sqrt[n]{a_n}\le 7/B(1/7)$ and conjectured that this estimate is sharp, or, in terms of power series, that the radius of convergence of $A(x)$ is exactly $B(1/7)/7$. We prove this conjecture by introducing a new criterion for sharpness in the analogous estimate for general power series $A(x)$ and $B(x)$ satisfying $B(x)=A(xB(x))$. Moreover, by way of singularity analysis performed on a recently discovered generating function for $B(x)$, we significantly refine the conjecture by deriving an asymptotic formula for the sequence $(a_n)$.

Mathematics Subject Classifications: 05A16, 05E10

Keywords: Analytic combinatorics

Thomas and Williams conjectured that rowmotion acting on the rational $(a,b)$-Tamari lattice has order $a+b-1$. We construct an equivariant bijection that proves this conjecture when $a\equiv 1(\mathrm{mod}b)$; in fact, we determine the entire orbit structure of rowmotion in this case, showing that it exhibits the cyclic sieving phenomenon. We additionally show that the down-degree statistic is homomesic for this action. In a different vein, we consider the action of rowmotion on Barnard and Reading's biCambrian lattices. Settling a different conjecture of Thomas and Williams, we prove that if $c$ is a bipartite Coxeter element of a coincidental-type Coxeter group $W$, then the orbit structure of rowmotion on the $c$-biCambrian lattice is the same as the orbit structure of rowmotion on the lattice of order ideals of the doubled root poset of type $W$.

Mathematics Subject Classifications: 05E18, 06B10, 06D75

Keywords: Rowmotion, $m$-Tamari lattice, biCambrian lattice, cyclic sieving, homomesy, homometry

We introduce the primitive Eulerian polynomial $P_{\mathcal{A}}(z)$ of a central hyperplane arrangement $\mathcal{A}$. It is a reparametrization of its cocharacteristic polynomial. Previous work by the first author implicitly shows that for simplicial arrangements, $P_{\mathcal{A}}(z)$ has nonnegative coefficients. For reflection arrangements of types A and B, the same work interprets the coefficients of $P_{\mathcal{A}}(z)$ using the (flag) excedance statistic on (signed) permutations.

The main result of this article is to provide an interpretation of the coefficients of $P_{\mathcal{A}}(z)$ for all simplicial arrangements using only the geometry and combinatorics of $\mathcal{A}$. This new interpretation sheds more light to the case of reflection arrangements and, for the first time, gives combinatorial significance to the coefficients of the primitive Eulerian polynomial of the reflection arrangement of type D, for which no well-behaved excedance statistic is known. In type B, we establish a link between the primitive Eulerian polynomial and the $1/2$-Eulerian polynomial of Savage and Viswanathan (2012). We present some results and conjectures regarding the real-rootedness of $P_{\mathcal{A}}(z)$.

Mathematics Subject Classifications: 52C35, 05A05

Keywords: Hyperplane arrangement, Eulerian polynomial, Tits product, permutation statistics

Robertson and Seymour proved two fundamental theorems about tangles in graphs: the tree-of-tangles theorem, which says that every graph has a tree-decomposition such that distinguishable tangles live in different nodes of the tree, and the tangle-tree duality theorem, which says that graphs without a $k$-tangle have a tree-decomposition that witnesses the non-existence of such tangles, in that $k$-tangles would have to live in a node but no node is large enough to accommodate one.

Erde combined these two fundamental theorems into one, by constructing a single tree-decomposition such that every node either accommodates a single $k$-tangle or is too small to accommodate one. Such a tree-decomposition thus shows at a glance how many $k$-tangles a graph has and where they are.

The two fundamental theorems have since been extended to abstract separation systems, which support tangles in more general discrete structures. In this paper we extend Erde's unified theorem to such general systems.

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

Keywords: Tree of tangles, tangle-tree duality, abstract separation system, submodularity, canonical

Björner and Wachs introduced CL-shellability as a technique for studying the topological structure of order complexes of partially ordered sets. They also introduced the notion of recursive atom ordering, and they proved that a finite bounded poset is CL-shellable if and only if it admits a recursive atom ordering.

In this paper, a generalization of the notion of recursive atom ordering is introduced. A finite bounded poset is proven to admit such a generalized recursive atom ordering if and only if it admits a traditional recursive atom ordering. This is also proven equivalent to admitting a CC-shelling (a type of shelling introduced by Kozlov) with a further property called self-consistency. Thus, CL-shellability is proven equivalent to self-consistent CC-shellability. As an application, the uncrossing posets, namely the face posets for stratified spaces of planar electrical networks, are proven to be dual CL-shellable.

Mathematics Subject Classifications: 05E45, 06A07

Keywords: Poset topology, lexicographic shellability, EC-shellability, recursive atom ordering, uncrossing order