Permutation Patterns

Permutohedron

Birkhoff Polytope

Pattern-Avoiding Polytopes
Robert Davis
joint with Bruce Sagan
Michigan State University

1 August 2016

Open Questions

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Pattern Avoidance
Let Sn denote the symmetric group on 1, 2, . . . , n, π ∈ Sk andσ ∈ Sn , written as words.
Definition
Say σ contains the pattern π if there is some substring of σ
whose elements have the same relative order as those in π. If nosuch substring exists, then σ avoids the pattern π. If Π ⊆ S,
then σ avoids Π if σ avoids every element of Π.
So 526413 does not avoid 132 while 453621 does.
Denote byAvn (Π) := {σ ∈ Sn | σ avoids Π}the avoidance class of Π.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Pattern Avoidance
A simple yet difficult question: given Π, determine | Avn (Π)|.
If π = a1 a2 . . . ak , call
π r := ak an−1 . . . a1
the reversal of π and
π c := (k − a1 + 1)(k − a2 + 1) . . . (k − ak + 1)
the complement of π. Then | Avn (π)| = | Avn (π r )| = | Avn (π c )|.
Definition
Say π1 and π2 are Wilf equivalent, written π1 ≡ π2 , if
| Avn (π1 )| = | Avn (π2 )| for all n.
Wilf equivalence is an equivalence relation on S.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Pattern Avoidance

So π ≡ π r ≡ π c . In fact, π is Wilf equivalent to any permutation
obtained by acting on its diagram by the dihedral group of thesquare. These are called the trivial Wilf equivalences.
Example4261573≡4271536≡4627315≡2537164

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Pattern Avoidance
Theorem (MacMahon (1915) and Knuth (1968))
If π ∈ S3 , then for all n, | Avn (π)| = Cn , the nth Catalan
number.
Theorem (Erdős-Szekeres (1935))
For any positive integers a, b, every permutation of length atleast (a − 1)(b − 1) + 1 contains the patterns 123 . . . a orb(b − 1)(b − 2) . . . 1.
Theorem (Billey, Burdzy, and Sagan (2012))
For all n, | Avn (132, 312)| = 2n−1 .

Permutation PatternsPermutohedron

Birkhoff Polytope

Open Questions

Why study pattern avoidance?

Stack-sortable permutations
A permutation is stack-sortable if and only if it avoids 231(Knuth, 1968)

Permutation statistics
Almost all known Mahonian permutation statistics reallybelong to a class of 14 statistics, if the use of vincularpatterns is allowed (Babson and Steingrı́msson, 2000)

Classifying smooth / factorial / Gorenstein Schubertvarieties using bivincular patterns (Úlfarsson, 2010)

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Ehrhart TheoryDefinition
For a lattice polytope P ⊆ Rn , its Ehrhart polynomial is
LP (m) := |mP ∩ Rn |,and its Ehrhart series isEP (t) :=XLP (m)tmm≥0=h∗P (t).
(1 − t)dim P +1

The numerator h∗P (t) is the h∗ -polynomial of P and its list ofcoefficients h∗ (P ) := (h∗0 , . . . , h∗d ) is the h∗ -vector of P .

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Two Big Questions

1When is h∗ (P ) palindromic?
This happens exactly when P is Gorenstein, a property thatthat is often reasonably detectable if a hyperplane
description of P is known.

2

When is h∗ (P ) unimodal? Various sufficient conditions areknown, but necessary conditions are not as clear.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Permutohedra
Definition
The permutohedron is defined as
Pn := conv{(a1 , . . . , an ) ∈ Rn | a1 . . . an ∈ Sn }.
Some quick facts about Pn :1

invariant under the action of Sn

2

simple zonotope3

its Ehrhart polynomial isLPn (m) =n−1
X

fin mi ,i=0

where fin is the number of labeled forests on n vertices
with i edges.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Permutohedra

Definition
For Π ⊆ S, definePn (Π) := conv{(a1 , . . . , an ) | a1 . . . an ∈ Avn (Π)}
to be the Π-avoiding permutohedron.
So if Π = ∅, then Pn (Π) = Pn .
Important note: this is not a subclass of generalized
permutohedra introduced by Postnikov. This fact can beverified by comparing normal fans and using a theorem ofPostnikov, Reiner, and Williams.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Permutohedra

