Yibo Gao

Quantum Bruhat graph is a weighted directed graph on a finite Weyl group first defined by Brenti-Fomin-Postnikov. It encodes quantum Monk's rule and can be utilized to study the \(3\)-point Gromov-Witten invariants of the flag variety. In this paper, we provide an explicit formula for the minimal weights between any pair of permutations on the quantum Bruhat graph, and consequently obtain an Ehresmann-like characterization for the tilted Bruhat order. Moreover, for any ordered pair of permutations \(u\) and \(v\), we define the tilted Richardson variety \(\mathcal{T}_{u,v}\), with a stratification that gives a geometric meaning to intervals in the tilted Bruhat order. We provide a few equivalent definitions to this new family of varieties that include Richardson varieties, and establish some fundamental geometric properties including their dimensions and closure relations.

Pak and Postnikov introduced a tree enumeration polynomial \(f_G\) on graphs, as a multivariate generalization of Cayley’s formula, and demonstrated an amazing reciprocity property. In this paper, we prove that this tree enumeration polynomial can be factorized into linear factors for the inversion graph of separable permutations. We derive an explicit formula for this factorization and provide three proofs: one using the reciprocity theorem, one algebraic, and another one bijective. We also prove its converse: the tree enumeration polynomials for all other graphs cannot be factored into linear factors.

For an arbitrary Coxeter group element \(\sigma\) and a connected subset \(J\) of the Dynkin diagram, the parabolic decomposition \(\sigma=\sigma^J\sigma_J\) defines \(\sigma_J\) as a consecutive pattern of \(\sigma\), generalizing the notion of consecutive patterns in permutations. We then define the cc-Wilf-equivalence classes as an extension of the c-Wilf-equivalence classes for permutations, and identify non-trivial families of cc-Wilf-equivalent classes. Furthermore, we study the structure of the consecutive pattern poset in Coxeter groups and prove that its Möbius function is bounded by \(2\) when the arguments belong to finite Coxeter groups, but can be arbitrarily large otherwise.

We prove a short, root-system uniform, combinatorial classification of Levi-spherical Schubert varieties for any generalized flag variety \(G/B\) of finite Lie type. We apply this to the study of multiplicity-free decompositions of a Demazure module into irreducible representations of a Levi subgroup.

For \(w\) in the symmetric group, we provide an exact formula for the smallest positive power \(q^{h(w)}\) appearing in the Kazhdan-Lusztig polynomial \(P_{e,w}(q)\). We also provide a tight upper bound on \(h(w)\) in simply-laced types, resolving a conjecture of Billey-Postnikov from 2002.

Given two vectors \(u\) and \(v\), their outer sum is given by the matrix \(A\) with entries \(A_{ij}=u_{i}+v_{j}\). If the entries of \(u\) and \(v\) are increasing and sufficiently generic, the total ordering of the entries of the matrix is a standard Young tableau of rectangular shape. We call standard Young tableaux arising in this way realizable. The set of realizable tableaux was defined by Mallows and Vanderbei for studying a deconvolution algorithm, but we show they have appeared in many other contexts including sorting algorithms, quantum computing, random sorting networks, reflection arrangements, fiber polytopes, and Goodman and Pollack's theory of allowable sequences. In our work, we prove tight bounds on the asymptotic number of realizable rectangular tableaux. We also derive tight asymptotics for the number of realizable allowable sequences, which are in bijection with realizable staircase-shaped standard Young tableaux with the notion of realizability coming from the theory of sorting networks. As a consequence, we resolve an open question of Angel, Gorin, and Holroyd from 2012 and improve upon a 1986 result of Goodman and Pollack.

We provide a type-uniform formula for the degree of the stretched Kostka quasi-polynomial \(K_{\lambda,\mu}(N)\) in all classical types, improving a previous result by McAllister in \(\mathfrak{sl}_r(\mathbb{C})\). Our proof relies on a combinatorial model for the weight multiplicity by Berenstein and Zelevinsky.

We study the ring of regular functions on the space of planar electrical networks, which we coin the grove algebra. This algebra is an electrical analogue of the Plücker ring studied classically in invariant theory. We develop the combinatorics of double groves to study the grove algebra, and find a quadratic Gröbner basis for the grove ideal.

