Combinatorial Theory

Tropical refined invariants of toric surfaces constitute a fascinating interpolation between real and complex enumerative geometries via tropical geometry. They were originally introduced by Block and Göttsche, and further extended by Göttsche and Schroeter in the case of rational curves. In this paper, we study the polynomial behavior of coefficients of these tropical refined invariants. We prove that coefficients of small codegree are polynomials in the Newton polygon of the curves under enumeration, when one fixes the genus of the latter. This provides a surprising reappearance, in a dual setting, of the so-called node polynomials and the Göttsche conjecture. Our methods, based on floor diagrams introduced by Mikhalkin and the first author, are entirely combinatorial. Although the combinatorial treatment needed here is different, we follow the overall strategy designed by Fomin and Mikhalkin and further developed by Ardila and Block. Hence our results may suggest phenomena in complex enumerative geometry that have not been studied yet. In the particular case of rational curves, we extend our polynomiality results by including the extra parameter $s$ recording the number of $\psi$ classes. Contrary to the polynomiality with respect to $ \Delta$, the one with respect to $s$ may be expected from considerations on Welschinger invariants in real enumerative geometry. This pleads in particular in favor of a geometric definition of Göttsche-Schroeter invariants.

Mathematics Subject Classifications: Primary 14T15, 14T90, 05A15; Secondary 14N10, 52B20

Keywords: Tropical refined invariants, enumerative geometry, Welschinger invariants, Gromov-Witten invariants, floor diagrams

We study arrangements of slightly skewed tropical hyperplanes, called blades by A. Ocneanu, on the vertices of a hypersimplex $\Delta_{k,n}$, and we investigate the resulting induced polytopal subdivisions. We show that placing a blade on a vertex $e_J$ induces an $\ell$-split matroid subdivision of $\Delta_{k,n}$, where $\ell$ is the number of cyclic intervals in the $k$-element subset $J$. We prove that a given collection of $k$-element subsets is weakly separated, in the sense of the work of Leclerc and Zelevinsky on quasicommuting families of quantum minors, if and only if the arrangement of the blade $((1,2,\ldots, n))$ on the corresponding vertices of $\Delta_{k,n}$ induces a matroid (in fact, a positroid) subdivision. In this way we obtain a compatibility criterion for (planar) multi-splits of a hypersimplex, generalizing the rule known for 2-splits. We study in an extended example a matroidal arrangement of six blades on the vertices $\Delta_{3,7}$.

Mathematics Subject Classifications: 52B40, 05B45, 52B99, 05E99, 14T15

Keywords: Combinatorial geometry, matroid subdivisions, weakly separated collections

For any northeast path $\nu$, we define two bivariate polynomials associated with the $\nu$-associahedron: the $F$- and the $H$-triangle. We prove combinatorially that we can obtain one from the other by an invertible transformation of variables. These polynomials generalize the classical $F$- and $H$-triangles of F. Chapoton in type $A$. Our proof is completely new and has the advantage of providing a combinatorial explanation of the relation between the $F$- and $H$-triangle.

Mathematics Subject Classifications: 05E45, 52B05

Keywords: $\nu$-Tamari lattice, $\nu$-associahedron, $F$-triangle, $H$-triangle

We prove solution uniqueness for the genus one Canham variational problem arising in the shape prediction of biomembranes. The proof builds on a result of Yu and Chen that reduces the variational problem to proving positivity of a sequence defined by a linear recurrence relation with polynomial coefficients. We combine rigorous numeric analytic continuation of D-finite functions with classic bounds from singularity analysis to derive an effective index where the asymptotic behaviour of the sequence, which is positive, dominates the sequence behaviour. Positivity of the finite number of remaining terms is then checked separately.

Mathematics Subject Classifications: 05A16, 68Q40, 30B40

Keywords: Analytic combinatorics, D-finite, P-recursive, positivity, Canham model

Billey-Konvalinka-Swanson studied the asymptotic distribution of the coefficients of Stanley's $q$-hook length formula, or equivalently the major index on standard tableaux of straight shape and certain skew shapes. We extend those investigations to Stanley's $q$-hook-content formula related to semistandard tableaux and $q$-hook length formulas of Björner-Wachs related to linear extensions of labeled forests. We show that, while their coefficients are "generically" asymptotically normal, there are uncountably many non-normal limit laws. More precisely, we introduce and completely describe the compact closure of the metric space of distributions of these statistics in several regimes. The additional limit distributions involve generalized uniform sum distributions which are topologically parameterized by certain decreasing sequence spaces with bounded $2$-norm. The closure of these distributions in the Lévy metric gives rise to the space of DUSTPAN distributions. As an application, we completely classify the limiting distributions of the size statistic on plane partitions fitting in a box.

Mathematics Subject Classifications: 05A16 (Primary), 60C05, 60F05 (Secondary)

Keywords: Hook length, $q$-analogues, major index, semistandard tableaux, plane partitions, forests, asymptotic normality, limit laws, Irwin-Hall distribution