Pn (π) is unimodularly equivalent to both Pn (π r ) and Pn (π c ).
But that’s about where it stops.
Example (Trivial Wilf equivalence 6⇒ unimodular equivalence)
Choose π = 1423 and π 0 = 2431. These are related by a90-degree rotation, but P5 (π) has 48 facets while P5 (π 0 ) only
has 46.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Permutohedra
Theorem (D. and Sagan)
If Π = {132, 312}, then Pn (Π) is a rectangular parallelepipedwith Ehrhart polynomialn−1X
i=0(n − 1)!
mi(n − i − 1)!

This extends the previous result | Avn (132, 312)| = 2n−1 .
Corollary
The number of interior lattice points of Pn (132, 312) is thenumber of derangements of Sn−1 .
(Follows from Ehrhart-Macdonald reciprocity)Permutation Patterns

Permutohedron

Birkhoff Polytope

Π-avoiding Permutohedra

Theorem (Beck, Jochemko, McCullough, in preparation)
Every lattice zonotope has a unimodal h∗ -vector.
Corollary
For all n, h∗ (Pn (132, 312)) is unimodal.

Open Questions

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Permutohedra

Theorem (D. and Sagan)
If Π = {123, 132}, then Pn (Π) is a combinatorial (but notgeometric!) cube with Ehrhart polynomial
n−1m+1 Y(nm + j)(n − 1)!
j=2(Pn (Π) is a Pitman-Stanley polytope)

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Permutohedra

Proposition (D. and Sagan)
If Π = {123, 132, 312}, then Pn (Π) is a simplex with Ehrhart
polynomial (1 + m)n−1 . Hence h∗P (t) is the Eulerian polynomial
An−1 (t).
Pn (123, 132, 312) is (unimodularly equivalent to) the simplex
containing certain lecture hall partitions. Work of Corteel, Lee,and Savage imply the Ehrhart-theoretic results (an observation
made by Ben Braun).

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Permutohedra

The results for the different avoidance classes were proven invery different ways.
This is common in the world of pattern avoidance.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Birkhoff Polytopes

DefinitionThe n × n Birkhoff polytope is
Bn := conv{M ∈ Rn×n | M a matrix for some σ ∈ Sn }Some variations:
1

transportation polytopes

2

permutation polytopes (Burggraf, De Loera, Omar)3

the “symmetric slice” of Bn (Stanley, Jia)

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Birkhoff Polytopes

Definition
For Π ⊆ S, define
Bn (Π) := conv{M ∈ Rn×n | M a matrix for some σ ∈ Avn (Π)}
to be the Π-avoiding Birkhoff polytope.
This time, if π ∈ Sk and π 0 are trivially Wilf equivalent, thenBn (π) and Bn (π 0 ) are unimodularly equivalent.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Alternating permutations

Definition
A permutation a1 a2 . . . an ∈ Sn is alternating if
a1 < a2 > a3 < a4 > a5 < · · · .
f n (Π) denote the alternating permutations in Sn that
Let Aven (Π).
avoid Π. Analogously define B
These could also be described as Bn (Π) for an appropriate Π if
we allow vincular patterns.
Our focus will be on the specific polytopes Bn (132, 312) anden (123).
BPermutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Π-avoiding Birkhoff Polytopes

Proposition (D. and Sagan)
For all n, ndim Bn (132, 312) =2anden (123) =dim B

dn/2e2



Beyond knowing the number of vertices of each, thecombinatorial structures of these are completely unknown.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Π-avoiding Birkhoff Polytopes

Theorem (Stanley (1970s), Athanasiadis (2005))
For all n, h∗ (Bn ) is palindromic and unimodal.
What can we say about h∗ (Bn (Π))?

Open QuestionsPermutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Main Conjecture

Conjecture (D. and Sagan)en (123) are palindromic
The h∗ -vectors of Bn (132, 312) and B
and unimodal.
Broad strategy:
1

Show that these polytopes have regular, unimodular
triangulations

2

Show that these polytopes are GorensteinPermutation Patterns

Permutohedron

Birkhoff Polytope

Open Questionsen (Π)The posets Qn (Π) and Q

Definition
The right weak (Bruhat) order on Sn is defined as σ l σ 0 if
σ 0 = σsi for some simple transposition si and σ 0 has more
inversions than σ. The left weak (Bruhat) order is defined
analogously.
Let Qn (132, 312) be the poset on Avn (132, 312) induced frome n (123) to be the poset on
the right weak order on Sn , and Q
f n (123) induced from the left weak order on Sn .
Av

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

e8 (123)
Examples: Q5 (132, 312) and Q
54321
78563412

45321
43521
43251

78562413 78463512 68573412
34521
78462513 68572413 68473512

43215

34251
34215

78362514

32451
32415

32145

23451

68472513

68372514

58472613

23415
58372614
23145
21345
12345

58473612