The (directed) Bruhat graph \(\hat{\Gamma}(u,v)\) has the elements of the Bruhat interval \([u,v]\) as vertices, with directed edges given by multiplication by a reflection. Famously, \(\hat{\Gamma}(u,v)\) is regular if and only if the Schubert variety \(X_v\) is smooth, and this condition on \(v\) is characterized by pattern avoidance. In this work, we classify when the undirected Bruhat graph \(\Gamma(e,v)\) is vertex-transitive; surprisingly this class of permutations is also characterized by pattern avoidance and sits nicely between the classes of smooth permutations and self-dual permutations. This leads us to a general investigation of automorphisms of \(\Gamma(e,v)\) in the course of which we show that special matchings, which originally appeared in the theory Kazhdan--Lusztig polynomials, can be characterized as certain \(\Gamma(e,v)\)-automorphisms which are conjecturally sufficient to generate the orbit of \(e\) under \(\mathrm{Aut}(\Gamma(e,v))\).

We study the maximum multiplicity \(\mathcal{M}(k,n)\) of a simple transposition \(s_k=(k\ k+1)\) in a reduced word for the longest permutation \(w_0=n\ n{-}1\cdots 21\), a problem closely related to much previous work on sorting networks and on the "\(k\)-sets" problem. After reinterpreting the problem in terms of monotone weakly separated paths, we show that, for fixed \(k\) and growing \(n\), the optimal paths are periodic in a precise sense, so that \(\mathcal{M}(k,n)=c_kn+p_k(n)\) for a periodic function \(p_k\) and constant \(c_k\). In fact we show that \(c_k\) is always rational, and compute several bounds and exact values for this quantity using "repeatable patterns", which we introduce.

We introduce balanced shifted tableaux, as an analogue of balanced tableaux of Edelman and Greene, from the perspective of root systems of type \(B\) and \(C\). We show that they are equinumerous to standard Young tableaux of the corresponding shifted shape by presenting an explicit bijection.

We present a direct bijection between reduced pipe dreams and reduced bumpless pipe dreams by interpreting reduced compatible sequences on bumpless pipe dreams and show that this bijection preserves Monk's formula, establishing its canonical nature.

We study the diameter of the graph \(G(w)\) of reduced words of an element \(w\) in a Coxeter group \(W\) whose edges correspond to applications of the Coxeter relations. We resolve conjectures of Reiner--Roichman and Dahlberg--Kim by proving a tight lower bound on this diameter when \(W=S_n\) is the symmetric group and by characterizing the equality cases. We also give partial results in other classical types which illustrate the limits of current techniques.

A Schubert variety in the complete flag manifold \(GLn/B\) is Levi-spherical if the action of a Borel subgroup in a Levi subgroup of a standard parabolic has a dense orbit. We give a combinatorial classification of these Schubert varieties. This establishes a conjecture of the latter two authors, and a new formulation in terms of standard Coxeter elements. Our proof uses the theory of key polynomials (type \(A\) Demazure module characters).

The limit weak order on an affine Weyl group was introduced by Lam and Pylyavskyy in their study of total positivity for loop groups. They showed that in the case of the affine symmetric group the minimal elements of this poset coincide with the infinite fully commutative reduced words and with infinite powers of Coxeter elements. We answer several open problems raised there by classifying minimal elements in all affine types and relating these elements to the classes of fully commutative and Coxeter elements. Interestingly, the infinite fully commutative elements correspond to the minuscule and cominuscule nodes of the Dynkin diagram, while the infinite Coxeter elements correspond to a single node, which we call the heavy node, in all affine types other than type \(A\).

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 Bn 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.

Upper homogeneous finite type (upho) posets are a large class of partially ordered sets with the property that the principal order filter at every vertex is isomorphic to the whole poset. Well-known examples include \(k\)-array trees, the grid graphs, and the Stern poset. Very little is known about upho posets in general. In this paper, we construct upho posets with Schur-positive Ehrenborg quasisymmetric functions, whose rank-generating functions have rational poles and zeros. We also categorize the rank-generating functions of all planar upho posets. Finally, we prove the existence of an upho poset with uncomputable rank-generating function.

