10am-11:10am (US Central): Poster Session (Algebra)

Moderator: Bruce Sagan

(This is 8am US Pacific, 11am US Eastern, 3pm GMT, 4pm in the UK, 5pm CEST, 6pm in Israel, 11pm in China, 1am in Sydney, 3am in New Zealand)


Title: Block number and descents of fully commutative elements in Bn

Author: Riccardo Biagioli (Université Claude Bernard Lyon 1)
Joint work with: Eli Bagno (Jerusalem College of Technology), Frédéric Jouhet (Université Claude Bernard Lyon 1), Yuval Roichman (Bar-Ilan University)

Abstract: PP2020_Biagioli_abstract

Poster: Biagioli poster

[Back to the top]

Title: Separable elements and splittings of Weyl groups

Author: Christian Gaetz (MIT)
Joint work with: Yibo Gao (MIT)

Abstract: We introduce separable elements in finite Weyl groups, generalizing the well-studied class of separable (3142- and 2413-avoiding) permutations. These elements are defined in terms of a generalization of the direct and skew sums of permutations to other Weyl groups. We show that separable elements, although initially defined recursively, have a non-recursive characterization in terms of root system pattern avoidance in the sense of Billey and Postnikov.

We prove that the principal 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 equals that of the whole group, answering an open problem of Fan Wei (2012), who proved this result for permutations.

We prove that the multiplication map $W/V \times V \to W$ for a generalized quotient of the symmetric group is always surjective when $V$ 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 show that this multiplication map is a bijection if and only if $V$ 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, answering a question of Bj\”{o}rner and Wachs (1988). 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 two 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 elegant product formulas for the rank generating functions of the principal upper and lower order ideals generated by $w$ in terms of these nested sets.

Poster: Gaetz_poster

[Back to the top]

Title: Self-dual intervals in the Bruhat order

Author: Yibo Gao (MIT)
Joint work with: Christian Gaetz (MIT)

Abstract: We show that the principal order ideal of a permutation w in the strong Bruhat order is self-dual if and only if w avoids 3412, 4231, 34521, 45321, 54123 and 54312. This is to be compared to the well-known result by Carrell and by Lakshmibai and Sandhya, that says the principal order ideal of a permutation in the strong Bruhat order is rank-symmetric if and only if it avoids 3412 and 4231, if and only if the corresponding Schubert variety is smooth.

We exhibit two more equivalent conditions for a permutation w to have a self-dual interval [id, w] in the Bruhat order. One is that the bipartite graph obtained from the Hasse diagram between rank 1 and rank 2 of the interval [id, w] is isomorphic to that between corank 1 and corank 2. This is surprising in contrast to smoothness of a permutation, which cannot be detected by checking the sizes of finitely many ranks. The other equivalent characterization is that w is polished, which is defined as certain products of maximal elements in parabolic subgroups, and this notion naturally generalizes to any finite Coxeter system.

Poster: Gao_poster

[Back to the top]

Title: Boolean elements in the Bruhat order

Author: Kaarel Hänni (MIT)
Joint work with: Yibo Gao (MIT)

Abstract: For a finite Weyl group $W$, we say an element $w\in W$ is \emph{boolean} if the principal order ideal $[e,w]$ in the strong Bruhat order is a boolean lattice. Tenner showed that boolean elements in the symmetric group $S_n$ are precisely the permutations that avoid $321$ and $3412$. She also gave a signed pattern avoidance characterization of boolean elements in types $B$ and $D$, with the number of patterns being $10$ and $20$ respectively. In our paper, we show that $w\in W$ is boolean if and only if it avoids a much smaller set of Billey-Postnikov patterns, which we describe explicitly. Although for types B and D, this could be deduced by an inspection of the list of patterns in Tenner’s result, we provide a new proof from scratch 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. $1$-boolean elements are then precisely the aforementioned boolean elements. 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 that $3$-boolean elements of $S_n$ are not characterized by pattern avoidance.

Poster: Hänni_poster

