Introduction Bijection between Tamari intervals and flows
Bijection between Tamari intervals and flows on rooted trees
Fr´ ed´ eric Chapoton 1 Gr´ egory Chˆ atel 2 Viviane Pons 3
1
Institut Camille Jordan, Univ. Claude Bernard Lyon
2
Laboratoire d’Informatique Gaspard Monge, Univ. Paris-Est Marne-la-Vall´ ee
3
Fakult¨ at f¨ ur Mathematik, Univ. Wien
26 March 2014
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Introduction
Order on permutations Order on trees
Link between these orders Flows of rooted trees
Bijection between Tamari intervals and flows Main result
Interval-posets Example of bijection
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Transpositions
1 2 3 4 5
1 2 3 4 5
(2, 5)
Simples transpositions
1 2 3 4 5
1 2 3 4 5
(2, 3) = s 2
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Transpositions
1 2 3 4 5
1 2 3 4 5
(2, 5) Simples transpositions
1 2 3 4 5
1 2 3 4 5
(2, 3) = s 2
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order σ
σs i
251436
521436 254136 251463
`(σs i ) = `(σ) + 1
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order σ
σs i
251436
521436 254136 251463
`(σs i ) = `(σ) + 1
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order σ
σs i
251436
521436 254136 251463
`(σs i ) = `(σ) + 1
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order σ
σs i
251436
521436 254136 251463
`(σs i ) = `(σ) + 1
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order σ
σs i
251436
521436 254136 251463
`(σs i ) = `(σ) + 1
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order
123
213 132
231 312
321
1234 2134 1324 1243 2314 3124 2143 1342 1423 3214 2341 3142 2413 4123 1432
3241 2431 3412 4213 4132 3421 4231 4312
4321
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order
123
213 132
231 312
321
1234 2134 1324 1243 2314 3124 2143 1342 1423 3214 2341 3142 2413 4123 1432
3241 2431 3412 4213 4132 3421 4231 4312
4321
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order
123
213 132
231 312
321
1234 2134 1324 1243 2314 3124 2143 1342 1423 3214 2341 3142 2413 4123 1432
3241 2431 3412 4213 4132 3421 4231 4312
4321
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right weak order
123
213 132
231 312
321
1234 2134 1324 1243 2314 3124 2143 1342 1423 3214 2341 3142 2413 4123 1432
3241 2431 3412 4213 4132 3421 4231 4312
4321
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Binary trees Recursive definition:
I empty tree or
I a root with a left and a right subtree
Examples
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Binary trees Recursive definition:
I empty tree or
I a root with a left and a right subtree Examples
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Right rotation
x y
A B
C →
x A y
B C
With x and y being nodes and A, B and C being subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Some results on the Tamari order:
I 1962, Tamari: order on formal bracketing
I 1972, Huang, Tamari: lattice structure
I 2007, Chapoton: number of intervals 2
n(n + 1)
4n + 1
n − 1
I 2013, Pournin: flip distance in the associahedra
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Some results on the Tamari order:
I 1962, Tamari: order on formal bracketing
I 1972, Huang, Tamari: lattice structure
I 2007, Chapoton: number of intervals 2
n(n + 1)
4n + 1
n − 1
I 2013, Pournin: flip distance in the associahedra
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Some results on the Tamari order:
I 1962, Tamari: order on formal bracketing
I 1972, Huang, Tamari: lattice structure
I 2007, Chapoton: number of intervals 2
n(n + 1)
4n + 1
n − 1
I 2013, Pournin: flip distance in the associahedra
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Some results on the Tamari order:
I 1962, Tamari: order on formal bracketing
I 1972, Huang, Tamari: lattice structure
I 2007, Chapoton: number of intervals 2
n(n + 1)
4n + 1
n − 1
I 2013, Pournin: flip distance in the associahedra
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Some results on the Tamari order:
I 1962, Tamari: order on formal bracketing
I 1972, Huang, Tamari: lattice structure
I 2007, Chapoton: number of intervals 2
n(n + 1)
4n + 1
n − 1
I 2013, Pournin: flip distance in the associahedra
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Link with the weak order Canonical labelling
x
< x > x
5 1
3
2 4
3 1
2 7
5 8
4 6
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Binary search tree insertion
15324 →
4
2
1 3
5
Characterization: the permutations which give the same tree are its linear extensions.
15324, 31254, 35124, 51324, . . .
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Binary search tree insertion
15324 →
4 2
1 3
5
Characterization: the permutations which give the same tree are its linear extensions.
15324, 31254, 35124, 51324, . . .
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Binary search tree insertion
15324 →
4 2
1
3
5
Characterization: the permutations which give the same tree are its linear extensions.
15324, 31254, 35124, 51324, . . .
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Binary search tree insertion
15324 →
4 2
1
3 5
Characterization: the permutations which give the same tree are its linear extensions.
15324, 31254, 35124, 51324, . . .
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Binary search tree insertion
15324 →
4 2
1 3
5
Characterization: the permutations which give the same tree are its linear extensions.
15324, 31254, 35124, 51324, . . .
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Binary search tree insertion
15324 →
4 2
1 3
5
Characterization: the permutations which give the same tree are its linear extensions.
15324, 31254, 35124, 51324, . . .
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
1234
2134 1324
3124
1243
1423
4123
2314 2143
2413
4213
1342
3142
3412
3214 2341 1432
4132
4312
3241 2431
4231 3421
4321
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Rooted tree
Recursive definition:
I empty tree or
I a root with a list of subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Rooted tree
Recursive definition:
I empty tree or
I a root with a list of subtrees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Forest of rooted trees
An ordered list of rooted trees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Forest of rooted trees
An ordered list of rooted trees.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Flow on a forest
Forest of rooted trees with weight on nodes such that:
x x≥ −1
y x x+y
-1
-1
-1
1 1
1
3 3 4 4
-1
-1
2 2 1 0 3
3
-1
0 0
2 2 1
1
The exit rate of a forest is the sum of the exit rates of the trees. A closed flow is a forest with exit rate 0.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Flow on a forest
Forest of rooted trees with weight on nodes such that:
x x≥ −1
y x x+y
-1
-1
-1
1 1
1
3 3 4 4
-1
-1
2 2 1 0 3
3
-1
0 0
2 2 1
1
The exit rate of a forest is the sum of the exit rates of the trees. A closed flow is a forest with exit rate 0.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Flow on a forest
Forest of rooted trees with weight on nodes such that:
x x≥ −1
y x x+y
-1
-1
-1
1 1
1
3 3 4 4
-1
-1
2 2 1 0 3
3
-1
0 0
2 2 1
1
The exit rate of a forest is the sum of the exit rates of the trees. A closed flow is a forest with exit rate 0.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Flow on a forest
Forest of rooted trees with weight on nodes such that:
x x≥ −1
y x x+y
-1
-1
-1
1 1
1
3 3 4 4
-1
-1
2 2 1 0 3
3
-1
0 0
2 2 1
1
The exit rate of a forest is the sum of the exit rates of the trees. A closed flow is a forest with exit rate 0.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Flow on a forest
Forest of rooted trees with weight on nodes such that:
x x≥ −1
y x x+y
-1
-1
-1
1 1
1
3 3 4 4
-1
-1
2 2 1 0 3
3
-1
0 0
2 2 1
1
The exit rate of a forest is the sum of the exit rates of the trees. A closed flow is a forest with exit rate 0.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Flow on a forest
Forest of rooted trees with weight on nodes such that:
x x≥ −1
y x x+y
-1
-1
-1
1 1
1
3 3 4 4
-1
-1
2 2 1 0
3
3
-1
0 0
2 2
1
1
The exit rate of a forest is the sum of the exit rates of the trees.
A closed flow is a forest with exit rate 0.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Order on permutations Order on trees Link between these orders Flows of rooted trees
Flow on a forest
Forest of rooted trees with weight on nodes such that:
x x≥ −1
y x x+y
-1
-1
-1
1 1
1
3 3 4 4
-1
-1
2 2 1 0 3
3
-1
0 0
2 2 1
1
The exit rate of a forest is the sum of the exit rates of the trees.
A closed flow is a forest with exit rate 0.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
Theorem (Chapoton, C., Pons)
The number of closed flows of a given forest F is the number of elements smaller than or equal to a certain binary tree T (F ) in the Tamari order.
The proof is a bijection between all the closed flows on a rooted forest and Tamari intervals having the same maximal element.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
Theorem (Chapoton, C., Pons)
The number of closed flows of a given forest F is the number of elements smaller than or equal to a certain binary tree T (F ) in the Tamari order.
The proof is a bijection between all the closed flows on a rooted forest and Tamari intervals having the same maximal element.
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
4
2 5
1 3 9
7
6 8
Final forest F ≥ (T )
1 2
3
4 5
6 7 9
8
Initial forest F ≤ (T )
4
2 3
1
5 9
7 8
6
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
4
2 5
1 3 9
7
6 8
Final forest F ≥ (T )
1 2
3
4 5
6 7 9
8 Initial forest F ≤ (T )
4
2 3
1
5 9
7 8
6
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
4
2 5
1 3 9
7
6 8
Final forest F ≥ (T )
1 2
3
4 5
6 7 9
8
Initial forest F ≤ (T )
4
2 3
1
5 9
7 8
6
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
4
2 5
1 3 9
7
6 8
Final forest F ≥ (T )
1 2
3
4 5
6 7 9
8 Initial forest F ≤ (T )
4
2 3
1
5 9
7 8
6
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
4
2 5
1 3 9
7
6 8
Final forest F ≥ (T )
1 2
3
4 5
6 7 9
8 Initial forest F ≤ (T )
4
2 3
1
5 9
7 8
6
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
1234
2134 1324
3124
1243
1423
4123
2314 2143
2413
4213
1342
3142
3412
3214 2341 1432
4132
4312
3241 2431
4231 3421
4321
4 2
1 3
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
1234
2134 1324
3124
1243
1423
4123
2314 2143
2413
4213
1342
3142
3412
3214 2341 1432
4132
4312
3241 2431
4231 3421
4321
F ≤ (T )
1
2 3
4
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
1234
2134 1324
3124
1243
1423
4123
2314 2143
2413
4213
1342
3142
3412
3214 2341 1432
4132
4312
3241 2431
4231 3421
4321
F ≥ (T )
1 2
3 4
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
1234
2134 1324
3124
1243
1423
4123
2314 2143
2413
4213
1342
3142
3412
3214 2341 1432
4132
4312
3241 2431
4231 3421
4321
2
1 3
4
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
1234
2134 1324
3124
1243
1423
4123
2314 2143
2413
4213
1342
3142
3412
3214 2341 1432
4132
4312
3241 2431
4231 3421
4321
F ≤ (T 0 )
1
2 3 4
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
1234
2134 1324
3124
1243
1423
4123
2314 2143
2413
4213
1342
3142
3412
3214 2341 1432
4132
4312
3241 2431
4231 3421
4321
F ≥ (T )
1 2
3 4
F ≤ (T 0 )
1
2 3 4
Interval-poset [T , T 0 ]
1 2
3 4
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
Theorem (C., Pons)
The Tamari order intervals are in bijection with the posets with labels in 1, . . . , n of size n such that:
I If a < c and a C c then b C c for all a < b < c.
I If a < c and c C a then b C a for all a < b < c.
1 4
⇒
1 2 3
4
4 1
⇒
4 3 2
1
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
Theorem (C., Pons)
The Tamari order intervals are in bijection with the posets with labels in 1, . . . , n of size n such that:
I If a < c and a C c then b C c for all a < b < c.
I If a < c and c C a then b C a for all a < b < c.
1 4
⇒
1 2 3
4
4 1
⇒
4 3 2
1
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
Theorem (C., Pons)
The Tamari order intervals are in bijection with the posets with labels in 1, . . . , n of size n such that:
I If a < c and a C c then b C c for all a < b < c.
I If a < c and c C a then b C a for all a < b < c.
1 4
⇒
1 2 3
4
4 1
⇒
4 3 2
1
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
-1
-1
2 2 1 0 0
-1
0 0
1 1 0
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
-1
-1
2 2 1 0 0
-1
0 0
1 1 0
1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
-1
-1
2 2 1 0 0
-1
0 0
1 1
0 1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
-1
-1
2 2 1 0 0
-1
0 0
1 1
0 1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
-1
-1
2 2 1 0 0
-1
0 0
1 1
0 1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
-1
-1
2 2 1 0 0
-1
0 0
1 1
0 1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
-1
-1
2 2 1 0 0
0
0 0
0 0
0 1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
-1
0
1 1 1 0 0
0
0 0
0 0
0 1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
-1
1 1
1
0 0 1 1
0
0
0 0 0 0 0
0
0 0
0 0
0 1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
-1
0
0 0
1
0 0 1 1
0
0
0 0 0 0 0
0
0 0
0 0
0 1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
1
2
3 4
5 6
7
8
9
10 11
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
1
2
3 4
5 6
7
8
9
10 11
9
6 11
5 7 10
1 8
4 2
3 9
1 11
6 10
2 7
4 8
3 5
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
Introduction Bijection between Tamari intervals and flows
Main result Interval-posets Example of bijection
Thank you for your attention !
Gr´egory Chˆatel Bijection between Tamari intervals and flows on rooted trees