We show that \(w\in W\) is boolean if and only if it avoids a set of Billey-Postnikov patterns, which we describe explicitly. Our proof is based on an analysis of inversion sets, and it is in large part type-uniform. We also introduce the notion of linear pattern avoidance, and show that boolean elements are characterized by avoiding just the 3 linear patterns \(s_1 s_2 s_1 \in W(A_2)\), \(s_2 s_1 s_3 s_2 \in W(A_3)\), and \(s_2 s_1 s_3 s_4 s_2 \in W(D_4)\).
We also consider the more general case of \(k\)-boolean Weyl group elements. We say that \(w\in W\) is \(k\)-boolean if every reduced expression for \(w\) contains at most \(k\) copies of each generator. We show that the 2-boolean elements of the symmetric group \(S_n\) are characterized by avoiding the patterns 3421, 4312, 4321 and 456123, and give a rational generating function for the number of 2-boolean elements of \(S_n\).

The 1/3-2/3 Conjecture, originally formulated in 1968, is one of the best-known open problems in the theory of posets, stating that the balance constant (a quantity determined by the linear extensions) of any non-total order is at least 1/3. By reinterpreting balance constants of posets in terms of convex subsets of the symmetric group, we extend the study of balance constants to convex subsets \(C\) of any Coxeter group. Remarkably, we conjecture that the lower bound of 1/3 still applies in any finite Weyl group, with new and interesting equality cases appearing.
We generalize several of the main results towards the 1/3-2/3 Conjecture to this new setting: we prove our conjecture when \(C\) is a weak order interval below a fully commutative element in any acyclic Coxeter group (an generalization of the case of width-two posets), we give a uniform lower bound for balance constants in all finite Weyl groups using a new generalization of order polytopes to this context, and we introduce generalized semiorders for which we resolve the conjecture.
We hope this new perspective may shed light on the proper level of generality in which to consider the 1/3-2/3 Conjecture, and therefore on which methods are likely to be successful in resolving it.

Björner-Ekedahl prove that general intervals \([e,w]\) in Bruhat order are "top-heavy", with at least as many elements in the \(i\)-th corank as the \(i\)-th rank. Well-known results of Carrell and of Lakshmibai-Sandhya give the equality case: \([e,w]\) is rank-symmetric if and only if the permutation \(w\) avoids the patterns 3412 and 4231 and these are exactly those \(w\) such that the Schubert variety \(X_w\) is smooth.
In this paper we study the finer structure of rank-symmetric intervals \([e,w]\), beyond their rank functions. In particular, we show that these intervals are still "top-heavy" if one counts cover relations between different ranks. The equality case in this setting occurs when \([e,w]\) is self-dual as a poset; we characterize these \(w\) by pattern avoidance and in several other ways.

Descent polynomials and peak polynomials, which enumerate permutations with given descent and peak sets respectively, have recently received considerable attention. We give several formulas for \(q\)-analogs of these polynomials which refine the enumeration by the length of the permutations. In the case of \(q\)-descent polynomials we prove that the coefficients in one basis are strongly \(q\)-log concave, and conjecture this property in another basis. For peaks, we prove that the \(q\)-peak polynomial is palindromic in \(q\), resolving a conjecture of Diaz-Lopez, Harris, and Insko.

We continue the study of separable elements in finite Weyl groups. These elements generalize the well-studied class of separable permutations. We show that the multiplication map \(W/U\times U\rightarrow W\) is a length-additive bijection, or splitting, of the Weyl group \(W\) when \(U\) is an order ideal in right weak order generated by a separable element; this generalizes a result for the symmetric group, answering an open problem of Wei.
For a generalized quotient of the symmetric group, we show that this multiplication map is a bijection if and only if \(U\) is an order ideal in right weak order generated by a separable element, thereby classifying those generalized quotients which induce splittings of the symmetric group, resolving a problem of Björner and Wachs from 1988. We also prove that this map is always surjective when \(U\) is an order ideal in right weak order. Interpreting these sets of permutations as linear extensions of 2-dimensional posets gives the first direct combinatorial proof of an inequality due originally to Sidorenko in 1991, answering an open problem Morales, Pak, and Panova. We also prove a new \(q\)-analog of Sidorenko's formula. All of these results are conjectured to extend to arbitrary finite Weyl groups.
Finally, we show that separable elements in \(W\) are in bijection with the faces of all dimensions of several copies of the graph associahedron of the Dynkin diagram of \(W\). This correspondence associates to each separable element \(w\) a certain nested set; we give product formulas for the rank generating functions of the principal upper and lower order ideals generated by \(w\) in terms of these nested sets, generalizing several known formulas.

We show that the principal specialization of the Schubert polynomial at \(w\) is bounded below by \(1+p_{132}(w)+p_{1432}(w)\) where \(p_u(w)\) is the number of occurrences of the pattern \(u\) in \(w\), strengthening a previous result by A. Weigandt. We then make a conjecture relating the principal specialization of Schubert polynomials to pattern containment. Finally, we characterize permutations \(w\) whose RC-graphs are connected by simple ladder moves via pattern avoidance.

