Algebraic and combinatorial structures on Baxter permutations

Algebraic and combinatorial structures on Baxter permutations

Samuele Giraudo

Universit´e de Marne-la-Vall´ee

66th S´eminaire Lotharingien de Combinatoire March 8, 2011

Contents

Hopf algebra of permutations and construction of subalgebras The Hopf algebra of permutations

Equivalence relations and quotients of the free monoid More structure on quotient monoids

From quotient monoids to Hopf subalgebras

Algebraic constructions on Baxter permutations The Baxter combinatorial family

The Baxter monoid

A Robinson-Schensted-like correspondence The Baxter lattice

The Baxter Hopf algebra

Contents

Hopf algebra of permutations and construction of subalgebras The Hopf algebra of permutations

Equivalence relations and quotients of the free monoid More structure on quotient monoids

From quotient monoids to Hopf subalgebras

The vector space of permutations

LetFQSym_nbe theQ-vector space based on permutations of{1, . . . ,n}

and

FQSym:=M

n≥0

FQSym_n,

be thevector space of permutations.

Its elements can be handled through thefundamental basis{Fσ}_σ∈S. A product and a coproduct can be added to this structure to form the Hopf algebra ofFree quasi-symmetric functions, also known as the Malvenuto-Reutenauer Hopf algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example: F12·F21=

F1243+F1423+F1432+F4123+F4132+F4312.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=

F1243+F1423+F1432+F4123+F4132+F4312.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F_••••+F_••••+F_••••+F_••••+F_••••+F_••••.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F_12••+F_••••+F_••••+F_••••+F_••••+F_••••.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F_12••+F_1•2•+F_••••+F_••••+F_••••+F_••••.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F_12••+F_1•2•+F_1••2+F_••••+F_••••+F_••••.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F_12••+F_1•2•+F_1••2+F_•12•+F_••••+F_••••.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F_12••+F_1•2•+F_1••2+F_•12•+F_•1•2+F_••••.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F_12••+F_1•2•+F_1••2+F_•12•+F_•1•2+F_••12.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F1243+F_1•2•+F_1••2+F_•12•+F_•1•2+F_••12.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F1243+F1423+F_1••2+F_•12•+F_•1•2+F_••12.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F1243+F1423+F1432+F_•12•+F_•1•2+F_••12.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21 =F1243+F1423+F1432+F4123+F_•1•2+F_••12.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F1243+F1423+F1432+F4123+F4132+F_••12.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F1243+F1423+F1432+F4123+F4132+F4312.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

A product in FQSym

FQSymis endowed by theshifted shuffle product:

Fσ·Fν := X

π∈σν

Fπ.

For example:

F12·F21=F1243+F1423+F1432+F4123+F4132+F4312.

I This product is associativeandnon-commutative;

I It admitsFasunit;

I It isgraded: ·:FQSym_n⊗FQSym_m→FQSym_n+m. Hence, (FQSym,·) is a graded unital associative algebra.

Right permutohedron order

Letσ, ν∈S_n. σis covered byν ifσ=uabv andν =ubav where a<b. This covering relation spans theright permutohedron.

Here is that of permutations of size 4:

1234 2134

2143

1243 1324

2314 3124 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

The elementsF_π appearing in a productF_σ·F_ν form an intervalof the permutohedron.

Right permutohedron order

Letσ, ν∈S_n. σis covered byν ifσ=uabv andν =ubav where a<b. This covering relation spans theright permutohedron.

Here is that of permutations of size 4:

1234

2134

2143

1243 1324

2314 3124 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

The elementsF_π appearing in a productF_σ·F_ν form an intervalof the permutohedron.

Right permutohedron order

Letσ, ν∈S_n. σis covered byν ifσ=uabv andν =ubav where a<b. This covering relation spans theright permutohedron.

Here is that of permutations of size 4:

1234

2134

2143

1243 1324

2314 3124 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

The elementsF_π appearing in a productF_σ·F_ν form an intervalof the permutohedron.

