PROGRESS ON THE 1/3 − 2/3 CONJECTURE
By
Emily Jean Olson

A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
Mathematics — Doctor of Philosophy
2017

ABSTRACT
PROGRESS ON THE 1/3 − 2/3 CONJECTURE
By
Emily Jean Olson
Let (P, ≤) be a finite partially ordered set, also called a poset, and let n denote the
cardinality of P . Fix a natural labeling on P so that the elements of P correspond to
[n] = {1, 2, . . . , n}. A linear extension is an order-preserving total order x1 ≺ x2 ≺ · · · ≺ xn
on the elements of P , and more compactly, we can view this as the permutation x1 x2 · · · xn
in one-line notation. For distinct elements x, y ∈ P , we define P(x ≺ y) to be the proportion
of linear extensions of P in which x comes before y. For 0 ≤ α ≤ 12 , we say (x, y) is an
α-balanced pair if α ≤ P(x ≺ y) ≤ 1 − α. The 1/3 − 2/3 Conjecture states that every finite
partially ordered set that is not a chain has a 1/3-balanced pair. This dissertation focuses
on showing the conjecture is true for certain types of partially ordered sets. We begin by
discussing a special case, namely when a partial order is 1/2-balanced. For example, this
happens when the poset has an automorphism with a cycle of length 2. We spend the
remainder of the text proving the conjecture is true for some lattices, including Boolean, set
partition, and subspace lattices; partial orders that arise from a Young diagram; and some
partial orders of dimension 2.

ACKNOWLEDGMENTS

I would first like to thank my advisor Dr. Bruce Sagan for opening the door to the mathematics community for me. He started by teaching me combinatorics and graph theory, and
then advised me as we explored new mathematics together.
I would also like to thank Dr. Jonathan Hall, Dr. Peter Magyar, and Dr. Michael Shapiro
for serving on my committee. I would additionally like to extend thanks to Dr. Robert Bell
for not only serving on my committee, but also for inviting me to be an REU mentor, an
experience I will use as I now begin to mentor students of my own.
Further, I offer thanks to the SMP community, a network of mathematicians who have
given me advice, encouragement, and comfort during my time as a graduate student.
Finally, I would like to thank Tim Olson for helping me optimize my code, without which
we would still be waiting for the posets of size 7 to run. I am also grateful for his perpetual
support, as he is holding the largest sign and cheering the loudest as I finish the last 0.2
miles of this marathon.

iii

TABLE OF CONTENTS

LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

v

Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Poset Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
3

Chapter 2 The 1/3 − 2/3 Conjecture .
2.1 History of the Conjecture . . . . . . .
2.2 Automorphisms of Posets . . . . . . .
2.3 Lattices . . . . . . . . . . . . . . . .
2.3.1 Boolean Lattices . . . . . . .
2.3.2 Set Partition Lattices . . . . .
2.3.3 Subspace Lattices . . . . . . .
2.3.4 Distributive Lattices . . . . .
2.3.5 Products of Two Chains . . .
2.4 Other Diagrams . . . . . . . . . . . .
2.5 Posets of Dimension 2 . . . . . . . .
2.6 Posets with Small Balance Constants
2.7 Future Work . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.

8
8
11
15
16
17
18
19
21
25
30
34
35

APPENDIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

iv

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

LIST OF FIGURES

Figure 1.1: A poset P with 6 elements and a matrix counting its linear extensions .

2

Figure 1.2: The poset T with three elements and one relation. . . . . . . . . . . . . .

3

Figure 1.3: A diagram of shape (4, 3, 1) and a standard Young tableau of the same
shape. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

Figure 2.1: Two posets with small balance constants.

. . . . . . . . . . . . . . . . .

9

Figure 2.2: The poset P has an automorphism with cycle length 2 and balance constant 1/2, while Q has no nontrivial automorphisms and balance constant
1/2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Figure 2.3: P and anti-automorphism σ with 1 fixed point. . . . . . . . . . . . . . .

15

Figure 2.4: The Boolean lattice B3 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

Figure 2.5: The set partition lattice Π3 . . . . . . . . . . . . . . . . . . . . . . . . .

18

Figure 2.6: A 4 element poset P , its corresponding J(P ), and a chart with values
e(P + xy). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

Figure 2.7: The poset C3 × C4 and its corresponding diagram. . . . . . . . . . . . .

22

Figure 2.8: The diagram of shape (4, 4, 2) where each cell is labeled by its hooklength. 23
Figure 2.9: (a) A Young diagram of shape (4, 22 , 1), (b) a shifted diagram of shape
(5, 3, 2, 1), (c) a skew left-justified diagram of shape (4, 22 , 1) / (2, 1), and
(d) a shifted skew diagram of shape (5, 3, 2, 1) / (3). . . . . . . . . . . . .

25

Figure 2.10: The shifted diagram of shape (4, 2, 1) and its corresponding poset. . . . .

26

Figure 2.11: The skew diagram (9, 72 , 54 ) / (6, 5, 32 , 2) . . . . . . . . . . . . . . . . .

28

Figure 2.12: Two skew left-justified diagrams and one skew shifted diagram. . . . . .

29

Figure 2.13: The set of linear extensions E(P, ω) of the poset (P, ω) forms the interval
[e, 41325] in the weak Bruhat order. . . . . . . . . . . . . . . . . . . . . .

32

Figure 2.14: Posets with the smallest balance constants greater than 1/3. . . . . . . .

34

v