We show that the number of signed permutations avoiding 1234 equals the number of signed permutations avoiding 2143 (also called vexillary signed permutations), resolving a conjecture by Anderson and Fulton. The main tool that we use is the generating tree developed by West. Many further directions are mentioned in the end.

In this paper, we study arithmetic properties of weighted Catalan numbers. Previously, Postnikov and Sagan found conditions under which the \(2\)-adic valuations of the weighted Catalan numbers are equal to the \(2\)-adic valutations of the Catalan numbers. We obtain the same result under weaker conditions by considering a map from a class of functions to \(2\)-adic integers. These methods are also extended to \(q\)-weighted Catalan numbers, strengthening a previous result by Konvalinka. Finally, we prove some results on the periodicity of weighted Catalan numbers modulo an integer and apply them to the specific case of the number of combinatorial types of Morse links. Many open questions are mentioned.

In the abelian sandpile model, recurrent chip configurations are of interest as they are a natural choice of coset representatives under the quotient of the reduced Laplacian. We investigate graphs whose recurrent identities with respect to different sinks are compatible with each other. The maximal stable configuration is the simplest recurrent chip configuration, and graphs whose recurrent identities equal the maximal stable configuration are of particular interest, and are said to have the complete maximal identity property. We prove that given any graph \(G\) one can attach trees to the vertices of \(G\) to yield a graph with the complete maximal identity property. We conclude with several intriguing conjectures about the complete maximal identity property of various graph products.

We define the notion of a separable element in a finite Weyl group, generalizing the well-studied class of separable permutations. We prove that the upper and lower order ideals in weak Bruhat order generated by a separable element are rank-symmetric and rank-unimodal, and that the product of their rank generating functions gives that of the whole group, answering an open problem of Fan Wei. We also prove that separable elements are characterized by pattern avoidance in the sense of Billey and Postnikov.

We prove a common generalization of the fact that the weighted number of maximal chains in the strong Bruhat order on the symmetric group is \({n \choose 2}!\) for both the code weights and the Chevalley weights. We also define weights which give a one-parameter family of strong order analogues of Macdonald's reduced word identity for Schubert polynomials.

Two partial orders on a reflection group, the codimension order and the prefix order, are together called the absolute order when they agree. We show that in this case the absolute order on a complex reflection group has the strong Sperner property, except possibly for the Coxeter group of type \(D_n\), for which this property is conjectural. The Sperner property had previously been established for the noncrossing partition lattice \(NC_W\), a certain maximal interval in the absolute order, but not for the entire poset, except in the case of the symmetric group. We also show that neither the codimension order nor the prefix order has the Sperner property for general complex reflection groups.

In recent work, the authors used an order lowering operator \(\nabla\), introduced by Stanley, to prove the strong Sperner property for the weak Bruhat order on the symmetric group. Hamaker, Pechenik, Speyer, and Weigandt interpreted \(\nabla\) as a differential operator on Schubert polynomials and used this to prove a new identity for Schubert polynomials and a determinant conjecture of Stanley. In this paper we study a raising operator \(\Delta\) for the strong Bruhat order, which is in many ways dual to \(\nabla\). We prove a Schubert identity dual to that of Hamaker et al. and derive formulas for counting weighted paths in the Hasse diagrams of the strong order which agree with path counting formulas for the weak order. We also show that powers of \(\nabla\) and \(\Delta\) have the same Smith normal forms, which we describe explicitly, answering a question of Stanley.

We construct a simple combinatorially-defined representation of \(\mathfrak{sl}_2\) which respects the order structure of the weak order on the symmetric group. This is used to prove that the weak order has the strong Sperner property, and is therefore a Peck poset, solving a problem raised by Björner [Orderings of Coxeter groups, Amer. Math. Soc., Providence, RI, 1984, pp. 175-195]; a positive answer to this question had been conjectured by Stanley [Some Schubert shenanigans, preprint, 2017].

In this paper, we provide explicit formula for the dual Schubert polynomials of a special class of permutations using certain involution principals on RC-graphs, resolving a conjecture by Postnikov and Stanley.