Right permutohedron order

Letσ, ν∈S_n. σis covered byν ifσ=uabv andν =ubav where a<b. This covering relation spans theright permutohedron.

Here is that of permutations of size 4:

1234 2134

2143

1243 1324

2314 3124 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

The elementsF_π appearing in a productF_σ·F_ν form an intervalof the permutohedron.

Right permutohedron order

Letσ, ν∈S_n. σis covered byν ifσ=uabv andν =ubav where a<b. This covering relation spans theright permutohedron.

Here is that of permutations of size 4:

1234 2134

2143

1243 1324

2314 3124 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

The elementsF_π appearing in a productF_σ·F_ν form an intervalof the permutohedron.

Right permutohedron order

Letσ, ν∈S_n. σis covered byν ifσ=uabv andν =ubav where a<b. This covering relation spans theright permutohedron.

Here is that of permutations of size 4:

1234 2134

2143

1243 1324

2314 3124 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

The elementsF_π appearing in a productF_σ·F_ν form an intervalof the permutohedron.

Right permutohedron order

Letσ, ν∈S_n. σis covered byν ifσ=uabv andν =ubav where a<b. This covering relation spans theright permutohedron.

Here is that of permutations of size 4:

1234 2134

2143

1243 1324

2314 3124 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

The elementsF_π appearing in a productF_σ·F_ν form an intervalof the permutohedron.

Right permutohedron order

Letσ, ν∈S_n. σis covered byν ifσ=uabv andν =ubav where a<b. This covering relation spans theright permutohedron.

Here is that of permutations of size 4:

1234 2134

2143

1243 1324

2314 3124 1342 1423

2341 3214 2413 3142 4123 1432

3241 2431 3412 4213 4132

3421 4231 4312

4321

The elementsF_π appearing in a productF_σ·F_ν form an intervalof the permutohedron.

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives: c a b b d a a b d

1 2 3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d 1

2 3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2

3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4

5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5

6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5 6

7

8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5 6

7 8

9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

Standardization process

LetA:={a<b<c< . . .}be a totally ordered infinite alphabet.

Thestandardization processstd is an algorithm computing a permutation σfrom a wordu∈A^∗ such thatσhas the same inversions thanu.

For example, the computation of std(cabbdaabd) gives:

c a b b d a a b d

1 2 3

4 5 6

7 8 9

7 1 4 5 8 2 3 6 9

A coproduct in FQSym

FQSymis endowed by thedeconcatenation coproduct:

∆ (Fσ) := X

u.v=σ

Fstd(u)⊗Fstd(v).

For example:

∆ () =

F⊗F4123+F1⊗F123+F21⊗F12+F312⊗F1+F4123⊗F.

I This coproduct is coassociative;

I It isnon-cocommutative;

I It isgraded: ∆ :FQSym_n→L

i+j=nFQSym_i⊗FQSym_j. Hence, (FQSym,∆) is a graded coassociative coalgebra.

A coproduct in FQSym

FQSymis endowed by thedeconcatenation coproduct:

∆ (Fσ) := X

u.v=σ

Fstd(u)⊗Fstd(v).

For example:

∆ (F4123) =

F⊗F4123+F1⊗F123+F21⊗F12+F312⊗F1+F4123⊗F.

I This coproduct is coassociative;

I It isnon-cocommutative;

I It isgraded: ∆ :FQSym_n→L

i+j=nFQSym_i⊗FQSym_j. Hence, (FQSym,∆) is a graded coassociative coalgebra.

A coproduct in FQSym

FQSymis endowed by thedeconcatenation coproduct:

∆ (Fσ) := X

u.v=σ

Fstd(u)⊗Fstd(v).

For example:

∆ F_|4123

=F⊗F4123

+F1⊗F123+F21⊗F12+F312⊗F1+F4123⊗F.

I This coproduct is coassociative;

I It isnon-cocommutative;

I It isgraded: ∆ :FQSym_n→L