Chapter 1
Introduction
We begin with some background before stating the conjecture. Section 1.1 provides a more
complete introduction to partially ordered sets, or posets. Let (P, ≤) be a partially ordered
set, and let n be the cardinality of P . Fix a natural labeling on P so that the elements of
P correspond to [n] = {1, 2, . . . , n}. A linear extension is a total order x1 ≺ x2 ≺ · · · ≺ xn
on the elements of P such that xi ≺ xj if xi <P xj ; more compactly, we can view this as
the permutation x1 x2 · · · xn in one-line notation. For distinct elements x, y ∈ P , we define
P(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For
0 ≤ α ≤ 21 , we say (x, y) is an α-balanced pair if

α ≤ P(x ≺ y) ≤ 1 − α,

and that P is α-balanced if it has some α-balanced pair. Notice that if (x, y) is α-balanced,
then (y, x) is α-balanced as well.
Conjecture 1.1 (The 1/3 − 2/3 Conjecture). Every finite partially ordered set that is not
a chain has a 1/3-balanced pair.
The conjecture was first proposed by Kislitsyn [Kis68] in 1968, although many resources
attribute the conjecture to having been formulated by Fredman [Fre76] in 1976 and later
independently by Linial [Lin84] in 1984.
1

5

6

4

3

1

2



0
6

0

0

0
0


9 15 15 15 15
0 15 12 15 15

0 0 6 12 15

3 9 0 15 13

0 3 0 0 8
0 0 2 7 0

Figure 1.1: A poset P with 6 elements and a matrix counting its linear extensions
We can see, for instance, that the conjecture holds for the poset P depicted in Figure 1.1.
This poset has 15 linear extensions, which are

{123456, 123465, 123645, 124356, 124365,
124536, 142356, 142365, 142536, 213456,
213465, 213645, 214356, 214365, 214536}.

If we want to find the 1/3-balanced pair(s) of P , we must examine the number of linear
extensions with x ≺ y for each incomparable x, y ∈ P . The matrix in Figure 1.1 has for
each entry (i, j) the number of linear extensions with i before j. For instance, P has 9 linear
extensions with 1 ≺ 2 and 6 with 2 ≺ 1, and so the entry (1, 2) in the matrix is 9 while the
(2, 1) entry is 6. Notice that if i < j in the poset, then the (i, j)th entry in the matrix is the
number of linear extensions of P . The bold entries have values that are between 1/3 and
2/3 of the total number of linear extensions, which gives us the 1/3-balanced pairs, namely
(1, 2), (2, 1), (3, 4), (4, 3), (5, 6), and (6, 5). We define the balance constant of P , denoted
δ(P ), to be
δ(P ) = max min{P(x ≺ y), P(y ≺ x)}
x,y∈P

For any poset P not a chain, it must be that 0 < δ(P ) ≤ 1/2. In the example in Figure 1.1,
7 ≈ 0.4667.
P has a balance constant of 15

2

T
Figure 1.2: The poset T with three elements and one relation.
So far, we have presented two equivalent ideas. That is, it is equivalent to say P has a
1/3-balanced pair and P has a balance constant δ(P ) ≥ 1/3. We will use these two phrases
interchangeably, as does the literature. In [BFT95], Conjecture 1.1 is described as “one of
the most intriguing problems in combinatorial theory”. If the conjecture is true, the bounds
are the best possible, as seen by the poset in Figure 1.2.

1.1

Poset Basics

This section will serve to set up notation and definitions relevant to partially ordered sets
later in this text. For a more complete background, see [Sta11].
Some standard notation we use for sets includes:
• N is the set of nonnegative integers.
• The set {1, 2, . . . , n} will be denoted by [n].
• Sn is the set of permutations on n elements.
• The symmetric difference of sets S and T is S∆T = (S ∪ T ) − (S ∩ T ).
Definition 1.2. A partially ordered set, or poset, is a set of elements P and binary operation
≤ that obey the following properties for all x, y, z ∈ P :
• x ≤ x (reflexivity),
3

• If x ≤ y and y ≤ x, then x = y (antisymmetry),
• If x ≤ y and y ≤ z, then x ≤ z (transitivity).
While this definition allows P to be an infinite set, we will assume here that all posets are
finite. Throughout the text, we will denote a poset by (P, ≤) or P if the binary relation is
clear from context. It may occasionally be useful to distinguish the binary operation between
posets, in which case we specify ≤ as ≤P . By x < y, we mean that x ≤ y and x = y. The
dual of P , denoted P ∗ , has the same elements as P and the partial order x ≤P ∗ y if y ≤P x.
For x, y ∈ P , we say x covers y, denoted x

y, if x < y and no element z ∈ P satisfies

x < z < y. The elements x and y are comparable if either x ≤ y or y ≤ x; otherwise, the pair
is incomparable. An element x ∈ P is minimal if for all y comparable to x, y ≥ x. Similarly,
z ∈ P is maximal if for all y comparable to z, y ≤ z. If a poset has only one minimal or
maximal element, we call it ˆ0 or ˆ1, respectively. For a poset with a ˆ0, the elements that
cover ˆ0 are called atoms. A poset is graded if it has a rank function r : P → N such that r
respects the partial order and for every x, y ∈ P with x

y, then r(y) = r(x) + 1.

We can create a graphical representation of posets by drawing its cover relations. The
Hasse diagram of a finite poset P is a graph whose vertices are elements of P and edges
are cover relations, such that whenever x

y, x is drawn below y. Figure 2.2 shows two

examples of Hasse diagrams of two different posets. A subset of elements S ⊆ P is called
a chain if for all u, v ∈ S, either u ≤ v or v ≤ u. The size of the largest chain in P is the
height of P . Similarly, a subset of elements such that any two elements are incomparable in
P is called an antichain and the size of the largest antichain of P is the width of P .
In later sections, we will refer back to the concept of order ideals as it will be useful in a
technique to show a poset is 1/3-balanced.

4

Definition 1.3. In a poset P , a lower order ideal is a subset I ⊂ P such that if x ∈ I and
y ≤ x, then y ∈ I. If there is some x ∈ P which is the unique maximal element of the lower
order ideal, we say the ideal is principal, and denote it Lx . We similarly define an upper
order ideal, and denote the principal upper order ideal generated by x by Ux .
Let P and Q be posets. A map φ : P → Q is order preserving if

x ≤P y

⇒

φ(x) ≤Q φ(y).

Similarly, a map σ : P → Q is order reversing if

x ≤P y

⇒

σ(y) ≤Q σ(x).

An isomorphism is an order-preserving bijection whose inverse is also order preserving. An
automorphism is an isomorphism from P to itself, and an anti-automorphism is an orderreversing bijection from P to itself. We say a poset P is a labeled poset if there is a bijection
ω : P → [n]. If we want to emphasize the labeling for P , we refer to the poset as (P, ω).
A labeling is natural if it is order preserving. We can fix a natural labeling on P so that
the elements of P correspond to [n] = {1, 2, . . . , n}. A linear extension is a total order
x1 ≺ x2 ≺ · · · ≺ xn on the elements of P such that xi ≺ xj if xi <P xj . We can
view a linear extension as a permutation x1 x2 · · · xn in one-line notation, which means the
permutation maps i to xi .
Let E(P ) be the set of linear extensions of P and e(P ) be the cardinality of E(P ). If
(P, ≤) is a poset and x, y ∈ P , let P + xy denote the poset (P, ≤ ), where ≤ is the transitive
closure of ≤ extended by the relation x < y. Therefore, E(P + xy) is the set of linear

5

8

6

5

7

4

3

2

1
Figure 1.3: A diagram of shape (4, 3, 1) and a standard Young tableau of the same shape.
extensions of P that have x before y and e(P + xy) is the size of E(P + xy). Notice that
e(P + xy) + e(P + yx) = e(P ).
We can build new posets by combining two or more posets. One way to do this is through
the linear sum. The linear sum of posets P and Q, denoted P + Q, is obtained by adding the
relations a < b for every a ∈ P and b ∈ Q. Another way to build a new poset is by taking
the product. The product of P and Q, denoted P × Q, is the set {(a, b) : a ∈ P, b ∈ Q} with
the partial order given by (a, b) ≤ (c, d) if a ≤P c and b ≤Q d.
We end with a discussion about integer partitions and Young diagrams, which we will see
again in Sections 2.3 and 2.4. An integer partition of n, or partition, is a weakly decreasing
sequence λ = (λ1 , . . . , λk ) that sums to n. In this case, we use the notation λ

n.

Definition 1.4. Let λ = (λ1 , . . . , λk ) be a partition of n. The Young diagram corresponding
to λ consists of k left-justified rows of cells where the ith row from the top has λi cells.
For an example of a Young diagram, see Figure 1.3. We will always let n be the number of
cells in a diagram, and since we often make no distinction between a partition and its Young
diagram, the same notation for both suffices. We can also abbreviate by using exponential
m
m
notation; we write λ = (λ1 1 , . . . , λk k ) when the first m1 rows of the diagram have length λ1 ,

etc. The cells of a Young diagram can be filled with integers from 1 to n using each number
exactly once and increasing in the rows and columns to form a standard Young tableau. An
example of this can be seen in Figure 1.3.
While we have covered some basic background information in this section, we later include
6

definitions relevant to particular sections. In Section 2.2, we see how automorphisms of posets
provide insight into Conjecture 1.1. In Section 2.3, we prove the conjecture for many types
of posets that are lattices, including rectangular Young diagrams. In Section 2.4, we consider
Young diagrams which are not lattices. In Section 2.5, we discuss permutations and how they
relate to posets of dimension 2. In Section 2.6, we discuss posets whose balance constants
are the smallest known values greater than 1/3.

7

Chapter 2
The 1/3 − 2/3 Conjecture

2.1

History of the Conjecture

Given the age of Conjecture 1.1, it should come as no surprise that many partial results
have been generated by many mathematicians. One of the first results appeared in 1984 by
Linial [Lin84], namely that the 1/3 − 2/3 Conjecture holds for posets of width 2.
Theorem 2.1 ([Lin84]). Let (P, ≤) be a poset of width exactly 2. Then, δ(P ) ≥ 1/3.
Aigner [Aig85] showed further that posets of width exactly 2 fit into one of two categories:
either the poset is a linear sum of copies of the singleton poset and T (the poset from
Figure 1.2); or the poset has an α-balanced pair with 1/3 < α < 2/3. In fact, the only
known posets that have a balance constant of 1/3 are the linear sums of singletons and
16 ≈ 0.3556, and until
T . The poset of width 2 in Figure 2.1 has a balance constant of 45

recently, it was the poset with the smallest balance constant greater than 1/3 [Bri99]. We
found posets of width 2 that have smaller balance constants, and we describe these results
in Section 2.6.
The smallest known balance constant for a poset with width strictly greater than 2 is
14
39

≈ 0.3590, as described in [Bri99]. It belongs to the poset with 7 elements in Figure 2.1.

We used a variation of the code in the Appendix to search all posets with up to 9 elements
and found no posets with balance constant smaller that 14
39 and width greater than 2.
8

Figure 2.1: Two posets with small balance constants.
There are many types of posets for which the conjecture has already been proven. This
includes posets of up to 11 elements [Pec06], posets with height 2 [TGF92], semiorders [Bri89],
posets with each element incomparable to at most 6 others [Pec08], N -free posets [Zag12],
and posets whose Hasse diagram is a tree [Zag16]. While the proof of the 1/3 bound for a
general poset remains elusive, in 1984 Kahn and Saks [KS84] proved that for any poset P ,
3 < P(x ≺ y) < 8 . In 1995, Brightwell, Felsner,
there is some pair x, y ∈ P such that 11
11

and Trotter [BFT95] improved the bound to be

√
5− 5
10

≤ P(x ≺ y) ≤

√
5+ 5
10 .

The interested

reader can refer to Brightwell’s 1999 survey [Bri99] on the conjecture for more information.
We now wish to recall a result of Zaguia which will be useful to us in the later sections.
The following definitions describe concepts introduced in [Zag16], although here we refer to
them with different names.
Definition 2.2. Let P be a poset and x and y be elements of P .
(a) We call the pair (x, y) twin elements if Lx = Ly and Ux = Uy .
(b) We call the pair (x, y) almost twin elements if the following two conditions hold in P or
in the dual of P :
(i) Lx = Ly , and
9

(ii) Ux \ Uy and Uy \ Ux are chains (possibly empty).
We will see that a poset with twin elements is 1/2-balanced in Section 2.2. In [Zag16],
Zaguia proves that a poset with an almost twin pair is 1/3-balanced. In fact, he proves
something stronger by generalizing the notion of an almost twin pair. He uses the term good
pair to describe these elements, but we will call them asymmetric.
Definition 2.3. Let P be a poset. A pair (x, y) of elements of P is asymmetric if the
following two conditions hold in P or in the dual of P :
(i) Lx ⊆ Ly and Uy \ Ux is a chain (possibly empty), and
(ii) P(x ≺ y) ≤ 21 .
Theorem 2.4 ([Zag16]). A finite poset that has an asymmetric pair of elements or an almost
twin pair of elements is 1/3-balanced.
In fact, every almost twin pair of elements is also asymmetric, and Zaguia’s proof focuses
on asymmetric pairs. Since we use almost twin elements later, we include them in Theorem 2.4 for emphasis. It is important to keep in mind that many of the known results for the
1/3 − 2/3 Conjecture are existence proofs and do not compute P(x ≺ y) exactly for any pair
(x, y) in the given poset. This is particularly true in the case of asymmetric pairs and almost
twin pairs of elements. In fact, one can find many examples of posets with asymmetric or
almost twin pairs of elements that do not coincide with any 1/3-balanced pairs of the poset.
We can make a few quick observations about the structure of a poset and how it relates
to the proportions of its linear extensions. A poset with a ˆ0 has P(ˆ0 ≺ x) = 1 for all x > ˆ0,
and so the proportion of linear extensions remains the same in P − {ˆ0}. For this reason, we
usually insist that posets have at least 2 minimal elements and similarly, at least 2 maximal
10

elements. Also, if we consider the linear sum P + Q of posets P and Q, we can easily see
that δ(P + Q) = max{δ(P ), δ(Q)}. For this reason, we need not consider posets that are
linear sums.

2.2

Automorphisms of Posets

We first provide a proof of an important observation about the linear extensions of a poset
with a nontrivial automorphism.
Proposition 2.5. A poset P with a nontrivial automorphism α has a nontrivial bijection
on its linear extensions. Further, P(x ≺ y) = P(α(x) ≺ α(y)) for all x, y ∈ P .
Proof. Let α : P → P be a nontrivial automorphism. This means that for x, y ∈ P , x ≤P y
if and only if α(x) ≤P α(y). Now, let π = a1 a2 · · · an be a linear extension of P , and
by the definition of linear extensions, we know that if ai ≤P aj , then i ≤ j. As α is an
automorphism, then we also have that if α(ai ) ≤P α(aj ), then i ≤ j. This gives us, by
definition, that α(π) = α(a1 )α(a2 ) · · · α(an ) is a linear extension of P . Therefore, α induces
a bijection on the linear extensions of P . Further, this bijection is nontrivial as α is nontrivial.
We can also observe that the linear extensions with x before y map bijectively via α to the
linear extensions with α(x) before α(y). Hence, P(x ≺ y) = P(α(x) ≺ α(y)), as desired.
In [GHP87], Ganter, Hafner, and Poguntke describe a proof of the fact that a poset with
a non-trivial automorphism will satisfy the 1/3 − 2/3 Conjecture. We present their short
argument here to illustrate a popular yet insightful approach to the conjecture using proof
by contradiction.

11

Theorem 2.6 ([GHP87]). If a poset P has a non-trivial automorphism, then P is 1/3balanced.
Proof. Let α : P → P be a nontrivial automorphism of a poset P . Assume there are no
x, y ∈ P with 1/3 ≤ P(x ≺ y) ≤ 2/3. We can then create a new relation

on P by defining

v if P(u ≺ v) > 2/3.

u

Observe that

is transitive. Indeed, for u, v, w ∈ P , assume u

v and v

w. This

means P(u ≺ v) > 2/3 and P(v ≺ w) > 2/3. We can see that since

P(u ≺ v ≺ w) + P(v ≺ u ≺ w) + P(v ≺ w ≺ u) = P(v ≺ w) > 2/3

and
P(v ≺ u ≺ w) + P(v ≺ w ≺ u) ≤ P(v ≺ u) < 1/3,
it must be that P(u ≺ v ≺ w) > 1/3. Therefore, P(u ≺ w) > 1/3, and since we assumed
there are no 1/3-balanced pairs in P , then P(u ≺ w) > 2/3. So, u

w, and hence

is a

transitive binary relation.
As

is transitive, it gives a linear order on P . Now, if u

v, then P (u ≺ v) > 2/3,

and so by Proposition 2.5, P (α(u) ≺ α(v)) > 2/3. This means that α(u)
α respects

. But as

α(v), and hence

is a linear order on P and α respects the linear order, it must be

that α is the identity. This contradicts our assumption.
Next, we present a result about when a poset has a balance constant of 1/2.
Proposition 2.7. If a poset P has an automorphism with a cycle of length 2, then P is
1/2-balanced. Further, if x and y are the elements in the cycle of length 2, then (x, y) is a
1/2-balanced pair.
12

5

4

3

2

6

5

4

3

2

1

1
Q

P

Figure 2.2: The poset P has an automorphism with cycle length 2 and balance
constant 1/2, while Q has no nontrivial automorphisms and balance constant 1/2.
Proof. Let α : P → P be an automorphism and x, y ∈ P be such that α(x) = y and
α(y) = x. Then we can see that

e(P + xy) = e(P + α(x)α(y)) = e(P + yx),

where the first equality comes from Proposition 2.5. So we have

e(P ) = e(P + xy) + e(P + yx)
= 2e(P + xy),

and so e(P + xy) = e(P )/2. Hence, (x, y) is a 1/2-balanced pair, as desired.
An example of a poset with an automorphism of cycle length 2 is given in Figure 2.2.
Poset P has a balance constant of 1/2. A counterexample to the converse of Proposition 2.7
is also provided in Figure 2.2. Poset Q has a balance constant of 1/2, as it has 12 linear
extensions and e(P + 34) = 6. However, we can see by inspection it has no nontrivial
automorphisms.
The following is a corollary to Proposition 2.7.

13

Corollary 2.8. A poset P with a twin pair of elements is 1/2-balanced.
Proof. Let P be a poset with x and y a twin pair of elements. We can see that P has a
non-trivial automorphism which fixes all elements except for x and y and maps x to y and
y to x. So, this poset has an automorphism is a cycle of length 2. By Proposition 2.7, then
P is 1/2-balanced and (x, y) is a 1/2-balanced pair.
While the above results depend on an automorphism of a poset, it is natural to ask if we
can obtain results from other types of maps. Next, we consider an anti-automorphism σ on
a poset. Observe that the linear extensions with x before y in P map bijectively via σ to the
linear extensions with σ(y) before σ(x). Hence, P(x ≺ y) = P(σ(y) ≺ σ(x)), as desired. Also
observe that any even number of iterations of σ give an automorphism of P . Hence, if σ 2 is
not the identity, then we know that P has a non-trivial automorphism, and by Theorem 2.6,
P is 1/3-balanced. We state this corollary to Theorem 2.6 here for completeness.
Corollary 2.9. If σ is an anti-automorphism on P and σ 2 is a non-trivial automorphism,
then P is 1/3-balanced.
We can also ask when an anti-automorphism guarantees a poset to be 1/2-balanced.
Once such case is described in Proposition 2.10.
Proposition 2.10. Let σ : P → P be an anti-automorphism. If σ has 2 fixed points, then
P is 1/2-balanced.
Proof. Let P be a poset and σ : P → P be an anti-automorphism with fixed points x and
y. Then, σ(x) = x and σ(y) = y. Since

P(x ≺ y) = P(σ(y) ≺ σ(x)) = P(y ≺ x),
14

9

8

7

6

5

4

3

2

1

σ

2

3

1

5

6

4

8

9

7

Figure 2.3: P and anti-automorphism σ with 1 fixed point.
and P(x ≺ y)+P(y ≺ x) = 1, we can see that P(x ≺ y) = 1/2. Hence, (x, y) is a 1/2-balanced
pair in P , and we are done.
We cannot weaken the assumption in Proposition 2.10, since a unique fixed point in
an anti-automorphism is not enough to guarantee that the poset is 1/2-balanced. For an
example, consider the poset P and anti-automorphism σ in Figure 2.3 where for x ∈ P
we place σ(x) on the right in the same position as x on the left. Any nontrivial antiautomorphism of P , including σ shown here, will have exactly 1 fixed point, and computer
711 = 1 .
calculations give us that δ(P ) = 1431
2

We can also see that the converse of Proposition 2.10 is not true, as evidenced by the
counterexample in Figure 2.2. Any anti-automorphism of the poset P will have exactly 1
fixed point, and yet it is 1/2-balanced.

2.3

Lattices

One commonly studied type of poset is a lattice. Here, we discuss the general definition of
a lattice before considering the conjecture for specific lattices in this section.
Definition 2.11. Let S ⊆ P be a nonempty set of elements. A lower bound of S is an
element z such that z ≤ u for all u ∈ S. The greatest lower bound, or meet, of S is a lower

15

bound w of S such that if z is another lower bound of S, then z ≤ w. If S = {x, y}, then
the meet, if it exists, is denoted by x ∧ y.
Similarly, an upper bound of S is an element z such that z ≥ u for all u ∈ S. The least
upper bound, or join, of S is an upper bound w of S such that if z is another upper bound
of S, then z ≥ w. If S = {x, y}, then the join, if it exists, is denoted by x ∨ y.
Note that in general, a set S ⊆ P could have zero, one, or many lower bounds or upper
bounds. However, if a meet or join exists, it must be unique. We call a poset a lattice if
every nonempty subset S ⊆ P has a meet and a join. One type of lattice we will consider
later is a distributive lattice.
Definition 2.12. A distributive lattice P is a lattice that obeys the following two equivalent
properties for all a, b, c ∈ P :

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) and a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c).