[Back to the top]

Title: Atoms for signed permutations

Author: Eric Marberg (Hong Kong University of Science and Technology)
Joint work with: Zachary Hamaker (University of Florida)

Abstract: An element of a Coxeter group is fully commutative if any two of its reduced expressions may be connected by a sequence moves swapping commuting factors. An atom for an involution $z$ in a finite Coxeter group is an element $w$ of minimal length such that $wz \leq w$ in (strong) Bruhat order. In the symmetric group, the following are equivalent: (i) an involution is fully commutative, (ii) an involution has a single atom, and (iii) an involution is 321-avoiding. The last condition can be rephrased as the property that an involution does not have a pair of nesting cycles.

For the type B Coxeter group of signed permutations, these three conditions are no longer equivalent. It still holds that a signed involution is fully commutative if and only if it does not have a pair of nesting cycles, where now cycles may include negative integers. We show that the signed involutions with a single atom are characterized by a slightly different pattern avoidance condition: namely, such involutions $z$ are precisely those that do not have a pair of nesting cycles $a < b \leq z(b) < z(a)$ with $z(a) \neq -a$ or $z(b) = -b$. As an application, we compute an exact formula for the number of such “atomic” signed involutions.

These facts are corollaries of stronger results in which we characterize all atoms for an arbitrary signed involution. These results are relevant to efficiently computing a cohomology formula of Brion. The rank $n$ complex general linear group acts on the flag variety for the rank $n$ symplectic group with finitely many orbits. The cohomology class of each orbit closure is a sum of type C Schubert polynomials. The terms in this sum are indexed by a certain subset of atoms for a signed involution, which we explicitly identify.

Poster: Marberg_poster

[Back to the top]

Title: P- and Q-vexillary involutions

Author: Brendan A Pawlowski (University of Southern California)
Joint work with: Zach Hamaker (University of Florida), Eric Marberg (Hong Kong University of Science and Technology)

Abstract: Any permutation has an associated Stanley symmetric function. These symmetric functions are Schur-positive, and have the property that a permutation is vexillary (2143-avoiding) if and only if its Stanley symmetric function equals a single Schur function. We introduce orthogonal and symplectic analogues of these symmetric functions, indexed respectively by involutions and fixed-point-free involutions in the symmetric group. In the same way that ordinary Stanley symmetric functions arise as limits of Schubert polynomials – cohomology representatives for Borel group orbit closures on the type A flag variety – our “involution Stanley symmetric functions” emerge from the Schubert calculus of the orbits of the orthogonal and symplectic groups acting on the flag variety.

Involution Stanley symmetric functions are not only Schur-positive, they are positive combinations of Schur’s P-functions (or Q-functions). We give pattern avoidance criteria on involutions for the associated orthogonal or symplectic Stanley symmetric function to equal a single Schur function, a single Schur P-function, or a single Schur Q-function. As an application, we reprove theorems of Ardila–Serrano and DeWitt characterizing those skew Schur functions which are Schur P-positive, or which equal a Schur P-function.

Poster: Pawlowski_poster

[Back to the top]

Title: Schedules in Square Cases of Social Golfer Problems

Author: Meng Zhang (University of North Georgia)
Joint work with: David Slutzky (University of North Georgia)

Abstract: Social Golfer Problem (SGP) is a combinatorial optimization problem of scheduling n=g*s golfers into g groups of s golfers for w weeks so that no two golfers play in the same group more than one week. An instance of the SGP is denoted by the triple g-s-w. The most common method is to use constraint programming to approach an available schedule. However, even for some small instances and using powerful computers, there are huge difficulties to get suitable and quick solutions. In this talk, we will use permutation to find an available schedule for p^r-p^r-p^r+1 and show that w=p^r+1 is the best possible when g=s=p^r, where p is a prime number and r is a positive integer. And then, we will show the algebraic structure of the solutions for the general p and r.

Poster: Zhang_poster
Video: Zhang_video

[Back to the top]

Back to the Workshop Program