i+j=nFQSym_i⊗FQSym_j. Hence, (FQSym,∆) is a graded coassociative coalgebra.

A coproduct in FQSym

FQSymis endowed by thedeconcatenation coproduct:

∆ (Fσ) := X

u.v=σ

Fstd(u)⊗Fstd(v).

For example:

∆ F_4|123

=F⊗F4123+F1⊗F123

+F21⊗F12+F312⊗F1+F4123⊗F.

I This coproduct is coassociative;

I It isnon-cocommutative;

I It isgraded: ∆ :FQSym_n→L

i+j=nFQSym_i⊗FQSym_j. Hence, (FQSym,∆) is a graded coassociative coalgebra.

A coproduct in FQSym

FQSymis endowed by thedeconcatenation coproduct:

∆ (Fσ) := X

u.v=σ

Fstd(u)⊗Fstd(v).

For example:

∆ F_41|23

=F⊗F4123+F1⊗F123+F21⊗F12

+F312⊗F1+F4123⊗F.

I This coproduct is coassociative;

I It isnon-cocommutative;

I It isgraded: ∆ :FQSym_n→L

i+j=nFQSym_i⊗FQSym_j. Hence, (FQSym,∆) is a graded coassociative coalgebra.

A coproduct in FQSym

FQSymis endowed by thedeconcatenation coproduct:

∆ (Fσ) := X

u.v=σ

Fstd(u)⊗Fstd(v).

For example:

∆ F_412|3

=F⊗F4123+F1⊗F123+F21⊗F12+F312⊗F1

+F4123⊗F.

I This coproduct is coassociative;

I It isnon-cocommutative;

I It isgraded: ∆ :FQSym_n→L

i+j=nFQSym_i⊗FQSym_j. Hence, (FQSym,∆) is a graded coassociative coalgebra.

A coproduct in FQSym

FQSymis endowed by thedeconcatenation coproduct:

∆ (Fσ) := X

u.v=σ

Fstd(u)⊗Fstd(v).

For example:

∆ F_4123|

=F⊗F4123+F1⊗F123+F21⊗F12+F312⊗F1+F4123⊗F.

I This coproduct is coassociative;

I It isnon-cocommutative;

I It isgraded: ∆ :FQSym_n→L

i+j=nFQSym_i⊗FQSym_j. Hence, (FQSym,∆) is a graded coassociative coalgebra.

A coproduct in FQSym

FQSymis endowed by thedeconcatenation coproduct:

∆ (Fσ) := X

u.v=σ

Fstd(u)⊗Fstd(v).

For example:

∆ (F4123) =F⊗F4123+F1⊗F123+F21⊗F12+F312⊗F1+F4123⊗F.

I This coproduct is coassociative;

I It isnon-cocommutative;

I It isgraded: ∆ :FQSym_n→L

i+j=nFQSym_i⊗FQSym_j. Hence, (FQSym,∆) is a graded coassociative coalgebra.

FQSym as a combinatorial Hopf algebra

These algebra and coalgebra structures are compatible,i.e., ∆ is an algebra morphism:

∆ (Fσ·Fν) = ∆ (Fσ)·∆ (Fν). Hence,FQSymis a bialgebra.

SinceFQSymis graded and connected, it is aHopf algebra.

We use the heuristic term ofcombinatorial Hopf algebra (CHA)for graded and connected Hopf algebras based on combinatorial objects.

Contents

Hopf algebra of permutations and construction of subalgebras The Hopf algebra of permutations

Equivalence relations and quotients of the free monoid More structure on quotient monoids

From quotient monoids to Hopf subalgebras

Equivalence relations on words

We define equivalence relations on words ofA^∗ by taking the reflexive, symmetric, and transitive closure of arewriting rule .

We are interested by equivalence relations onA^∗ that are congruences:

Definition

The equivalence relation≡is a congruenceif for all u,u⁰,v,v⁰ ∈A^∗, u≡v and u⁰≡v⁰ imply u.u⁰≡v.v⁰.