2.3.1

Boolean Lattices

Consider the set of all subsets of [n], and define an order by S ≤ T when S ⊆ T for
S, T ⊆ [n]. This is a lattice as it is closed under joins and meets, specifically, S ∨ T = S ∪ T
and S ∧ T = S ∩ T . We call this poset the Boolean lattice of size n, denoted Bn . This poset
has the empty set as its ˆ0 and [n] is its ˆ1. An example when n = 3 is given in Figure 2.4.
In the case that n = 1, the poset B1 is a chain, and so the 1/3 − 2/3 Conjecture only
applies to Bn when n ≥ 2. We present the following as a corollary to Proposition 2.7.
Corollary 2.13. For all n ≥ 2, the Boolean lattice Bn has an automorphism with a cycle
of length 2, and so the Boolean lattice is 1/2-balanced.
16

{1, 2, 3}

{1, 2}

{1, 3}

{2, 3}

{1}

{2}

{3}

∅
Figure 2.4: The Boolean lattice B3
Proof. Let n ≥ 2. We will first describe a map from Bn to itself that is a poset isomorphism.
For S ⊆ [n], consider φ : Bn → Bn defined by

φ(S) =





S∆{1, 2}, if S ∩ {1, 2} = {1} or S ∩ {1, 2} = {2}