We study Newton polytopes for cluster variables in cluster algebras $\mathcal{A}(\Sigma)$ of types A and D. A famous property of cluster algebras is the Laurent phenomenon: each cluster variable can be written as a Laurent polynomial in the cluster variables of the initial seed $\Sigma$. The cluster variable Newton polytopes are the Newton polytopes of these Laurent polynomials. We show that if $\Sigma$ has principal coefficients or boundary frozen variables, then all cluster variable Newton polytopes are saturated. We also characterize when these Newton polytopes are empty; that is, when they have no non-vertex lattice points.

Mathematics Subject Classifications: 13F60, 52B20

Keywords: Cluster algebras, Newton polytopes, snake graphs

We reinterpret an inequality, due originally to Sidorenko, for linear extensions of posets in terms of convex subsets of the symmetric group $\mathfrak{S}_n$. We conjecture that the analogous inequalities hold in arbitrary (not-necessarily-finite) Coxeter groups $W$, and prove this for the hyperoctahedral groups $B_n$ and all right-angled Coxeter groups. Our proof for $B_n$ (and new proof for $\mathfrak{S}_n$) use a combinatorial insertion map closely related to the well-studied promotion operator on linear extensions; this map may be of independent interest. We also note that the inequalities in question can be interpreted as a triangle inequalities, so that convex hulls can be used to define a new invariant metric on $W$ whenever our conjecture holds. Geometric properties of this metric are an interesting direction for future research.

Mathematics Subject Classifications: 05A20, 05C12, 05E16, 20F55

Keywords: Linear extension, promotion, Coxeter group, convex hull, metric

We associate two modules, the $G$-parking critical module and the toppling critical module, to an undirected connected graph $G$. The $G$-parking critical module and the toppling critical module are canonical modules (with suitable twists) of quotient rings of the well-studied $G$-parking function ideal and the toppling ideal, respectively. For each critical module, we establish a Tutte-like short exact sequence relating the modules associated to $G$, an edge contraction $G/e$ and an edge deletion $G \setminus e$ ($e$ is a non-bridge). We obtain purely combinatorial consequences of Tutte short exact sequences. For instance, we reprove a theorem of Merino that the critical polynomial of a graph is an evaluation of its Tutte polynomial, and relate the vanishing of certain combinatorial invariants (the number of acyclic orientations on connected partition graphs satisfying a unique sink property) of $G/e$ to the equality of the corresponding invariants of $G$ and $G \setminus e$.

Mathematics Subject Classifications: 13D02, 05E40

Keywords: Tutte polynomials, chip firing games, toppling ideals, $G$-parking function ideals, canonical modules

For a fixed irrational number $\alpha$ and $n\in \mathbb{N}$, we look at the shape of the sequence $(f(1),\ldots,f(n))$ after Schensted insertion, where $f(i) = \alpha i \mod 1$. Our primary result is that the boundary of the Schensted shape is approximated by a piecewise linear function with at most two slopes. This piecewise linear function is explicitly described in terms of the continued fraction expansion for $\alpha$. Our results generalize those of Boyd and Steele, who studied longest monotone subsequences. Our proofs are based on a careful analysis of monotone sets in two-dimensional lattices.

Mathematics Subject Classifications: 05A05, 11H06, 11B57, 11K06

Keywords: Longest increasing subsequence, Schensted shape, geometry of numbers, S os permutations