In this way,A^∗/_≡ is a quotient monoidof the free monoid.

An example: The plactic equivalence relation

For example, the rewriting rule

. . .acb. . . . . .cab. . . if a≤b<c, . . .bac. . . . . .bca. . . if a<b≤c,

defines the well-knownplactic equivalence relation ≡_P. A^∗/_≡P is the plactic monoid.

Here is the plactic equivalence class of 31542: 31542

35142

35412 53142

53412

An example: The plactic equivalence relation

For example, the rewriting rule

. . .acb. . . . . .cab. . . if a≤b<c, . . .bac. . . . . .bca. . . if a<b≤c,

defines the well-knownplactic equivalence relation ≡_P. A^∗/_≡P is the plactic monoid.

Here is the plactic equivalence class of 31542:

31542

35142

35412 53142

53412

An example: The plactic equivalence relation

For example, the rewriting rule

. . .acb. . . . . .cab. . . if a≤b<c, . . .bac. . . . . .bca. . . if a<b≤c,

defines the well-knownplactic equivalence relation ≡_P. A^∗/_≡P is the plactic monoid.

Here is the plactic equivalence class of 31542:

31542

35142

35412 53142

53412

An example: The plactic equivalence relation

For example, the rewriting rule

. . .acb. . . . . .cab. . . if a≤b<c, . . .bac. . . . . .bca. . . if a<b≤c,

defines the well-knownplactic equivalence relation ≡_P. A^∗/_≡P is the plactic monoid.

Here is the plactic equivalence class of 31542:

31542 35142

35412 53142

53412

An example: The plactic equivalence relation

For example, the rewriting rule

. . .acb. . . . . .cab. . . if a≤b<c, . . .bac. . . . . .bca. . . if a<b≤c,

defines the well-knownplactic equivalence relation ≡_P. A^∗/_≡P is the plactic monoid.

Here is the plactic equivalence class of 31542:

31542 35142

35412 53142

53412

An example: The plactic equivalence relation

For example, the rewriting rule

. . .acb. . . . . .cab. . . if a≤b<c, . . .bac. . . . . .bca. . . if a<b≤c,

defines the well-knownplactic equivalence relation ≡_P. A^∗/_≡P is the plactic monoid.

Here is the plactic equivalence class of 31542:

31542 35142 35412

53142 53412

An example: The plactic equivalence relation

For example, the rewriting rule

. . .acb. . . . . .cab. . . if a≤b<c, . . .bac. . . . . .bca. . . if a<b≤c,

defines the well-knownplactic equivalence relation ≡_P. A^∗/_≡P is the plactic monoid.

Here is the plactic equivalence class of 31542:

31542 35142

35412 53142

53412

Contents

Hopf algebra of permutations and construction of subalgebras The Hopf algebra of permutations

Equivalence relations and quotients of the free monoid More structure on quotient monoids

From quotient monoids to Hopf subalgebras

Compatibility with the destandardization process

Denote by ev(u) the non-decreasing rearrangement ofu. For example:

ev(babcaac) =aaabbcc.

Definition

Let≡be a congruence. The monoidA^∗/≡ is compatible with the destandardization processif for allu,v∈A^∗,

u≡v iff std(u)≡std(v) and ev(u) = ev(v).

Compatibility with the restriction of alphabet intervals

LetS⊆Aandube a word. Denote byu_|S the longest subword of u made of letters ofS. For example:

bcacca_|{a,b}=baa.

Definition

Let≡be a congruence. The monoidA^∗/≡ is compatible with the restriction of alphabet intervalsif for all intervalLofAandu,v ∈A^∗,

u≡v implies u_|L≡v_|L.

Contents

Hopf algebra of permutations and construction of subalgebras The Hopf algebra of permutations

Equivalence relations and quotients of the free monoid More structure on quotient monoids

From quotient monoids to Hopf subalgebras

Construction of Hopf subalgebras of FQSym