S,

otherwise.

We can easily see that φ is a poset automorphism. Let A = {1} and B = {2} in Bn .
Then, φ(A) = B and φ(B) = A. Hence, by Proposition 2.7, Bn has a 1/2-balanced pair.

2.3.2

Set Partition Lattices

Consider the set Πn of all partitions of [n]. A partition is composed of pairwise disjoint,
non-empty subsets B1 , . . . , Bk whose union is [n], and we write B1 / · · · /Bk

[n]. Each Bi

is called a block of the partition. For π, τ ∈ Πn , we say π is a refinement of τ if every block
of π is contained in a block of τ . This produces a partial order on Πn given by π ≤ τ when π
is a refinement of τ . This is a lattice as it is closed under joins and meets, specifically π ∨ τ
is the minimal partition that refines both π and τ and π ∧ τ is the maximal partition that
is a refinement of both π and τ . Hence, Πn is called the set partition lattice. For brevity, we

17

123

1/23

2/13

3/12

1/2/3
Figure 2.5: The set partition lattice Π3
will write 12/3/4 for the set partition {{1, 2}, {3}, {4}} and similarly for other partitions.
An example of Π3 can be seen in Figure 2.5.
For n = 1, 2, Πn is a chain, and so the 1/3 − 2/3 Conjecture only applies to Πn when
n ≥ 3. We present the following as a corollary to Proposition 2.7.
Corollary 2.14. For n ≥ 3, the set partition lattice Πn has an automorphism with a cycle
of length 2, and so the set partition lattice is 1/2-balanced.
Proof. Let n > 2. We consider the map that sends a partition π to the partition π , where π
has the same blocks as π with the elements 1 and 2 interchanged. This is an automorphism
of the lattice. Indeed, it is a bijection because it is an involution and swapping 1 and 2
preserves ordering by refinement. To see that this automorphism has a 2-cycle, notice that
the lattice contains partitions π1 = 13/2/4/ · · · /n and π2 = 1/23/4/ · · · /n as n ≥ 3. Under
the automorphism described above, π1 and π2 form a 2-cycle. Hence, by Proposition 2.7,
the set partition lattice on n elements is 1/2-balanced when n ≥ 3.

2.3.3

Subspace Lattices

Let q = pm be some power of a prime p, and consider the finite vector space V = Fn
q , which
is the set of n-tuples of elements from the finite field Fq . The subspace lattice Ln (q) consists
of the set of all subspaces of Fn
q ordered by inclusion. We can see that for two subspaces
18

W, W ⊆ Fn
q , their meet W ∧ W is W ∩ W and their join W ∨ W is W + W . As Ln (q) is
closed under meets and joins, Ln (q) is a lattice. Further, we can note that Ln (q) is ranked
by the dimension of the subspace. If U ⊆ Fn
q is a subspace spanned by {v1 , . . . , vk }, then we
write U = v1 , . . . , vk . Let ei be the standard basis vector of Fn
q that has zeros everywhere
except for a 1 in the ith position. We present the following as a corollary to Proposition 2.7.
Corollary 2.15. For n ≥ 2, the subspace lattice Ln (q) has an automorphism with a cycle
of length 2, and so the subspace lattice is 1/2-balanced.
Proof. Let B = {e1 , . . . , en } be the standard basis of Ln (q). Since n ≥ 2, then there are
at least 2 distinct elements in B, and e1 and e2 are two 1-dimensional subspaces of Fn
q.
Consider the linear transformation on Fn
q defined by the n × n matrix M that has 1s in the
(1, 2), (2, 1), and (i, i), 3 ≤ i ≤ n, positions and zeros elsewhere. We can see that M sends
e1 to e2 , e2 to e1 , and fixes all other basis elements of Fn
q.
We can create an automorphism of Ln (q) as follows: for U ⊆ Fn
q , φ(U ) = M · U , where
M · U multiplies every element u ∈ U by M . Indeed, this is an automorphism of the lattice,
since if U ≤ U in Ln (q), then M · U ≤ M · U as well.
Since φ( e1 ) = e2 and φ( e2 ) = e2 , we have that e1 and e2 form a 2-cycle. By
Proposition 2.7, Ln (q) is 1/2-balanced.