A shelling of a graph, viewed as an abstract simplicial complex that is pure of dimension 1, is an ordering of its edges such that every edge is adjacent to some other edges appeared previously. In this paper, we focus on complete bipartite graphs and trees. For complete bipartite graphs, we obtain an exact formula for their shelling numbers. And for trees, we propose a simple method to count shellings and bound shelling numbers using vertex degrees and diameter.

The notions of critical ideals and characteristic ideals of graphs are introduced by Corrales and Valencia to study properties of graphs, including clique number, zero forcing number, minimum rank and critical group. In this paper, we provide methods to compute critical ideals of complete multipartite graphs and obtain complete answers for the characteristic ideals of complete multipartite graphs.

We find a relation between the genus of a quotient of a numerical semigroup \(S\) and the genus of \(S\) itself. We use this identity to compute the genus of a quotient of \(S\) when \(S\) has embedding dimension 2. We also exhibit identities relating the Frobenius numbers and the genus of quotients of numerical semigroups that are generated by certain types of arithmetic progressions.

Valuations on finite lattices have been known for a long time. In this paper, we present a combinatorial procedure called modularization that associates a modular lattice to any given finite lattice such that they have the same valuation polytopes.

Gelfand–Tsetlin polytopes arise in representation theory and algebraic combinatorics. One can construct the Gelfand–Tsetlin polytope \(\mathrm{GT}_\lambda\) for any partition \(\lambda = (\lambda _1,\ldots ,\lambda _n)\) of weakly increasing positive integers. The integral points in a Gelfand–Tsetlin polytope are in bijection with semi-standard Young tableau of shape \(\lambda\) and parametrize a basis of the \(\mathrm{GL}_n\)-module with highest weight \(\lambda\). The combinatorial geometry of Gelfand–Tsetlin polytopes has been of recent interest. Researchers have created new combinatorial models for the integral points and studied the enumeration of the vertices of these polytopes. In this paper, we determine the exact formulas for the diameter of the 1-skeleton, \(\mathrm{diam}(\mathrm{GT}_\lambda )\), and the combinatorial automorphism group, \(\mathrm{Aut}(\mathrm{GT}_\lambda )\), of any Gelfand–Tsetlin polytope. We exhibit two vertices that are separated by at least \(\mathrm{diam}(\mathrm{GT}_\lambda )\) edges and provide an algorithm to construct a path of length at most \(\mathrm{diam}(\mathrm{GT}_\lambda )\) between any two vertices. To identify the automorphism group, we study \(\mathrm{GT}_\lambda\) using combinatorial objects called ladder diagrams and examine faces of co-dimension 2.

Brane tilings are infinite, bipartite, periodic, planar graphs that are dual to quivers. In this paper, we study the del Pezzo 2 (dP\(_2\)) quiver and its associated brane tiling which arise in theoretical physics. Specifically, we prove explicit formulas for all cluster variables generated by toric mutation sequences of the dP\(_2\) quiver. Moreover, we associate a subgraph of the dP\(_2\) brane tiling to each toric cluster variable such that the sum of weighted perfect matchings of the subgraph equals the Laurent polynomial of the cluster variable.

In this paper, we work toward answering the following question: given a uniformly random algebra homomorphism from the ring of symmetric functions over \(\mathbb{Z}\) to a finite field \(\mathbb{F}_q\), what is the probability that the Schur function \(s_\lambda\) maps to zero? We show that this probability is always at least \(1/q\) and is asymptotically \(1/q\). Moreover, we give a complete classification of all shapes that can achieve probability \(1/q\). In addition, we identify certain families of shapes for which the events that the corresponding Schur functions are sent to zero are independent. We also look into the probability that Schur functions are mapped to nonzero values in \(\mathbb{F}_q\).

In this paper, we prove that the largest pure partial plane of order 6 has size 25. At the same time, we classify all pure partial planes of order 6 and size 25 up to isomorphism. Our major approach is computer search. The search space is very large so we use combinatorial arguments to rule out some of the cases. For the remaining cases, we subdivide each search by phases and use multiple checks to reduce search space via symmetry.

Varchenko (Adv Math 97(1):110–144, 1993) defined the Varchenko matrix associated with any real hyperplane arrangement and computed its determinant. In this paper, we show that the Varchenko matrix of a hyperplane arrangement has a diagonal form if and only if it is semigeneral, i.e., without degeneracy. In the case of semigeneral arrangement, we present an explicit computation of the diagonal form via combinatorial arguments and matrix operations, thus giving a combinatorial interpretation of the diagonal entries.