Let≡be an equivalence relation. For all equivalence class C ofS/≡, let us define the following element ofFQSym:

PC :=X

σ∈C

Fσ.

Theorem

If≡is a congruence andA^∗/_≡ is compatible with the destandardization process and with the restriction of alphabet intervals, then, the family {PC}_C∈S/

≡ spans a Hopf subalgebra ofFQSym.

Some Hopf subalgebras of FQSym

FQSym Permutations 1,1,2,6,24,120,720

FSym Std. Young. tab.

1,1,2,4,10,26,76

Sym Compositions 1,1,2,4,8,16,32

PBT Binary trees 1,1,2,5,14,42,132 DSym⁽³⁾

– 1,1,2,6,18,54,162

DSym⁽⁴⁾ – 1,1,2,6,24,96,384

Bell Set partitions 1,1,2,5,15,52,203

Some Hopf subalgebras of FQSym

FQSym Permutations 1,1,2,6,24,120,720

FSym Std. Young. tab.

1,1,2,4,10,26,76

Sym Compositions 1,1,2,4,8,16,32

PBT Binary trees 1,1,2,5,14,42,132 DSym⁽³⁾

– 1,1,2,6,18,54,162

DSym⁽⁴⁾ – 1,1,2,6,24,96,384

Bell Set partitions 1,1,2,5,15,52,203

Some Hopf subalgebras of FQSym

FQSym Permutations 1,1,2,6,24,120,720

FSym Std. Young. tab.

1,1,2,4,10,26,76

Sym Compositions 1,1,2,4,8,16,32

PBT Binary trees 1,1,2,5,14,42,132 DSym⁽³⁾

– 1,1,2,6,18,54,162

DSym⁽⁴⁾ – 1,1,2,6,24,96,384

Bell Set partitions 1,1,2,5,15,52,203

Some Hopf subalgebras of FQSym

FQSym Permutations 1,1,2,6,24,120,720

FSym Std. Young. tab.

1,1,2,4,10,26,76

Sym Compositions 1,1,2,4,8,16,32

PBT Binary trees 1,1,2,5,14,42,132

DSym⁽³⁾ – 1,1,2,6,18,54,162

DSym⁽⁴⁾ – 1,1,2,6,24,96,384

Bell Set partitions 1,1,2,5,15,52,203

Some Hopf subalgebras of FQSym

FQSym Permutations 1,1,2,6,24,120,720

FSym Std. Young. tab.

1,1,2,4,10,26,76

Sym Compositions 1,1,2,4,8,16,32

PBT Binary trees 1,1,2,5,14,42,132 DSym⁽³⁾

– 1,1,2,6,18,54,162

DSym⁽⁴⁾ – 1,1,2,6,24,96,384

Bell Set partitions 1,1,2,5,15,52,203

Some Hopf subalgebras of FQSym

FQSym Permutations 1,1,2,6,24,120,720

FSym Std. Young. tab.

1,1,2,4,10,26,76

Sym Compositions 1,1,2,4,8,16,32

PBT Binary trees 1,1,2,5,14,42,132 DSym⁽³⁾

– 1,1,2,6,18,54,162

DSym⁽⁴⁾ – 1,1,2,6,24,96,384

Bell Set partitions 1,1,2,5,15,52,203

Combinatorial structures and Hopf subalgebras

The construction of Hopf subalgebras ofFQSymfrom an equivalence relation often leads to the construction ofnew combinatorial structures:

CHA Objects Monoid Ins. Alg. Partial order

FQSym permutations A^∗ trivial permutohedron FSym std. Young tab. plactic R-S Reiner order

PBT binary trees sylvester bst^∼ Tamari lattice

Sym compositions hypoplactic K-T hypercube

Bell set partitions Bell Bell Bell order

Aim of this work

Provide similar structures on Baxter permutations.

Contents

Algebraic constructions on Baxter permutations The Baxter combinatorial family

The Baxter monoid

A Robinson-Schensted-like correspondence The Baxter lattice