2.3.4

Distributive Lattices

For a given poset P , consider the lower order ideals of P . Recall the definition of order
ideals is given in Definition 1.3. The lower order ideals are partially ordered by I ≤ I if
I ⊆ I . This gives us the distributive lattice J(P ) created from P . It is a lattice as meets
and joins are given by intersections and unions, respectively. An example of P and J(P ) is
19

{1, 2, 3, 4}
{2, 3, 4}

{1, 2, 3}

4
3

1

{2, 3}

{1, 2}

2
P

{2}
J(P )

y

{2} {2, 3} {2, 3, 4}
{1} 5
10
13
4
10
{1, 2}
5
{1, 2, 3}
x

{1}
∅

Figure 2.6: A 4 element poset P , its corresponding J(P ), and a chart with values e(P + xy).
given in Figure 2.6. In fact, by the Fundamental Theorem on Distributive Lattices, every
distributive lattice is isomorphic to the lattice of lower order ideals of some poset P . As a
result, we were motivated to find results about J(P ) that depend on properties of P .
Unfortunately, it is not true that if P is 1/2-balanced, then J(P ) is 1/2-balanced as well.
An example can be seen in Figure 2.6. While P is 1/2-balanced by the pair (1, 3), J(P ) is
not 1/2-balanced, as evidenced in the chart in Figure 2.6 whose entries are e(P + xy) for
every x and y not comparable in J(P ). Since J(P ) has 14 linear extensions, we can see no
pair is 1/2−balanced.
Adding an extra condition, namely that P has an automorphism with a 2-cycle, allows
us to prove that J(P ) is 1/2-balanced.
Proposition 2.16. If P has an automorphism with cycle of length 2, then J(P ) is 1/2balanced.
Proof. Let α : P → P be an automorphism with α(x) = y and α(y) = x for some x, y ∈ P .
This induces an automorphism α
¯ of J(P ), given by α
¯ (I) = {α(w) : w ∈ I} for I ∈ J(P ).
We claim that α
¯ has a cycle of length 2, namely that α
¯ (Lx ) = Ly and α
¯ (Ly ) = Lx .
We will show α
¯ (Lx ) = Ly , as the proof of the other equality is similar. Let z ∈ α
¯ (Lx ),
20

so z = α(w) for some w ∈ Lx . This means that w ≤ x, and so α(w) ≤ α(x) = y. Therefore,
z ≤ y and we have z ∈ Ly . Hence, α
¯ (Lx ) ⊆ Ly . The proof of the other set containment is
similar. Thus, we have proven the claim. Since α
¯ has a cycle of length 2, by Proposition 2.7,
J(P ) is 1/2-balanced.
This leads to another proof that Boolean lattices are 1/2-balanced.
Corollary 2.17. For n ≥ 2, the Boolean lattice Bn is 1/2-balanced.
Proof. Let n ≥ 2. The Boolean lattice Bn is the distributive lattice corresponding to the
poset P with n elements and no relations. There is an automorphism on P that swaps
elements 1 and 2 and is the identity on the remaining elements. Since P has an automorphism
with a cycle of length 2, then by Proposition 2.16, Bn is 1/2-balanced.

2.3.5

Products of Two Chains

Let Cn be the chain with n elements. This section will be concerned with the product of
two chains Cm and Cn , with m, n ≥ 2. The poset Cm × Cn is a lattice with grid structure,
as in Figure 2.7. Recall Young diagrams from Definition 1.4 and notation from Section 1.1.
Figure 2.7 depicts the rectangular Young diagram of shape λ = (43 ) corresponding to C3 ×C4 .
We can see the correspondence as m gives us the number of rows of the Young diagram,
while n gives us the length of each row. The number of linear extensions of Cm × Cn is
the same as the number of standard Young tableaux (SYT) of the Young diagram of shape
(nm ).
Unlike many other demonstrations that a poset is 1/3-balanced, our proof for Cm × Cn
finds the exact value of P(a ≺ b) for a pair of elements (a, b). Let a be the atom from the
chain Cm × ˆ0 and b the atom from the chain ˆ0 × Cn , as labeled in Figure 2.7. In order to
21

a
b
b

a

Figure 2.7: The poset C3 × C4 and its corresponding diagram.
compute how many linear extensions of Cm × Cn have a ≺ b, we will compute how many
SYT have (1, 2) filled with a smaller number than (2, 1). Since the entry 2 must go in one
of these two cells, this assumption forces the SYT to have the (1, 1) cell filled with a 1 and
the (1, 2) cell filled with a 2. Flipping and rotating by 180 degrees, one sees that this is
equivalent to counting the SYT of shape (nm−1 , n − 2).
To prove Lemma 2.18, we will need the hooklength formula for f λ , the number of SYT
of a diagram of shape λ. For a given cell (i, j) in a diagram of shape λ, its hook is the set
of all the cells weakly to its right together with all cells weakly below it, and its hooklength
hλ (i, j) is the number of cells in its hook. The hooklength formula for a diagram with n cells
is
fλ =

n!
,
hλ (i, j)

where the product is over all cells (i, j) in λ. A diagram of shape (4, 4, 2) is given in Figure 2.8,
and each cell is labeled by its hooklength. Using the formula, we can see that

f (4,4,2) =

6 · 52

10!
= 252,
· 4 · 3 · 23 · 12

and so the diagram has 252 SYT.
Lemma 2.18. Let m ≥ 1 and n ≥ 3. We can relate the number of standard Young tableaux
22

6

5

3

2

5

4

2

1

2

1

Figure 2.8: The diagram of shape (4, 4, 2) where each cell is labeled by its hooklength.
of shape (nm ) and of shape (nm−1 , n − 2) by the following equality:

f (n

m−1 ,n−2)

=

(n − 1)(m + 1) (nm )
f
.
2(mn − 1)

Proof. Let λ = (nm ) and µ = (nm−1 , n − 2) be diagrams and f λ be the number of SYT
of shape λ. We will proceed by first describing which factors differ between f λ and f µ .
We can observe that the hooklengths only disagree between λ and µ in those cells in the
last two columns and those in the last row. The last two columns of λ have hooklengths
of m + 1, m, . . . , 2 and m, m − 1, . . . , 1, while in µ the last two columns have hooklengths
m, m − 1, . . . , 2 and m − 1, m − 2, . . . , 1. Overall, f µ is missing a factor of (m + 1)m which
appears in the denominator of f λ . Similarly, the hooklength values of the last row of λ,
excluding the ones in the last two columns which have already been accounted for, are
n, n − 1, . . . , 3, while those in µ are n − 2, n − 3, . . . , 1. So our formula for f µ is missing
a factor of n(n − 1) from the denominator and a factor of 2 from the numerator. Finally
f λ has a numerator of (mn)! while µ has a numerator of (mn − 2)!, so there is a factor of
(mn)(mn−1) we need to remove from the numerator of f λ . Overall, our hooklength formula
for µ derived from f λ is

fµ

=

n(n − 1)(m + 1)m λ
f
2(mn)(mn − 1)

as desired.
23

=

(n − 1)(m + 1) λ
f ,
2(mn − 1)

Theorem 2.19. Let Cm and Cn be chains of lengths m ≥ 2 and n ≥ 2, respectively. Then
their product Cm × Cn has a 1/3-balanced pair.
Proof. Without loss of generality, we can let n ≥ m. Let P = Cm × Cn . If m = 2, then P
has width 2, and so by Theorem 2.1, we know that δ(P ) ≥ 1/3. If m = n = 3, then P has a
non-trivial automorphism, and so by Theorem 2.6, P has a 1/3-balanced pair.
Next, let m ≥ 3 and n ≥ 4. We can see that P has exactly two atoms. Let the atoms
be labeled a and b, as in Figure 2.7. We claim that a, b are a 1/3-balanced pair. Notice that
the linear extensions of P begin with either ˆ0a . . . or ˆ0b . . ., and the number that begin with
ˆ0a . . . is the same as e(P + ab). We can also see that e(P + ab) is the same as the number
of standard Young tableaux of shape (nm−1 , n − 2). Hence, by Lemma 2.18, we know that