The recently introduced twin-width of a graph $G$ is the minimum integer $d$ such that $G$ has a $d$-contraction sequence, that is, a sequence of $\left| V(G) \right|-1$ iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most $d$, where a red edge appears between two sets of identified vertices if they are not homogeneous in $G$ (not fully adjacent nor fully non-adjacent). We show that if a graph admits a $d$-contraction sequence, then it also has a linear-arity tree of $f(d)$-contractions, for some function $f$. Informally if we accept to worsen the twin-width bound, we can choose the next contraction from a set of $\Theta(\left| V(G) \right|)$ pairwise disjoint pairs of vertices. This has two main consequences. First it permits to show that every bounded twin-width class is small, i.e., has at most $n!c^n$ graphs labeled by $[n]$, for some constant $c$. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. It implies in turn that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width. The second consequence is an $O(\log n)$-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the small conjecture that, conversely, every small hereditary class has bounded twin-width. The conjecture passes many tests. Inspired by sorting networks of logarithmic depth, we show that $\log_{\Theta(\log \log d)}n$-subdivisions of $K_n$ (a small class when $d$ is constant) have twin-width at most $d$. We obtain a rather sharp converse with a surprisingly direct proof: the $\log_{d+1}n$-subdivision of $K_n$ has twin-width at least $d$. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. These sparse classes are surprisingly rich since they contain certain (small) classes of expanders. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from $K_4$ [Bilu and Linial, Combinatorica '06] also have bounded twin-width. These graphs are related to so-called separable permutations and also form a small class. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width. We show that for a hereditary class $\mathcal C$ of bounded twin-width the five following conditions are equivalent: every graph in $\mathcal C$ (1) has no $K_{t,t}$ subgraph for some fixed $t$, (2) has an adjacency matrix without a $d$-by-$d$ division with a 1 entry in each of the $d^2$ cells for some fixed $d$, (3) has at most linearly many edges, (4) the subgraph closure of $\mathcal C$ has bounded twin-width, and (5) $\mathcal C$ has bounded expansion. We discuss how sparse classes with similar behavior with respect to clique subdivisions compare to bounded sparse twin-width.

Mathematics Subject Classifications: 68R10, 05C30, 05C48

Keywords: Twin-width, small classes, expanders, clique subdivisions, sparsity

A family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is called $k$-wise intersecting if any $k$ members of $\mathcal{F}$ have non-empty intersection, and it is called maximal $k$-wise intersecting if no family strictly containing $\mathcal{F}$ satisfies this condition. We show that for each $k\geq 2$ there is a maximal $k$-wise intersecting family of size $O(2^{n/(k-1)})$. Up to a constant factor, this matches the best known lower bound, and answers an old question of Erdős and Kleitman, recently studied by Hendrey, Lund, Tompkins, and Tran.

Mathematics Subject Classifications: 05D05

Keywords: Intersecting family, saturation, set system

We study the symplectic Howe duality using two new and independent combinatorial methods: via determinantal formulae on the one hand, and via (bi)crystals on the other hand. The first approach allows us to establish a generalised version where weight multiplicities are replaced by branching coefficients. In turn, this generalised Howe duality is used to prove the injectivity of induction for Levi branchings as previously conjectured by the last two authors.

Mathematics Subject Classifications: 17B10, 17B37, 05E05, 05E10

Keywords: Lie algebras, representation theory, Schur-Weyl duality, Howe duality, crystals, Schur functions, induced modules

In 2011, Han and Ji proved addition-multiplication theorems for integer partitions, from which they derived modular analogues of many classical identities involving hook-length. In the present paper, we prove addition-multiplication theorems for the subset of self-conjugate partitions. Although difficulties arise due to parity questions, we are almost always able to include the BG-rank introduced by Berkovich and Garvan. This gives us as consequences many self-conjugate modular versions of classical hook-lengths identities for partitions. Our tools are mainly based on fine properties of the Littlewood decomposition restricted to self-conjugate partitions.

Mathematics Subject Classifications: 05A15, 05A17, 05A19, 05E05, 05E10, 11P81

Keywords: Hook-length formulas, BGP-ranks, Integers partitions, Littlewood decomposition, core partitions

We solve two problems regarding the enumeration of lattice paths in $\mathbb{Z}^2$ with steps $(1,1)$ and $(1,-1)$ with respect to the major index, defined as the sum of the positions of the valleys, and to the number of certain crossings. The first problem considers crossings of a single path with a fixed horizontal line. The second one counts pairs of paths with respect to the number of times they cross each other. Our proofs introduce lattice path bijections with convenient visual descriptions, and the answers are given by remarkably simple formulas involving $q$-binomial coefficients.

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

Keywords: Lattice path, major index, crossing, valley, bijection

We show that there exist constants $\alpha,\epsilon>0$ such that for every positive integer $n$ there is a continuous odd function $f:S^m\to S^n$, with $m\geq \alpha n$, such that the $\epsilon$-expansion of the image of $f$ does not contain a great circle. This result is motivated by a conjecture of Vitali Milman about well-complemented almost Euclidean subspaces of spaces uniformly isomorphic to $\ell_2^n$.

Mathematics Subject Classifications: 46B09, 60C05

Keywords: Anti-Ramsey, antipodal subsphere

Lusztig's fake degree is the generating polynomial for the major index of standard Young tableaux of a given shape. Results of Springer (1974) and James & Kerber (1984) imply that, mysteriously, its evaluation at a $k$-th primitive root of unity yields the number of border strip tableaux with all strips of size $k$, up to sign. This is essentially the special case of the Murnaghan-Nakayama rule for evaluating an irreducible character of the symmetric group at a rectangular partition. We refine this result to standard Young tableaux and border strip tableaux with a given number of descents. To do so, we introduce a new statistic for border strip tableaux, extending the classical definition of descents in standard Young tableaux. Curiously, it turns out that our new statistic is very closely related to a descent set for tuples of standard Young tableaux appearing in the quasisymmetric expansion of LLT polynomials given by Haglund, Haiman and Loehr (2005).

Mathematics Subject Classifications: 05A19, 05E10

Keywords: Border strip tableaux, descents, Murnaghan-Nakayama rule, fake degree

A character identity which relates irreducible character values of the hyperoctahedral group $B_n$ to those of the symmetric group $S_{2n}$ was recently proved by Lübeck and Prasad. Their proof is algebraic and involves Lie theory. We present a short combinatorial proof of this identity, as well as a generalization to other wreath products.

Mathematics Subject Classifications: 20C30, 20E22, 05E10

Keywords: Character identity, wreath product, partition, Murnaghan-Nakayama rule, colored permutations