The Baxter Hopf algebra

Baxter permutations

Definition

The permutationσis a Baxter permutation[Baxter, 1964]if it avoids the generalized permutation patterns

2−41−3 and

3−14−2.

For example:

I 561382479

is not a Baxter permutation;

I , 1, 1234, 2143

are Baxter permutations.

Baxter permutations

Definition

The permutationσis a Baxter permutation[Baxter, 1964]if it avoids the generalized permutation patterns

2−41−3 and

3−14−2.

For example:

I 561382479

is not a Baxter permutation;

I , 1, 1234, 2143

are Baxter permutations.

Baxter permutations

Definition

The permutationσis a Baxter permutation[Baxter, 1964]if it avoids the generalized permutation patterns

2−41−3 and

3−14−2.

For example:

I 561382479 is not a Baxter permutation;

I , 1, 1234, 2143

are Baxter permutations.

Baxter permutations

Definition

The permutationσis a Baxter permutation[Baxter, 1964]if it avoids the generalized permutation patterns

2−41−3 and

3−14−2.

For example:

I 561382479 is not a Baxter permutation;

I , 1, 1234, 2143 are Baxter permutations.

Baxter objects

Theorem

The numberbn of Baxter permutations of sizenis bn=

n

X

k=1 n+1 k−1

n+1 k

n+1 k+1

n+1 1

n+1 2

.

The sequence (b_n)_n≥0begins as

1,1,2,6,22,92,422,2074,10754.

This enumerates also

I pairs of twin binary trees[Dulucq, Guibert, 1994];

I rectangular partitions[Yao and al., 2003];

I planar bipolar orientations[Bousquet-M´elou and al., 2010]; and many other objects.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0

1 0

0 1 0 1

The canopy of this binary tree is

0100101.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0

1 0

0 1 0 1

The canopy of this binary tree is

0100101.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0

1 0

0 1 0 1

The canopy of this binary tree is 0

100101.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0 1

0

0 1 0 1

The canopy of this binary tree is 01

00101.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0

1 0

0 1 0 1

The canopy of this binary tree is 010

0101.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0

1 0 0

1 0 1

The canopy of this binary tree is 0100

101.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0

1 0

0 1

0 1

The canopy of this binary tree is 01001

01.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0

1 0

0 1 0

1

The canopy of this binary tree is 010010

1.

Viennot’s canopy

Thecanopyof a binary treeT is the word on the alphabet{0,1}

obtained by browsing the leaves ofT from left to right except the first and the last one, writing 0 if the considered leaf is right-oriented, 1 otherwise.

For example:

0

1 0

0 1 0 1

The canopy of this binary tree is 0100101.

Pairs of twin binary trees

Definition

A pair (T_L,T_R) of binary trees is apair of twin binary treesif the canopies ofT_L andT_R are complementary.

The six pairs of twin binary trees with 3 nodes are

, , ,

, , .

Theorem

The set of pairs of twin binary trees withnnodes is in bijection with the set of Baxter permutations of sizen.

Contents

Algebraic constructions on Baxter permutations The Baxter combinatorial family

The Baxter monoid

A Robinson-Schensted-like correspondence The Baxter lattice

The Baxter Hopf algebra

The Baxter monoid

Definition

TheBaxter equivalence relation ≡B is defined from the Baxter rewriting rule where:

. . .cu adv b. . . . . .cudav b. . . ifa≤b<c≤d, . . .bu dav c. . . . . .buadv c. . . ifa<b≤c<d.

On permutations, one hasσ ν iff

σ=u.ad.v and ν=u.da.v with u_|[a,d]6=6=v_|[a,d].

We callA^∗/_≡B theBaxter monoid.

An example of Baxter equivalence class

The Baxter equivalence class of 3125647 is

3125647

3152647

3156247 3512647

3516247

3561247

An example of Baxter equivalence class

The Baxter equivalence class of 3125647 is

3125647

3152647

3156247 3512647

3516247

3561247