e(P + ab) =

(n − 1)(m + 1)
e(P ).
2(mn − 1)

It remains to be shown that
1
(n − 1)(m + 1)
2
≤
≤
3
2(mn − 1)
3

(2.1)

for all m ≥ 3, n ≥ 4. For the first inequality, cross multiply and bring everything to one
side to get the equivalent inequality (mn − 1) + 3(n − m) ≥ 0. This inequality is true since
n ≥ m and mn ≥ 1.
For the second inequality, proceed in the same manner to get mn + 3(m − n) − 1 ≥
0. By the lower bounds for m, n we have (m − 3)(n − 4) ≥ 0. So it suffices to prove
mn + 3m − 3n − 1 ≥ (m − 3)(n − 4). Moving everything to one side yet again gives the
equivalent inequality 7m − 13 ≥ 0 which is true since m ≥ 3.
Therefore, we have shown that (2.1) holds, and so (a, b) is a 1/3-balanced pair in P .

24

(a)

(b)

(c)

(d)

Figure 2.9: (a) A Young diagram of shape (4, 22 , 1), (b) a shifted diagram of shape
(5, 3, 2, 1), (c) a skew left-justified diagram of shape (4, 22 , 1) / (2, 1),
and (d) a shifted skew diagram of shape (5, 3, 2, 1) / (3).

2.4

Other Diagrams

In Section 2.3.5, we considered the product of two chains as a rectangular Young diagram,
and the linear extensions of the poset corresponded to the standard Young tableaux of that
Young diagram. Given Theorem 2.19, it is natural to consider other posets that come from
other diagrams. Recall the definition of Young diagram given in Definition 1.4, and let
λ = (λ1 , . . . , λk ) be a weakly decreasing partition of n. An example of the Young diagram
of shape (4, 22 , 1) is given in Figure 2.9(a). To generalize the notion of Young diagram, next
let λ1 > λ2 > · · · > λk , in which case λ is called a strict partition. The shifted diagram
corresponding to a strict partition λ indents row i so that it begins on the diagonal cell (i, i).
An example is given in Figure 2.9(b). A third type of diagram is a skew diagram, λ/µ, which
is the set-theoretic difference between diagrams λ = (λ1 , . . . , λk ) and µ = (µ1 , . . . , µl ) such
that µ ⊆ λ, that is, l ≤ k and µi ≤ λi for each 1 ≤ i ≤ l. A skew diagram can be either
left-justified, as seen in Figure 2.9(c), or shifted, as seen in Figure 2.9(d).
We would like to point out that if we allow µ to be an empty partition, then λ/µ could
refer to a Young, shifted, or skew diagram. To avoid ambiguity, we will always specify the
type of diagram we intend, and to be clear, when referring to Young diagrams, we exclusively
mean left-justified and non-skew diagrams.

25

g
a

b

c

f

d

d

e f

c

g

e
b
a

Figure 2.10: The shifted diagram of shape (4, 2, 1) and its corresponding poset.
For each diagram, there is a corresponding poset formed by letting each cell be an element
of P . For x, y ∈ P , x ≤ y exactly when the cell for y is weakly to the right and/or weakly
below the cell for x. See Figure 2.10 for an example of the poset corresponding to the shifted
diagram (4, 2, 1). We will use the notation λ/µ to refer to a diagram and Pλ/µ for the
corresponding poset.
As we have already seen, the cells of a Young diagram can be filled with integers from
1 to n using each number exactly once and increasing in the rows and columns to form a
standard Young tableau. In a similar manner, we define shifted standard Young tableaux
and skew standard Young tableaux. The standard (shifted) (skew) Young tableaux for a
given diagram are in bijective correspondence with linear extensions of the poset. Therefore,
when we want to discuss linear extensions, we can discuss standard (shifted) (skew) Young
tableaux instead.
We next present a generalized version of Theorem 2.19. For any type of diagram, we use
the notation (i, j) to refer to the cell in the ith row and jth column. For instance, the (2, 2)
cell in the shifted diagram in Figure 2.10 is labeled with an e.
Theorem 2.20. Let Pλ/µ be the poset corresponding to the diagram λ/µ, where µ could
be an empty partition, and assume Pλ/µ is not a linear order. If λ/µ is a Young diagram,
shifted diagram, or skew diagram, Pλ/µ is a 1/3-balanced poset.

26

Proof. Let λ = (λ1 , . . . , λk ) and µ = (µ1 , . . . , µl ) be partitions such that µ ⊆ λ. Assume the
diagram λ/µ does not correspond to a linear order. Assume first that µ is empty; we will
show that when Pλ corresponds to a Young diagram or shifted non-skew diagram, it has an
almost twin pair of elements. Hence, by Theorem 2.4, Pλ is 1/3-balanced.
When λ is a Young diagram, let x correspond to the (1, 2) cell and y correspond to the
(2, 1) cell of λ. So, (x, y) is an almost twin pair of elements in Pλ .
When λ is a shifted diagram which is not skew, then λ1 ≥ 3, as Pλ is not a linear order.
Let x correspond to the (1, 3) cell and y correspond to the (2, 2) cell. So, (x, y) is an almost
twin pair of elements in Pλ .
Next, we consider skew diagrams. If λ/µ is a disconnected diagram, observe that an
almost twin pair in a connected component of Pλ/µ remains an almost twin pair in the entire
poset. Therefore, we can assume λ/µ is a connected skew diagram that does not correspond
to a poset that is a chain. First consider left-justified skew diagrams. By removing any
empty columns on the left of the diagram, we can assume without loss of generality that
k ≥ l + 1. For ease in discussing the first and last rows of µ, define µ0 = λ1 and µl+1 = 0.
We have the following cases:
(i) If there exists i ∈ [l] such that

µi−1 − 1 ≥ µi = µi+1 + 1

then (i, µi + 1) and (i + 1, µi+1 + 1) is an almost twin pair. For an example of this case,
see the pair (a, b) in Figure 2.11.

27

a
b
c
d
e
f
Figure 2.11: The skew diagram (9, 72 , 54 ) / (6, 5, 32 , 2)
(ii) If there exists i ∈ [l − 1] such that

µi−1 − 2 ≥ µi = µi+1

then (i, µi + 2) and (i + 1, µi+1 + 1) is an almost twin pair. Note that (i, µi + 2) exists
in the diagram since λ/µ is connected. For an example of this, see the pair (c, d) in
Figure 2.11.
(iii) If k = l + 1 and µl−1 − 1 ≥ µl , then (l, µl + 1) and (l + 1, 1) are an almost twin pair.
For an example of this, see the pair (e, f ) in Figure 2.11.
(iv) If k ≥ l + 2 and µl ≥ 2, then (l + 1, 2) and (l + 2, 1) are an almost twin pair. Notice
this is similar to case (ii), only it occurs at the bottom of the skew diagram.
We can now decide what types of diagrams do not fall into cases (i)-(iv) above. We claim
that any remaining diagram has µ of the form

(sm1 , (s − 1)m2 , . . . , (s − p + 1)mp )

where mi ≥ 2 for all i ∈ [p] and s ∈ N\{0}. We call this case (v).
28

a
b

c
d

e
f

(8, 6, 5, 3, 2) / (6, 3)
(53 , 43 , 3) / (42 , 32 , 22 )

(34 , 22 , 1) / (22 , 13 )