48372615

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questionsen (Π)The posets Qn (Π) and Q
Theorem (D. and Sagan)
The following isomorphisms hold:Qn (132, 312) ∼= M (n − 1),
where M (k) is the lattice of shifted Young diagrams with largest
part at most k, and∗e n (123) ∼Q,= Ddn/2ewhere Dk is the lattice of Dyck paths of length 2k such that if
d1 , d2 ∈ Dk , then d1 < d2 if d1 lies entirely underneath d2 .

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questionsen (Π)The posets Qn (Π) and Q

From here, we want to use the following facts:
distributive lattices have EL-labelings
posets with EL-labelings have shellable order complexes
given a lattice polytope with a shellable unimodular
triangulation, its h∗ -vector can be computed based on
information about the shelling order
Goal: show that the order complexes of Qn (132, 312) ande n (123) induce shellable unimodular triangulations ofQen (123).
Bn (132, 312) and B

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

The Commutative Algebra

Conjecture (D. and Sagan)en (123) have flag, regular unimodular
Bn (132, 312) and B
triangulations.
Theorem (Sturmfels)
For a lattice polytope P , the initial ideals of the toric ideal IP
are in bijection with the regular triangulations of P . The initial
ideal of IP is squarefree if and only if the corresponding
triangulation of P is unimodular.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Watermelons, Stars, and Fermi Configurations
Definition
A watermelon W l,k is the digraph with vertices{(−i, −j) ∈ Z2 | 0 ≤ i ≤ l, 0 ≤ j ≤ k, j ≤ i}with an arc from a to b if b − a ∈ {−e1 , −e2 }. A star graph Sn
is the graph whose vertex set is{(−i, −j) ∈ Z2 | i, j ≥ 0, i + j ≤ n}with arcs formed the same way as with watermelons.
To make later definitions simpler, we introduce a unique sink v
for Sn by including an arc from the points (−i, −n + i) to v.

Permutation Patterns

Permutohedron

Examples: W 4,3 and S3Birkhoff Polytope

Open Questions

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Watermelons, Stars, and Fermi Configurations
Definition
A Fermi configuration in a digraph H with source u and sink v
is a collection of distinct, noncrossing paths from u to v. A
Fermi configuration is maximal if no additional distinct
noncrossing paths from u to v can be included in theconfiguration.
Example (A maximal Fermi configuration in W 3,2 )
p1

p2

p3

p4

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Watermelons, Stars, and Fermi Configurations
Definition
A triple of adjacent paths in a maximal Fermi configuration iscalled a flipflop if the two 2-dimensional faces it bounds shareno edges of the central path. If the central path goes to theright of the first 2-dimensional face it encounters, then the pathis called flopped. Otherwise, it is flipped.
ExampleThe configuration on the previous slide contains the flopped
walk (p2 , p3 , p4 ) but no flipped walks.
p1
p2

p2

p3

p3

p4

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open QuestionsWatermelons, Stars, and Fermi Configurations

Theorem (Arrowsmith, Bhatti, and Essam (2012))
Suppose H is a digraph with unique source and sink, and that H
has a unique minimal-cardinality Fermi configuration covering
all of its arcs. Let ϕk (H) denote the number of maximal Fermi
configurations in H that contain k flopped walks. Then thepolynomialXΦ(H; t) =ϕk (H)tki≥0

has palindromic coefficients.

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Watermelons, Stars, and Fermi Configurations

Sagan and I have shown that if the previously-mentioned
conjecture holds, then Φ(Sn ; t) is the h∗ -polynomial forBn (132, 312) and Φ(W bn/2c,bn/2c ; t) is the h∗ -polynomial foren (123).
BIt appears that the coefficients of Φ(W k,m ; t) are unimodal for
all k and m, but it is not immediately obvious how to choose Π
so that Φ(W k,m ; t) = Bn (Π) (or if any such Π exists)

Permutation Patterns

Permutohedron

Birkhoff Polytope

Open Questions

Open Questions
12

Is there a nice combinatorial proof for the number ofinterior lattice points of Pn (132, 312)?
For “nice” special classes of Π,1234

what is the combinatorial structure of Pn (Π) or Bn (Π)?
what is Vol(Pn (Π)), Vol(Bn (Π))?
what is the Ehrhart polynomial for Pn (Π)?
what is the h∗ -vector of Bn (Π)?

3

What happens if we consider classes of vincular orbivincular patterns?

4

For which choices of Π is Bn (Π) IDP? Gorenstein?

5

What are the homotopy types of Qn (Π)? (in general theirorder complexes aren’t necessarily spheres, or even
Cohen-Macaulay)