An example of Baxter equivalence class

The Baxter equivalence class of 3125647 is

3125647

3152647

3156247 3512647

3516247

3561247

An example of Baxter equivalence class

The Baxter equivalence class of 3125647 is

3125647

3152647

3156247 3512647

3516247

3561247

An example of Baxter equivalence class

The Baxter equivalence class of 3125647 is

3125647

3152647

3156247

3512647

3516247

3561247

An example of Baxter equivalence class

The Baxter equivalence class of 3125647 is

3125647

3152647

3156247 3512647

3516247

3561247

Structure properties of the Baxter monoid

Proposition

The Baxter monoid is compatible with the destandardization process.

Proposition

The Baxter monoid is compatible with the restriction of alphabet intervals.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c 123, and hence (123)^#= 123;

I 4312−^∼→2134−→^c 3421, and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→

321−→^c 123, and hence (123)^#= 123;

I 4312−^∼→2134−→^c 3421, and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c

123, and hence (123)^#= 123;

I 4312−^∼→2134−→^c 3421, and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c 123,

and hence (123)^#= 123;

I 4312−^∼→2134−→^c 3421, and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c 123, and hence (123)^#= 123;

I 4312−^∼→2134−→^c 3421, and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c 123, and hence (123)^#= 123;

I 4312−^∼→

2134−→^c 3421, and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c 123, and hence (123)^#= 123;

I 4312−^∼→2134−→^c

3421, and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c 123, and hence (123)^#= 123;

I 4312−^∼→2134−→^c 3421,

and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c 123, and hence (123)^#= 123;

I 4312−^∼→2134−→^c 3421, and hence (4312)^#= 3421.

Let ≡_S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Link with the sylvester monoid

TheSch¨utzenberger involution# :S→Sis the composition of two involutions: The mirror image∼and the complementationc.

For example:

I 123−^∼→321−→^c 123, and hence (123)^#= 123;

I 4312−^∼→2134−→^c 3421, and hence (4312)^#= 3421.

Let ≡S be thesylvester equivalenceand ≡_S# be the #-sylvester equivalence.

Proposition

Letσandν be two permutations. Then,

σ≡Bν iff σ≡Sν and σ≡_S#ν.

Contents

Algebraic constructions on Baxter permutations The Baxter combinatorial family

The Baxter monoid

A Robinson-Schensted-like correspondence The Baxter lattice

The Baxter Hopf algebra

The P -symbol

Definition

TheP-symbol of a permutationσis the pair (bst(σ),bst (σ^∼)).

This definition is based on the previous proposition and the following theorem:

Theorem

bst(u^∼) = bst(v^∼) iff u≡_Sv.

Letσbe a permutation. The left member ofP(σ) encodes the

#-sylvester class ofσwhile the second member encodes its sylvester class.

Insertion algorithm

P(σ) is constructed by iteratively inserting the letters ofσand by making well-knownleaf insertionsandroot insertions in binary search trees.

For example, forσ:= 6317425 one has

⊥⊥ −→^{6 6 6} −→³

3 6 3

6

−1

→

1 3

6 1 3

6

−7

→

1 3

6 7

1 3

6 7

−4

→

1 3

4 6

7 1 3

4 6

7 2

−

→

1 2

3 4

6 7 1

2 3

4 6

7

−5

→

1 2

3 4

5 6

7 1

2 3

4 5

6 7

Insertion algorithm

P(σ) is constructed by iteratively inserting the letters ofσand by making well-knownleaf insertionsandroot insertions in binary search trees.

For example, forσ:= 6317425 one has

⊥⊥

−6

→ ^{6 6} −→³

3 6 3

6

−1

→

1 3

6 1 3

6

−7

→

1 3

6 7

1 3

6 7

−4

→

1 3

4 6

7 1 3

4 6

7 2

−

→

1 2

3 4

6 7 1

2 3

4 6

7

−5

→

1 2

3 4

5 6

7 1

2 3

4 5

6 7