Figure 2.12: Two skew left-justified diagrams and one skew shifted diagram.
Indeed, all consecutive µi values differ by 1 or 0 since if there is some r with µr−1 −2 ≥ µr ,
then to avoid cases (i) and (ii) above, it must be that µs−1 − 2 ≥ µs for all s ∈ [r, l + 1].
In particular, this means µl ≥ 2, and this diagram will fall into case (iii) or (iv). So, any
consecutive µi values differ by 1 or 0. Further, if mi = 1 for any i ∈ [p], the diagram would
fall into case (i). Hence, µ must have the form above.
It also must be true that λ/µ has λ1 = µ1 + 1, in order to avoid case (ii) above. Two
examples of diagrams λ/µ that do not fall into cases (i)-(iv) are given in Figure 2.12. In these
remaining diagrams, (1, µ1 + 1) and (m1 + 1, µ(m +1) + 1) is an almost twin pair. Examples
1
of this pair are (a, b) and (c, d) in Figure 2.12. Hence every skew left-justified diagram λ/µ
satisfies one of these five cases, and so Pλ/µ not a chain has an almost twin pair.
Finally, we consider the skew shifted diagrams. Notice that that the first l rows of the
diagram can be viewed as a skew left-justified diagram. Therefore, if any of the first l − 1
rows are of the forms found in cases (i) or (ii), or if the first rows correspond to case (v),
then the almost twin pairs in those cases remain almost twin in this poset, and we are done.
If none of cases (i), (ii), or (v) apply, then consider µl . In particular, it must be the
µl > 1, else case (ii) or (v) applies. If µl > 3, then the last k − l rows of the diagram

29

are a shifted diagram, and so we have the same almost twin pair as in the shifted case. If
µl ∈ {2, 3}, then (l, µl + l) and (l + 1, l + 1) are an almost twin pair, as seen by the pair
(e, f ) in Figure 2.12. Hence, for skew diagrams λ/µ, if Pλ/µ is not a chain, it has an almost
twin pair of elements, as claimed.

2.5

Posets of Dimension 2

The set of linear extensions E(P ) of a labeled poset P with n elements can be considered
a subset of Sn , where permutations are written in one-line notation. The full set Sn is
a poset under the weak Bruhat ordering. For background on the weak Bruhat order, see
[BB05, Chapter 3]. Since we use natural numbers to discuss the elements of a labeled poset
P , we will use <N and <P to distinguish between the linear order on the natural numbers
and the partial order on P . The following definitions for permutations are relevant to this
section and are thus provided here:
Definition 2.21. Let π = π1 π2 . . . πn be a permutation in one-line notation. An inversion
in π is a pair (i, j) such that i < j and πi > πj .
Definition 2.22. For π and σ permutations, π is said to contain σ as a pattern if some
subsequence of π has the same relative order as σ. Otherwise we say that π avoids σ. We
can also consider a subsequence S = πi1 πi2 · · · πim of elements from π = π1 · · · πn . We say
that S is contained in the pattern σ if some instance of σ in π contains S. Otherwise, we
say that S avoids σ.
An example of Definition 2.22 can be seen with π = 23154. We can see that π contains
the pattern 123 in the subsequence 235, while it avoids 321. If S = 14, then S is contained
in the pattern 132 in the instance 154 and avoids 123.
30

For the remainder of this section, we will consider E(P ) for any poset P to be a subposet
of Sn . We might ask what can be said about E(P ) as a poset, and Bj¨orner and Wachs
[BW91] showed that E(P ) has especially nice structure when P has dimension 2.
The dimension of a poset is the least k such that there is some U ⊆ E(P ) of size k such
that ∩U = (P, ≤). An equivalent definition is that the dimension of P is the least k such
that P can be embedded as a subset into the product Nk . For our purposes, we discuss
posets with dimension 2, which Bj¨orner and Wachs [BW91] characterize in the following
proposition.
Proposition 2.23 ([BW91]). A poset P has dimension 2 if and only if it has a labeling ω
such that E(P, ω) forms an interval in the weak Bruhat ordering of Sn .
If the labeling ω for a poset P of dimension 2 is natural, then E(P, ω) forms a lower
order interval. Since the characterization by Bj¨orner and Wachs is necessary and sufficient,
we know there is a correspondence between naturally labeled posets and lower-order intervals
in Sn . The interval contains permutations between the identity permutation e and some
maximal permutation π. When E(P, ω) forms the interval [e, π], the two linear extensions
required to describe P as a poset of dimension 2 are exactly e and π. For the reverse
correspondence, we can start with a permutation π and create the naturally labeled poset
(Pπ , ω) with the property that E(Pπ , ω) is the set of permutations in the interval [e, π]. Here,
the subscript emphasizes that Pπ was created from π. To create Pπ , add labeled elements
by reading π left to right. A relation is added between two elements a and b exactly when
a is to the left of b in π and a <N b.
As a brief example, consider the poset P and labeling ω in Figure 2.13. This poset has 8
linear extensions, and using the weak Bruhat order, we can create the poset E(P, ω), which

31

41325

5

4

3

2

1

14325

41235

13425

14235

13245

12435

(P, ω)
e = 12345
E(P, ω)
Figure 2.13: The set of linear extensions E(P, ω) of the poset (P, ω)
forms the interval [e, 41325] in the weak Bruhat order.
is a subposet of S5 . For the reverse correspondence, we construct (Pπ , ω) from the maximal
element of the interval [e, 41325] as follows: Add labeled elements by reading π left to right,
so first add 4, then 1, etc. Add the relations 1 <P 3, 1 <P 2, and finally add 5 as a maximal
element. Notice that 1 and 4 are minimal elements as no values to the left of 1 or 4 in 41325
are smaller than them. By this process, we can see that for every inversion (i, j) of π gives
us a pair of elements in Pπ that are not comparable.
Our goal is to use properties of the maximal permutation in E(P, ω), where P has dimension 2, to determine if the poset has a 1/3-balanced pair. Our result, in fact, deals with
a case when the poset has a 1/2-balanced pair.
Proposition 2.24. Let π = π1 π2 . . . πn be an element of Sn , and assume that π has an
inversion (i, j) such that πi πj avoid the patterns 312 and 231 in π. Then (πi , πj ) is a 1/2balanced pair of Pπ .
Before we proceed to the proof, we can observe an example of this in Figure 2.13. We
can see (3, 4) is inversion of π = 41325, and π3 π4 = 32 avoids 312 and 231 in π. So,
32

(π3 , π4 ) = (3, 2) is a 1/2-balanced pair in P .
Proof. Let π ∈ Sn , and assume π has an inversion (i, j). Let πi = y and πj = x, and further
assume yx avoids the patterns 312 and 231. Therefore, π has the form

π = π 1 · · · y · · · x · · · πn

where y >N x. Now, since yx avoids 312 and 231, there are no elements between x and y in
π that are larger than y or smaller than x. Also, no elements to the right of x or left of y
have values between x and y. To put this description another way, if yx avoids 312 and 231
in π, the elements between y and x in π are exactly those in the set {a | x <N a <N y}.
We claim that Ux = Uy and Lx = Ly in Pπ . We will show that Ux = Uy as the proof
of Lx = Ly is nearly identical. If z ∈ Ux , then z is to the right of x in π and thus also to
the right of y in π. Since yx avoids 312 in π and x <N z, it must be that y <N z. Hence,
y <P z and so z ∈ Uy .
If z ∈ Uy , then z is to the right of y in π and y <N z. Since yx avoids 231 in π, then z
must also be to the right of x in π. Also, x <N y <N z. Thus x <P z, which means z ∈ Ux .
Hence, we have that Ux = Uy .
Now, because Ux = Uy and Lx = Ly , (x, y) is a twin pair of elements. By Corollary 2.8,
as Pπ has a twin pair, then Pπ is 1/2-balanced, as desired.
It is important to note that not every permutation has an inversion that satisfies the
conditions of Proposition 2.24. This means we have not shown the 1/3 − 2/3 Conjecture for
every poset of dimension 2; however, we hope that other helpful properties of permutations
will emerge to show every dimension 2 poset satisfies the conjecture.

33

A

C
B

Figure 2.14: Posets with the smallest balance constants greater than 1/3.

2.6

Posets with Small Balance Constants

As previously mentioned, Aigner [Aig85] proved that a poset of width 2 has a balance
constant of 1/3 if and only if it is the linear sum of the singleton poset and T from Figure 1.2.
One can then ask: how close to 1/3 can a balance constant be for a poset not of this form?
The posets with the previous closest values can be found in Figure 2.1.
We have found posets of width 2 that have balance constants closest known values to
6 ≈ 0.35294. Poset B has δ(B) = 60 ≈ 0.350877.
1/3. In Figure 2.14, poset A has δ(A) = 17
171
37 ≈ 0.349057.
Poset C has δ(C) = 106

