We continue our study, initiated in our prior work with Richard Stanley, of the representation of the symmetric group on the multilinear component of an $n$-ary generalization of the free Lie algebra known as the free Filippov $n$-algebra with $k$ brackets. Our ultimate aim is to determine the multiplicities of the irreducible representations in this representation. This had been done for the ordinary Lie representation ($n=2$ case) by Kraskiewicz and Weyman. The $k=2$ case was handled in our prior work, where the representation was shown to be isomorphic to $S^{2^{n-1}1}$. In this paper, for general $n$ and $k$, we obtain decomposition results that enable us to determine the multiplicities in the $k=3$ and $k=4$ cases. In particular we prove that in the $k=3$ case, the representation is isomorphic to $S^{3^{n-1}1} \oplus S^{3^{n-2}21^2}$. Our main result shows that the multiplicities stabilize in a certain sense when $n$ exceeds $k$. As an important tool in proving this, we present two types of generalizations of the notion of Specht module that involve trees.
We introduce multicritical Schur measures, which are probability laws on integer partitions which give rise to non-generic fluctuations at their edge. They are in the same universality classes as one-dimensional momentum-space models of free fermions in flat confining potentials, studied by Le Doussal, Majumdar and Schehr. These universality classes involve critical exponents of the form 1/(2m+1), with m a positive integer, and asymptotic distributions given by Fredholm determinants constructed from higher order Airy kernels, extending the generic Tracy-Widom GUE distribution recovered for m=1. We also compute limit shapes for the multicritical Schur measures, discuss the finite temperature setting, and exhibit an exact mapping to the multicritical unitary matrix models previously encountered by Periwal and Shevitz.
A generalization of the scattering equations on $X(2,n)$, the configuration space of $n$ points on $\mathbb{CP}^1$, to higher dimensional projective spaces was recently introduced by Early, Guevara, Mizera, and one of the authors. One of the new features in $X(k,n)$ with $k>2$ is the presence of both regular and singular solutions in a soft limit. In this work we study soft limits in $X(3,7)$, $X(4,7)$, $X(3,8)$ and $X(5,8)$, find all singular solutions, and show their geometrical configurations. More explicitly, for $X(3,7)$ and $X(4,7)$ we find $180$ and $120$ singular solutions which when added to the known number of regular solutions both give rise to $1\, 272$ solutions as it is expected since $X(3,7)\sim X(4,7)$. Likewise, for $X(3,8)$ and $X(5,8)$ we find $59\, 640$ and $58\, 800$ singular solutions which when added to the regular solutions both give rise to $188\, 112$ solutions. We also propose a classification of all configurations that can support singular solutions for general $X(k,n)$ and comment on their contribution to soft expansions of generalized biadjoint amplitudes.
We investigate the combinatorial structure of subspaces of the exterior algebra of a finite-dimensional real vector space, working in parallel with the extremal combinatorics of hypergraphs. Using initial monomials, projections of the underlying vector space onto subspaces, and the interior product, we find analogues of local and global LYM inequalities, the Erdős-Ko-Rado theorem, and the Ahlswede-Khachatrian bound for $t$-intersecting hypergraphs. Using these tools, we prove a new extension of the Two Families Theorem of Bollobás, giving a weighted bound for subspace configurations satisfying a skew cross-intersection condition. We also verify a recent conjecture of Gerbner, Keszegh, Methuku, Abhishek, Nagy, Patkós, Tompkins, and Xiao on pairs of set systems satisfying both an intersection and a cross-intersection condition.
Tomás M. Coronado, Mareike Fischer, Lina Herbst
et al.
Measures of tree balance play an important role in the analysis of phylogenetic trees. One of the oldest and most popular indices in this regard is the Colless index for rooted bifurcating trees, introduced by Colless (1982). While many of its statistical properties under different probabilistic models for phylogenetic trees have already been established, little is known about its minimum value and the trees that achieve it. In this manuscript, we fill this gap in the literature. To begin with, we derive both recursive and closed expressions for the minimum Colless index of a tree with $n$ leaves. Surprisingly, these expressions show a connection between the minimum Colless index and the so-called Blancmange curve, a fractal curve. We then fully characterize the tree shapes that achieve this minimum value and we introduce both an algorithm to generate them and a recurrence to count them. After focusing on two extremal classes of trees with minimum Colless index (the maximally balanced trees and the greedy from the bottom trees), we conclude by showing that all trees with minimum Colless index also have minimum Sackin index, another popular balance index.
João Gouveia, Antonio Macchia, Rekha R. Thomas
et al.
The slack ideal of a polytope is a saturated determinantal ideal that gives rise to a new model for the realization space of the polytope. The simplest slack ideals are toric and have connections to projectively unique polytopes. We prove that if a projectively unique polytope has a toric slack ideal, then it is the toric ideal of the bipartite graph of vertex-facet non-incidences of the polytope. The slack ideal of a polytope is contained in this toric ideal if and only if the polytope is morally 2-level, a generalization of the 2-level property in polytopes. We show that polytopes that do not admit rational realizations cannot have toric slack ideals. A classical example of a projectively unique polytope with no rational realizations is due to Perles. We prove that the slack ideal of the Perles polytope is reducible, providing the first example of a slack ideal that is not prime.
We give a complete combinatorial characterization of homogeneous quadratic relations of "universal character" valid for minors of quantum matrices (more precisely, for minors in the quantized coordinate ring $O_q(M_{m,n}(K))$ of $m\times n$ matrices over a field $K$, where $q\in K^\ast$). This is obtained as a consequence of a study of quantized minors of matrices generated by paths in certain planar graphs, called SE-graphs, generalizing the ones associated with Cauchon diagrams. Our efficient method of verifying universal quadratic identities for minors of quantum matrices is illustrated with many appealing examples.
The results of [1,2] on linear homogeneous two-weight codes over finite Frobenius rings are exended in two ways: It is shown that certain non-projective two-weight codes give rise to strongly regular graphs in the way described in [1,2]. Secondly, these codes are used to define a dual two-weight code and strongly regular graph similar to the classical case of projective linear two-weight codes over finite fields [3].
We expose a rule for multiplying a general Schubert polynomial with a power sum polynomial in $k$ variables. A signed sum over cyclic permutations replaces the signed sum over rim hooks in the classical Murgnahan-Nakayama rule. In the intersection theory of flag manifolds this computes all intersections of Schubert cycles with tautological classes coming from the Chern character. We also discuss extensions of this rule to small quantum cohomology.
The purpose of this work is to initiate a combinatorial study of the Bruhat-Chevalley ordering on certain sets of permutations obtained by omitting the parentheses from their standard cyclic notation. In particular, we show that these sets form bounded, graded, unimodal, rank-symmetric and EL-shellable posets. Moreover, we determine the homotopy types of the associated order complexes.
Olivier Bodini, Antoine Genitrini, Frédéric Peschanski
In this paper, we study the shuffle operator on concurrent processes (represented as trees) using analytic combinatorics tools. As a first result, we show that the mean width of shuffle trees is exponentially smaller than the worst case upper-bound. We also study the expected size (in total number of nodes) of shuffle trees. We notice, rather unexpectedly, that only a small ratio of all nodes do not belong to the last two levels. We also provide a precise characterization of what ``exponential growth'' means in the case of the shuffle on trees. Two practical outcomes of our quantitative study are presented: (1) a linear-time algorithm to compute the probability of a concurrent run prefix, and (2) an efficient algorithm for uniform random generation of concurrent runs.
We use death processes and embeddings into continuous time in order to analyze several urn models with a diminishing content. In particular we discuss generalizations of the pill's problem, originally introduced by Knuth and McCarthy, and generalizations of the well known sampling without replacement urn models, and OK Corral urn models.
Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements. Through this construction, we explain combinatorially the relationship between the Gelfand–Tsetlin polytopes (1950) and the Feigin–Fourier–Littelmann–Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand–Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin–Fourier–Littelmann–Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.
When $W$ is a finite reflection group, the noncrossing partition lattice $NC(W)$ of type $W$ is a very rich combinatorial object, extending the notion of noncrossing partitions of an $n$-gon. A formula (for which the only known proofs are case-by-case) expresses the number of multichains of a given length in $NC(W)$ as a generalized Fuß-Catalan number, depending on the invariant degrees of $W$. We describe how to understand some specifications of this formula in a case-free way, using an interpretation of the chains of $NC(W)$ as fibers of a "Lyashko-Looijenga covering''. This covering is constructed from the geometry of the discriminant hypersurface of $W$. We deduce new enumeration formulas for certain factorizations of a Coxeter element of $W$.
We use the polynomial ring $\mathbb{C}[x_{1,1},\ldots,x_{n,n}]$ to modify the Kazhdan-Lusztig construction of irreducible $S_n$-modules. This modified construction produces exactly the same matrices as the original construction in [$\textit{Invent. Math}$ $\mathbf{53}$ (1979)], but does not employ the Kazhdan-Lusztig preorders. We also show that our modules are related by unitriangular transition matrices to those constructed by Clausen in [$\textit{J. Symbolic Comput.}$ $\textbf{11}$ (1991)]. This provides a $\mathbb{C}[x_{1,1},\ldots,x_{n,n}]$-analog of results of Garsia-McLarnan in [$\textit{Adv. Math.}$ $\textbf{69}$ (1988)].
The median problem seeks a permutation whose total distance to a given set of permutations (the base set) is minimal. This is an important problem in comparative genomics and has been studied for several distance measures such as reversals. The transposition distance is less relevant biologically, but it has been shown that it behaves similarly to the most important biological distances, and can thus give important information on their properties. We have derived an algorithm which solves the transposition median problem, giving all transposition medians (the median cloud). We show that our algorithm can be modified to accept median clouds as elements in the base set and briefly discuss the new concept of median iterates (medians of medians) and limit medians, that is the limit of this iterate.
To a word $w$, we associate the rational function $\Psi_w = \prod (x_{w_i} - x_{w_{i+1}})^{-1}$. The main object, introduced by C. Greene to generalize identities linked to Murnaghan-Nakayama rule, is a sum of its images by certain permutations of the variables. The sets of permutations that we consider are the linear extensions of oriented graphs. We explain how to compute this rational function, using the combinatorics of the graph $G$. We also establish a link between an algebraic property of the rational function (the factorization of the numerator) and a combinatorial property of the graph (the existence of a disconnecting chain).
We prove that for each $k \geq 0$, the probability that a root vertex in a random planar graph has degree $k$ tends to a computable constant $d_k$, and moreover that $\sum_k d_k =1$. The proof uses the tools developed by Gimènez and Noy in their solution to the problem of the asymptotic enumeration of planar graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function $p(w)=\sum_k d_k w^k$. From the explicit expression for $p(w)$ we can compute the $d_k$ to any degree of accuracy, and derive asymptotic estimates for large values of $k$.