This analysis was done through the code found in the Appendix , which can be adapted
to find the balance constants of many posets at a time.

34

2.7

Future Work

In Section 2.3.4, we discussed one special case when a distributive lattice is 1/2-balanced.
Future work on the conjecture could include showing that all distributive lattices are 1/3balanced.
In Section 2.3.5, we discussed the product of two chains. We were motivated to study
products of chains as they are isomorphic to divisor lattices. A divisor lattice is the set of
divisors of n partially ordered by x ≤ y if x divides y. It is a lattice as the meet of two
elements is their greatest common divisor and the join of two elements is their least common
multiple. One future direction this work could take is to prove that a product of k chains is
1/3-balanced, for k ≥ 3.
In Section 2.6, we discussed finding posets of width 2 with small balance constants.
Future work in this direction could continue to search for posets with balance constants
approaching 1/3, and it would be ideal to find a pattern among these posets.

35

APPENDIX

36

Appendix
Code to Count P(x ≺ y)
In this section, we include a simplified version of the code we developed in the Python
programming language [Ros95] to calculate the proportions of linear extensions for a given
poset. The input is a representation of the poset as an upper-triangular binary matrix M ,
and the output is the total number of linear extensions and a matrix L whose (i, j)th entry
is the number of linear extensions in which i ≺ j.
We originally implemented the algorithm in Sage, but when we attempted to compute the
linear extensions for all posets of size 7, it became necessary to incorporate modules found
in Python, such as numpy, abbreviated as np in the code, for faster matrix computations.

Matrix Representations
In order to obtain an upper-triangular binary matrix for a poset P , first give the poset a
natural labeling, which ensures the desired matrix M is upper-triangular. The entries of M
are Mij = 1 if and only if i <P j, and zeros elsewhere. As as example, consider the poset
and natural labeling in Figure 1.1. The following is a matrix representation of this poset.

0
0

0

0

0
0

0
0
0
0
0
0

1
1
0
0
0
0

1
0
0
0
0
0

37

1
1
0
1
0
0


1
1

1

0

0
0

(A.1)

Finding the Linear Extensions
Given a matrix M , we recursively construct the set of permutations that are linear extensions
of the given poset in the function linear extensions(M). The function operates by starting
with the identity permutation and considers if the largest value k can be moved one position
to the left. If it can, it calculates all the permutations recursively with k in that position
before considering if k can again be moved to the left. We can see that Mkk = 0 for all
k ∈ [n], and so in the kth iteration of the recursion, we can always append k to the end of
the permutation in consideration.
1 def l i n e a r e x t e n s i o n s (M, k=None ) :
i f k i s None :
3
k = len (M) − 1
5
7
9
11
13
15
17
19

if k < 0:
yield [ ]
else :
# Recursively generate permutations with fewer elements
# and i n s e r t k a t a l l a l l o w e d p o s i t i o n s i n each
f o r p in l i n e a r e x t e n s i o n s (M, k − 1 ) :
yield p + [k]
# Attempt t o i n s e r t k as we move l e f t t h r o u g h p
f o r i in reversed ( xrange ( k ) ) :
i f not M[ p [ i ] ] [ k ] :
# I f a l l o w e d , i n s e r t and c o n t i n u e
yield p [ : i ] + [ k] + p[ i : ]
else :
# All smaller i insertions forbidden
break

Counting the Proportions
Now that we have all the linear extensions of P , we need a way to keep track of how many
times i ≺ j for all i, j ∈ P . We do this through a matrix L whose entries are the number of
linear extensions of P with i ≺ j.
38

The function count extensions(M) loops over the linear extensions found by
linear extensions(M) and computes the matrix L. It returns not only the matrix, but
also the maximum value of L, which is the total number of linear extensions of P . To compute L, we use the inverse h of each linear extension p, since we want to count when the
values i and j satisfy i ≺ j, not when the positions i and j satisfy i ≺ j.
To do the count, the function creates a matrix h as matrix, whose ith row is n copies of
the ith element of h. We compare this to the transpose of h as matrix, whose jth column
is n copies of the jth element of h. When we compare the (i, j)th elements of these matrices,
we obtain a 1 if hi < hj and 0 otherwise. The matrix L increments any position which
obtains a 1 in the comparison.
def c o u n t e x t e n s i o n s (M) :
n = len (M)
rng = np . a r a n g e ( n , dtype=np . i n t )
4
h = np . z e r o s ( n , dtype=np . i n t )
2

6

# P r e a l l o c a t e indexing matrix
Lind = np . a r r a y ( [ range ( n ) ] ∗ n ) . T

8
10

# Use 64 b i t i n t e g e r s f o r c o u n t i n g t o a v o i d o v e r f l o w
# ( as we l e a r n e d t h e hard way )
L = np . z e r o s ( ( n , n ) , dtype=np . i n t 6 4 )

12
14

f o r p in l i n e a r e x t e n s i o n s (M) :
# Compute h , t h e i n v e r s e o f p
h [ p ] = rng

16
18
20

# Copy h i n t o t h e columns o f a m a t r i x
h a s m a t r i x = h [ Lind ]
# Increment L by d o i n g a comparison f o r each e n t r y
L += ( h a s m a t r i x < h a s m a t r i x . T)

22
return L .max( ) , L

As an example, by inputting the matrix in (A.1) for the poset found in Figure 1.1, we
obtain the matrix from Figure 1.1. The bold values in the matrix were added for emphasis.

39

BIBLIOGRAPHY

40

BIBLIOGRAPHY

[Aig85] Martin Aigner. A note on merging. Order, 2(3):257–264, 1985.
[BB05] A. Bj¨orner and F. Brenti. Combinatorics of Coxeter Groups. Graduate Texts in
Mathematics. Springer Berlin Heidelberg, 2005.
[BFT95] Graham Brightwell, S. Felsner, and W. T. Trotter. Balancing pairs and the cross
product conjecture. Order, 12(4):327–349, 1995.
[Bri89] Graham Brightwell. Semiorders and the 1/3–2/3 conjecture. Order, 5(4):369–380,
1989.
[Bri99] Graham Brightwell. Balanced pairs in partial orders. Discrete Mathematics, 201(13):25–52, 1999.
[BW91] Anders Bj¨orner and Michelle L. Wachs. Permutation statistics and linear extensions
of posets. Journal of Combinatorial Theory - Series A, 58(1):85–114, 1991.
[Fre76] Michael L. Fredman. How good is the information theory bound in sorting? Theoretical Computer Science, 1(4):355 – 361, 1976.
[GHP87] B. Ganter, G. Hafner, and W. Poguntke. On linear extensions of ordered sets with
a symmetry. Discrete Mathematics, 63:153–156, 1987.
[Kis68] S.S Kislitsyn. Finite partially ordered sets and their associated sets of permutation.
Matematicheskiye Zametki, 4:511–518, 1968.
[KS84] Jeff Kahn and Michael Saks. Balancing poset extensions. Order, 1(2):113–126, 1984.
[Lin84] Nathan Linial. The information-theoretic bound is good for merging. SIAM Journal
on Computing, 13(4):795 – 801, 1984.
[Pec06] Marcin Peczarski. The gold partition conjecture. Order, 23(1):89–95, 2006.
[Pec08] Marcin Peczarski. The gold partition conjecture for 6-thin posets. Order, 25(2):91–
103, 2008.
[Ros95] Guido Rossum. Python reference manual. Technical report, Amsterdam, The Netherlands, The Netherlands, 1995.
[Sta11] Richard P. Stanley. Enumerative Combinatorics: Volume 1. Cambridge University
Press, New York, NY, USA, 2nd edition, 2011.
41

[TGF92] W. T. Trotter, W. G. Gehrlein, and P. C. Fishburn. Balance theorems for height-2
posets. Order, 9(1):43–53, 1992.
[Zag12] Imed Zaguia. The 1/3 − 2/3 conjecture for n-free ordered sets. Elec. J. Combinatorics, 19(2):1–5, 2012.
[Zag16] I. Zaguia. The 1/3-2/3 Conjecture for ordered sets whose cover graph is a forest.
ArXiv e-prints, October 2016.

42