On the 1-factorizations of Middle Level Graph:
Inner structure, Algorithm, and Application∗
Kai Jin1
1

The University of Hong Kong, Hong Kong SAR, China
cscjjk@gmail.com

arXiv:1704.08852v4 [cs.DM] 12 Feb 2018

Abstract
In this paper, we revisit the lexical and modular factorization of the middle level graph. As results,
we provide their alternative definitions, which are either simpler or more direct than the previous
definitions, and derive their interesting properties and formulas, which shed insights into their
inner combinatorial structures. Moreover, we design optimum algorithms for computing these
factorizations, which can be applied in playing restricted-supply hat-guessing games.
1998 ACM Subject Classification G.2.1 Combinatorics; G.2.2 Graph Theory; F.2.2 Nonnumerical Algorithms and Problems; I.2.11 Distributed Artificial Intelligence
Keywords and phrases Modular factorization, Lexical factorization, Middle level graph, Bipartite Kneser graph, Coding theory
Digital Object Identifier 10.4230/LIPIcs.SWAT.2018.23

1

Introduction

The bipartite Kneser graph H(n, k) (k < n/2) has as vertices all k-element and (n − k)element subsets of [n] := {1, . . . , n} and an edge between any two vertices when one is a
subset of the other. Because it is regular and bipartite, each bipartite Kneser graph admits a
1-factorization due to Hall’s Marriage Theorem [14]. For the special case n = 2k + 1, graph
H(2k + 1, k) is also known as the middle level graph and it admits two explicit 1-factorizations
– lexical factorization [15] and modular factorization [8] (see definitions in Section 2). However,
to the best of our knowledge, it remains a challenging open problem for decades to give an
explicit factorization of the general bipartite Kneser graphs.
In this paper, we show that 1-factorizations of bipartite Kneser graph can be applied
in playing restricted-supply hat-guessing games (see the details in Subsection 1.1), which
hopefully motivates the investigation of the above open problem. As part of an ongoing
effort to solve this open problem, we then conduct a comprehensive study of the two existing
factorizations of middle level graphs. First, we propose an intuitive definition of the modular
factorization, which establishes a connection between this factorization and the inversion
number of permutations [23]. Second, we show an inner structure of the lexical factorization,
which leads to not only a direct constructive proof that the factorization is well-defined
(the previous proof was indirect), but also an optimum algorithm for computing such a
factorization. This algorithm is applicable in playing the aforementioned hat-guessing games.
Moreover, we prove new properties (referred to as variation laws; see Lemma 3 and 12) of
the two factorizations, which present some similarities between these factorizations.

∗

This work was partially supported by someone. (To be added later.)

© Kai Jin;
licensed under Creative Commons License CC-BY
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018).
Editors: John Q. Open and Joan R. Acces; Article No. 23; pp. 23:1–23:15
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

23:2

1-factorizations of Middle Level Graph

In addition, we propose a simple method to explicitly construct a 1-factor (but not a
1-factorization) for the general bipartite Kneser graph (see Definition 13).
Other related work. The bipartite Kneser graph is strongly related to the set inclusion
matrix introduced in [24]. Such matrix has been studied extensively in recent years due to
their connections to t-design in coding theory (see [4, 12] and the references within).
Historical motivation. Although the problem of constructing an explicit 1-factorization
of the middle level graph is worth to study in its own right, it was once motivated by the
middle level conjecture, which states that middle level graphs are hamiltonian. It was hoped
that people can find two 1-factors (i.e. perfect matchings) which form a Hamiltonian cycle.
However, after extensive studies for thirty years, the conjecture itself was settled recently by
Mütze [17]. See also [18] for an optimum algorithm for computing such a Hamiltonian cycle.
Moreover, Mütze and Su [19] proved that the bipartite Kneser graphs are Hamiltonian.

1.1

Motivations from cooperative games

Hat-guessing games have been studied extensively in a broad area due to their relations to
graph entropy, circuit complexity, network coding, and auctions [1, 3, 5, 6, 9, 10, 11, 16, 21].
We consider the following restricted-supply hat-guessing game.
♠ Restricted-supply hat-guessing game. Assume there are n hats, each with a different
color in [n] = {1, . . . , n}. (This means the supply for hats in each color is uniquely restricted.)
Assume m players and one dealer (nature) are playing the following game.
The dealer randomly places k hats to each player (assume n − mk = d > 0).
Each player can observe those hats placed to any other player, but cannot see and has
to guess the k colors of hats on his or her own head. The guess is private between one
player and the dealer – players are forbidden to communicate during the game.
Player i (i ∈ [m]) is allowed to guess gi times. A guess is correct if all the k colors are
correct. If any guess of any player is correct, all players (as a team) win the game.
It is permissible for the players to discuss a strategy before the game starts.
Question How do the players design the strategy to achieve the optimum chance of winning?
The answer for the two players case (i.e. m = 2) is as follows.
Graph Model. After placement of hats, the state of the game can be represented as an edge
in H(n, k). Let A, B respectively denote the set of colors placed to Player 1 and Player 2.
Let A0 = [n] − B. The current state is the edge (A, A0 ). Each player knows one node of
the edge; to be clear, Player 1 observes A0 whereas Player 2 observes A.

k+d
Upper bound. The uncertainty for each
player
is
. This is the degree of each node.
d

k+d
By one guess, a player has 1/ d chance to win. Therefore,
the maximum winning

probability is no larger than p = max{1, (g1 + g2 )/ k+d
}.
d
Lower bound. Suppose we have a 1-factorization of H(n, k). This 1-factorization labels
each edge by a number in [ k+d
d ]. In the g1 + g2 guesses of Player 1 and Player 2, they
respectively choose the edges with labels 1, . . . , g1 + g2 . Thus, the players win the game
when the label of the edge is in [g1 + g2 ], which occurs with probability p.
To play this game easily, both players wish to have a simple 1-factorization. This gives a
motivation to design an explicit 1-factorization of the general bipartite Kneser graphs.
I Example 1. n = 3, k = d = g1 = g2 = 1. If Player 1 observes b, she guesses b mod 3 + 1.
If Player 2 observes a, he guesses a mod 3 + 1. Then, exactly one player guesses right.

K. Jin

23:3

We can consider other winning rules, e.g. the team wins if each player has at least one
correct guess. For this variant rule, the case m = 2 can also be solved according
to a

k+d
1-factorization. The maximum winning probability is p0 = min{g1 , g2 , k+d
}/
.
d
d
In addition, we point out that a 1-factor of the middle level graph can be used in the above
hating-guessing game for another restricted case k = 1, d = m − 1, g1 = . . . = gm = 1. Let C
denote the set of colors placed to the m players. Let Ci (i ∈ [m]) denote the set of colors
observed by player i. Note that |Ci | = m − 1, |C| = m and n = mk + d = 2m − 1. Assume γ
is a 1-factor of H(2m − 1, m − 1). After observing Ci , player i answers the 1-element set
γ(Ci ) − Ci . Since γ is a perfect matching, there exists one and only one element c ∈ C such
that γ(C − {c}) = C. Obviously, the player whom is placed by c is the only one who guesses
correctly. Therefore, exact one player is correct. Therefore, this is the best strategy.

2

Preliminaries

The subset lattice is the family of all subsets of [n], partially ordered by inclusion. Let Pk
denote the k-th layer of this subset lattice, whose members are the k-element subsets of [n].
Denote [k#, k4, 1×] as the multiset of 2k + 1 characters with k ‘#’s, k ‘4’s, and 1 ‘×’. Let
the words clockwise and counterclockwise be abbreviated as CW and CCW respectively.
A representation of edges of H(2k + 1, k) by permutations of [k#, k4, 1×]. An edge
(A, A0 ) from Pk to Pk+1 in the middle level graph H(2k + 1, k) can be represented by a permutation of [k#, k4, 1×], where the k ‘#’s indicate the k elements in A, the k ‘4’s indicate
the k elements that are not in A0 , and the unique ‘×’ indicates the unique element in A0 − A.
For convenience, we do not distinguish the edges with their corresponding permutations.
Giving a 1-factorization of the middle level graph is equivalent to giving a labeling
function f from these 2k+1
k,k,1 permutations to integers 0, . . . , k so that
(a) f (ρ) 6= f (σ) for those pairs ρ, σ who admit the same positions for k #’s; and
(b) f (ρ) 6= f (σ) for those pairs ρ, σ who admit the same positions for k 4’s.
Then, for fixed i (0 ≤ i ≤ k), all edges labeled by i constitute a 1-factor, denoted by Ff,i ,
and Ff,0 , . . . , Ff,k constitute a 1-factorization of the middle level graph.
For any sequence S = (S1 , . . . , Sn ) and integer j, the j-th cyclic-shift of S is defined as
S (j) := (S1+j , . . . , Sn+j ), where subscripts are taken modulo n. We say that the labeling
function f is cyclic, and so that the 1-factorization Ff,0 , . . . , Ff,k is cyclic, if ∀ρ, f (ρ(1) ) = f (ρ).
The lexical factorization[15]. (Note: we use a slightly simplified description based on
[15].) Let ρ = (ρ1 , . . . , ρ2k+1 ) be any permutation of [k#, k4, 1×]. Arrange ρ1 , . . . , ρ2k+1 in
a cycle in CW order. For any ρj that equals #, it is positive if there are more #’s than 4’s
in the interval that starts from the unique × and ends at ρj in CW order. The number of
positive #’s is defined to be fLEX (ρ). See Figure 1 for an illustration. It is proved in [15] that
fLEX satisfies the above two conditions (a) and (b). We provide in Section 4 an alternative
proof which is more direct. The lexical factorization is {L0 , . . . , Lk }, where Li = FfLEX ,i .

fLEX(×◯Δ◯Δ◯Δ)=3

fLEX(Δ◯×◯Δ◯Δ)=2

fLEX(Δ◯Δ◯×◯Δ)=1

fLEX(Δ◯Δ◯Δ◯×)=0

Figure 1 Illustration of the definition of fLEX . In the graph, the solid circles indicate positive #’s.
Note that the positions of #’s are identical in all the permutations drawn here. As we see, the four
permutations are mapped to different numbers under fLEX .

S WAT 2 0 1 8

23:4

1-factorizations of Middle Level Graph

The modular factorization[8]. The modular factorization is given by {M0 , . . . , Mk }
where Mi is a 1-factor defined as follows. Assume A ∈ Pk . Let ΣA indicate the sum of all
elements in A. Let y = (ΣA + i) mod (k + 1). Here we assume that y is restricted to [k + 1].
Then, Mi (A) = A ∪ {z}, where z denotes the y-th largest element in [n] − A.
For example, assume k = 3, n = 2k + 1 = 7, and A = {2, 4, 6}.
When i = 0, we have y = 12 mod 4 = 4 and z = 1. So M0 (A) = {1, 2, 4, 6}.
When i = 1, we have y = 13 mod 4 = 1 and z = 7. So M1 (A) = {2, 4, 6, 7}.
When i = 2, we have y = 14 mod 4 = 2 and z = 5. So M2 (A) = {2, 4, 5, 6}.
When i = 3, we have y = 15 mod 4 = 3 and z = 3. So M3 (A) = {2, 3, 4, 6}.
Fact: 1. It is proved in [8] that Mi is a 1-factor for each i. Moreover, it is obvious that such
1-factors are pairwise-disjoint. 2. Assume Mi (A) = A0 . We can compute A from i and A0 in
a symmetric way. Let x = (ΣA0 + i) mod (k + 1) ∈ [k + 1] where ΣA0 indicates the sum of
elements in A0 . Then A = A0 − {z}, where z is the x-th smallest element in A0 .
The following lemma gives two equivalent labeling functions of the modular factorization.
I Lemma 2. Let ρ = (ρ1 , . . . , ρ2k+1 ) be any permutation of [k#, k4, 1×]. For each i ∈
[2k + 1], we call i the position of character ρi . Let O1ρ , . . . , Okρ be the positions of all #’s in ρ
and T1ρ , . . . , Tkρ the positions of all 4’s. Denote by rank4 (ρ) the rank of × when enumerating
all 4’s and × in ρ in CCW. So, rank4 (ρ) − 1 is the number of 4’s that have positions larger
than the position of ×. Denote by rank# (ρ) the rank of × when enumerating all #’s and ×
in ρ in CCW. The labeling function of {M0 , . . . , Mk } is given by fmod , where
fmod (ρ)

:= rank4 (ρ) − Σkj=1 Ojρ

fmod (ρ)

Σkj=1 Tjρ

:=

1+

(mod k + 1), or

− rank# (ρ)

(1)

(mod k + 1).

(2)

Proof. We first state two trivial observations:
(×’s position) + Σj Ojρ + Σj Tjρ = 1 + . . . + (2k + 1) = 0

(mod k + 1)

(×’s position) + rank4 (ρ) − 1 + rank# (ρ) − 1 = 2k + 1 = −1

(mod k + 1).

By subtraction, we get rank4 (ρ) − Σkj=1 Ojρ = 1 + Σkj=1 Tjρ − rank# (ρ) (mod k + 1).
Therefore, the two definitions of fmod given in (1) and (2) are equivalent.
Next, we show that fmod is the labelling function of {M0 , . . . , Mk }.
Recall that ρ represents the edge (A, A0 ) in the middle level graph, where A = {O1ρ , . . . , Okρ }
and A0 = {O1ρ , . . . , Okρ , the position of ×}. We shall prove that (A, A0 ) ∈ Mfmod (ρ) . By the
definition of Mfmod (ρ) , it reduces to proving that the single element in A0 −A is the y-th largest
one in [n] − A, where y = (ΣA + fmod (ρ)) mod (k + 1) (y ∈ [k + 1]). Namely, the unique ×
has rank y when enumerating all 4’s or × in ρ in CCW, namely, rank4 (ρ) = y mod (k + 1).
This holds because y = ΣA + fmod (ρ) = Σkj=1 Ojρ + rank4 (ρ) − Σkj=1 Ojρ mod (k + 1).
J

3

Modular factorization

In this section, we introduce a new labeling function fMOD (which is different from fmod )
and prove that fMOD ≡ fmod + C for some constant C. Therefore, {FfMOD ,0 , . . . , FfMOD ,k }
constitute an equivalent definition of the modular factorization.
Assume ρ = (ρ1 , . . . , ρ2k+1 ) is an arbitrary permutation of [k#, k4, 1×]. Arrange
ρ1 , . . . , ρ2k+1 in CW order. We count the number of tuples (×, #, 4) which are located in CW order within this cycle of characters (whose positions may not be consecutive).
Taken modulo by (k + 1), the remainder is defined as fMOD (ρ). See Figure 2 for an illustration.

K. Jin

23:5

fMOD(ρ)=1

fMOD(ρ)=0

#(×◯Δ)=5=1(mod 4)

#(×◯Δ)=4=0(mod 4)

fMOD(ρ)=2

#(×◯Δ)=6=2(mod 4)

fMOD(ρ)=3
#(×◯Δ)=3(mod 4)

Figure 2 Illustration of the definition of fMOD . In the four permutations drawn here, the positions
of #’s are identical. As we see, these permutations are mapped to different numbers under fMOD .
This figure also illustrates the equation fMOD (ρ×→4 ) = fMOD (ρ) − 1 (mod k + 1) discussed below.

Let ρ×→4 be constructed from ρ, which swaps × with its CW next 4.
Let ρ×→# be constructed from ρ, which swaps × with its CW next #.
Let ρ4←× be constructed from ρ, which swaps × with its CCW next 4.
Let ρ#←× be constructed from ρ, which swaps × with its CCW next #.
The following lemma shows that fmod and fMOD have the same variation law. As a
corollary, there must exist a constant C so that fMOD ≡ fmod + C.
I Lemma 3. Let ρ be any permutation of [k#, k4, 1×]. We have:
fMOD (ρ×→4 ) = fMOD (ρ#←× ) = fMOD (ρ) − 1 (mod k + 1),
fMOD (ρ×→# ) = fMOD (ρ4←× ) = fMOD (ρ) + 1 (mod k + 1).
f (ρ×→4 ) = f (ρ#←× ) = f (ρ) − 1 (mod k + 1)
mod

fmod (ρ

mod

×→#

) = fmod (ρ

mod

4←×

) = fmod (ρ) + 1

(mod k + 1).

(3)
(4)
(5)
(6)

Note: According to (3) or (4), function fMOD satisfies the two conditions (a) and (b).
t

ρ

t

ρ

×→Δ

Figure 3 Illustration of the proof the variation law of fMOD function..

Proof. We prove (3) and (5). (4) is equivalent to (3) and (6) is equivalent to (5).
We first prove fMOD (ρ×→4 ) = fMOD (ρ)−1 (mod k+1). The other equation fMOD (ρ#←× ) =
fMOD (ρ) − 1 (mod k + 1) in (3) is symmetric; proof omitted. See Figure 3. Denote by t the
number of #’s between × and its CW next 4 in ρ. Recall that fMOD (ρ) denotes the number
of (×, #, 4)-tuples which are located in CW order within ρ (and then modulo k + 1). So,
fMOD (ρ×→4 ) − fMOD (ρ) = (k − t) · 1 − t · k mod (k + 1). To see this more clearly, we state:
(i) For the (k − t) #’s that are located between the 4 being swapped and × (in CW order),
the number of (×, #, 4)-tuples related to each of them increases by 1.
(ii) For the other #’s, the number of (×, #, 4)-tuples related to each of them decreases by k.
The above equation implies that fMOD (ρ×→4 ) = fMOD (ρ) − 1 mod (k + 1).
Next, we prove (5). By swapping × with its CW next 4, rank4 (ρ) decreases by 1. Further
applying (1), fmod (ρ) = rank4 (ρ) − Σkj=1 Ojρ (mod k + 1) decreases by 1. Symmetrically,
by swapping × with its CCW next #, rank# (ρ) increases by 1. Further applying (2),
fmod (ρ) = 1 + Σkj=1 Tjρ − rank# (ρ) (mod k + 1) decreases by 1.
J

C = 0,
when k is even;
Note: To be complete, we point out that
C = (k + 1)/2, when k is odd.

S WAT 2 0 1 8

23:6

1-factorizations of Middle Level Graph

I Remark. 1. Following the above definition of fMOD , we immediately see that the modular
factorization is cyclic (although it was proved in [8], their proof was more complicated).
2. Through this definition of fMOD , we have established an interesting connection between
the modular factorization and the inversion number of permutations [23].

4

Lexical factorization

In this section, we first present a direct proof of the statement that fLEX satisfies (a) and
(b). Based on an inner structure of the lexical factorization revealed in this proof, we then
design optimum algorithms for solving two fundamental computational problems about the
factorization (P1 and P2 below). Finally we prove variation laws of lexical factorization.
P1. Given a k-element subset A and an integer i ∈ {0, . . . , k}, how do we find the unique A0
so that (A, A0 ) ∈ Li ? In other words, given number i and the positions of #’s in ρ and
suppose fLEX (ρ) = i, how do we determine the position of × in ρ?
P2. Given a (k + 1)-element subset A0 and an integer i ∈ {0, . . . , k}, how do we find the
unique A so that (A, A0 ) ∈ Li ? In other words, given number i and the positions of 4’s
in ρ and suppose fLEX (ρ) = i , how do we determine the position of × in ρ?

4.1

fLEX satisfies (a) and (b) – a constructive proof

I Lemma 4. Given any sequence S of k of right parentheses ‘)’ and k + 1 left parentheses
‘(’. There exists a unique cyclic-shift S (j) of S whose first 2k parentheses are paired up when
parenthesized, and we can compute j in O(k) time. (See the proof in Appendix A.)
I Example 5. Assume k = 9. S = (1 (2 )3 )4 )5 (6 (7 (8 )9 )10 (11 )12 )13 (14 (15 )16 (17 (18 )19 .
The unique cyclic-shift in which the first 2k parentheses are paired up is:
     
   
    
(14)
S
=
(2 )3
(8 )9
.
15

16

17 18 19 1

4

5

6 7

10 11 12

13

14

I Definition 6 (Index). Given a sequence S of 2k + 1 parentheses, k of which are right
parentheses and k + 1 are left, and assume that its first 2k parentheses are paired up. We
index the k + 1 left parentheses in S by 0, . . . , k according to the following rule: The
smaller the depth, the less the index; and index from right to left for those
under the same depth. Here, depth is defined in the standard way; it is the number of
pairs of matched parentheses that cover the fixed parenthesis. Moreover, we index the k
right parentheses in such a way that any two paired parentheses have the same index.
For convenience, let depth(Si ), index(Si ) denote the depth and index of Si for each i.
For S (14) in Example 5, the depth and index are drawn below.
   
|{z}
0

()



()

   

;

   

()



()

   

.

|{z}
|{z} |{z}
|{z} |{z}
|{z} |{z}
|{z} |{z} |{z}
|{z}
2
2
9
8
1 | {z }
7 | {z }
| {z } 1
| {z } 4
0
3
0
1
1
6
5
|
{z
}|
{z
}
|
{z
}|
{z
}
0

0

2

1

I Lemma 7. Assume S is given as Definition 6. For any Sl = ( and Sr =), there are more
)’s than (’s in the (cyclic) interval {Sl+1 , Sl+2 , . . . , Sr } if and only if index(Sl ) ≥ index(Sr ).

K. Jin

23:7

Proof. For each i (0 ≤ i ≤ 2k + 1), denote
Hi

=

the number of ‘)’s − the number of ‘(’s in S1 , . . . , Si ,

Hi0

=

the number of ‘)’s − the number of ‘(’s in Si+1 , . . . , S2k+1 .

0
To be clear, H0 = H2k+1
= 0. Trivially, we have:

Hi + Hi0 = −1 (for all i).

depth(Sl ) = −Hl − 1.

depth(Sr ) = −Hr .

We need to discuss two cases depending on which one of l, r is smaller.
Case 1: l < r. Let us count the number of ’)’s minus the number of ’(’s in the interval
Sl+1 , . . . , Sr . This is given by Hr − Hl . Therefore,
there are more ’)’s in this interval ⇔ Hr − Hl > 0 ⇔ −depth(Sr ) + depth(Sl ) + 1 > 0
By definition of index, for l < r, we have

⇔ depth(Sr ) ≤ depth(Sl ) ⇐========================⇒ index(Sr ) ≤ index(Sl ).
Case 2: r < l. The number of ’)’ minus the number of ’(’s in (cyclic) interval
Sl+1 , . . . , S2k+1 , S1 , . . . , Sr is given by Hl0 + Hr = −1 − Hl + Hr . Therefore,
there are more ’)’s in this interval ⇔ −1 − Hl + Hr > 0 ⇔ depth(Sl ) − depth(Sr ) > 0
By definition of index, for r < l, we have

⇔ depth(Sr ) < depth(Sl ) ⇐========================⇒ index(Sr ) ≤ index(Sl ).
In either case, the lemma holds.

J

I Corollary 8. 1. Given S as Definition 6 and l such that Sl =0 (0 . Construct a permutation
ρ of [k#, k4, 1×] as follows: first copy S; then replace k )’s by #’s and replace the l-th
character by × and replace the other k (’s by 4’s. Then, fLEX (ρ) = index(Sl ).
2. fLEX satisfies (a) and (b).
Proof. 1. By Lemma 7, the positive #’s correspond to those right parentheses whose indices
are smaller than or equal to index(Sl ). So, the amount, i.e. fLEX (ρ), equals index(Sl ).
2. To prove (a), assume k + 1 distinct permutations ρ0 , . . . , ρk share the same positions
of #’s, we argue that fLEX (ρ0 ), . . . , fLEX (ρk ) are distinct. First, construct a sequence S
of parentheses: Si =0 )0 if and only if ρ0i = . . . = ρki = #. Without loss of generality,
assume the first 2k parentheses of S are paired up. Otherwise, cyclicly shift S, ρ0 , . . . , ρk
simultaneously until this holds (recall Lemma 4 and notice that fLEX (ρ0 ) = fLEX (ρ) for
 cyclic
shift ρ0 of ρ). By the first claim in this corollary, we know fLEX (ρ0 ), . . . , fLEX (ρk ) equals
(index(Sl0 ), . . . , index(Slk )), where li (i ∈ {0, . . . , k}) denotes the position of × in ρi . These
k + 1 indices are distinct because l0 , . . . , lk are distinct and because Sli =0 (0 for all i.
Before proving (b), we define the dual of ρ, denoted by ρ∗ , to be another permutation of
[k#, k4, 1×] constructed from ρ by swapping the 4’s with #’s. Formally,

 ×, when ρi = ×;
ρ∗i =
4, when ρi = #; for each i ∈ [2k + 1].

#, when ρi = 4

Assume k + 1 permutations ρ0 , . . . , ρk are distinct but share the same positions of 4’s.
Then, (ρ0 )∗ , . . . , (ρk )∗ share the same positions of #’s. Then, fLEX ((ρ0 )∗ ), . . . , fLEX ((ρk )∗ )
are distinct due to (a). Therefore, fLEX (ρ0 ), . . . , fLEX (ρk ) are distinct because fLEX (ρ∗ ) ≡
k − fLEX (ρ). (The last equation is formally stated in Lemma 15 in Appendix A.)
J
I Remark. The previous proof in [15] did not reveal the simple connection between fLEX (·) and
the indices of the parentheses, i.e. fLEX (ρ) = index(Sl ). This connection plays an important
role in designing our linear time algorithm for solving P1 and P2.

S WAT 2 0 1 8

23:8

1-factorizations of Middle Level Graph

4.2

Linear Time Algorithms for P1 and P2

Recall P1 and P2 at the beginning of this section. They admit trivial O(k 2 ) time solutions
as follows. Given the positions of #’s in ρ and the number i, we can enumerate the position
of the unique × among the remaining k + 1 positions and compute fLEX (ρ) in O(k) time,
until that we find the returning value is i. P2 can be solved symmetrically.
By utilizing the aforementioned connection between fLEX (·) and the indices of the parentheses, we can actually compute fLEX () for all candidate permutations ρ0 , . . . , ρk (the
positions of #’s in these permutations are as given) altogether in O(k) time, and then easily
find the correct candidate ρj so that fLEX (ρj ) = i. We present the algorithm in the following.

1

2
3
4

Input: set A ∈ Pk and number i ∈ {0, . . . , k}.
(Elements in A indicate the positions of #’s in permutation ρ.)
Output: set A0 = A ∪ {z} so that (A, A0 ) ∈ Li .
(Integer z indicates the position of × so that fLEX (ρ) = i.)
Compute a parentheses sequence T = (T1 , . . . , T2k+1 ) as follows.
Ti =0 )0 when i ∈ A and Ti =0 (0 when i ∈
/ A.
Compute the unique j so that the first 2k parentheses are paired up in T (j) .
Compute the entire index for S = T (j) according to Definition 6.
Find the unique left parenthesis Sz−j in S with index i and output A0 = A ∪ {z}.
Algorithm 1: Computing the unique A0 such that (A, A0 ) ∈ Li .

I Theorem 9. 1. Algorithm 1 solves P1 in O(k) time.
2. P2 can be reduced to P1 and thus can be solved in O(k) time.
Proof. 1. Construct ρ from S = T (j) and l = z − j as described in Corollary 8.1. The
following imply that (A, A0 ) ∈ Li : (1) ρ(−j) is the permutation corresponding to edge (A, A0 )
and (2) fLEX (ρ(−j) ) = i. Proof of (1): Because the set of positions of #’s in ρ(−j) is the same
as the set of positions of ’)’s in T , which equals A, and the position of × in ρ(−j) is at z, we
get (1). Proof of (2): fLEX (ρ(−j) ) = fLEX (ρ) = index(Sz−j ) = i. This applies Corollary 8.1.
Running time analysis. By Lemma 4, Step 2 takes O(k) time. Moreover, it is easy to
compute the index for each parenthesis in S in O(k) time according to the definition of index;
so Step 3 also takes O(k) time. All the other steps clearly run in O(k) time.
2. Applying the equation fLEX (ρ∗ ) = k − fLEX (ρ) (see the proof of Corollary 8.2 for the
definition of ρ∗ ), the instance (A0 , i) of P2 reduces to the instance ([n] − A0 , k − i) of P1. J
I Remark. 1. The main difficulty in designing Algorithm 1 for solving P1 essentially lies in
finding the correct order to index the parentheses as described in Definition 6.
2. The counterparts of P1 and P2 in the modular factorization are easy to solve in O(k) time
according to the definition; see also the second fact above Lemma 2.

4.3

Variation laws of fLEX

Assume ρ is an arbitrary permutation of [k#, k4, 1×] in this subsection.
I Definition 10. Consider any character 4 or # in ρ. We say it is CW-balanced if there are
equal number of 4’s and #’s in the (cyclic) interval of ρ starting from × to this character in
CW order. Similarly, we say it is CCW-balanced if there are equal number of 4’s and #’s in
the (cyclic) interval of ρ starting from × to this character in CCW order.

K. Jin

23:9

I Lemma 11. 1. fLEX (ρ) > 0 ⇔ there is a CW-balanced 4 ⇔ there is a CCW-balanced #.
2. fLEX (ρ) < k ⇔ there is a CW-balanced # ⇔ there is a CCW-balanced 4.
Proof of Lemma 11 is put in Appendix A due to space limit.
When fLEX (ρ) > 0, let ρ×4 (respectively, ρ#× ) be constructed from ρ by swapping
× with the CW first CW-balanced 4 (respectively, the CCW first CCW-balanced #).
When fLEX (ρ) < k, let ρ×# (respectively, ρ4× ) be constructed from ρ by swapping
× with the CW first CW-balanced # (respectively, the CCW first CCW-balanced 4).
I Lemma 12 (Variation law of fLEX ; see Lemma 3 for a comparison).

fLEX (ρ×4 ) = fLEX (ρ#× ) = fLEX (ρ) − 1 (when fLEX (ρ) > 0).
fLEX (ρ×# ) = fLEX (ρ4× ) = fLEX (ρ) + 1 (when fLEX (ρ) < k).

(7)
(8)

See Figure 1 for an illustration of the equation fLEX (ρ×4 ) = fLEX (ρ) − 1.
See Figure 4 for an illustration of the equation fLEX (ρ×# ) = fLEX (ρ) + 1.

fLEX=0

fLEX=2

fLEX=1

fLEX=3

Figure 4 Illustration of the variation law fLEX (ρ×# ) = fLEX (ρ) + 1. The bold circles indicate
the CW first CW-balanced #’s. No CW-balanced # exists in the last picture.

Proof. We only prove fLEX (ρ×4 ) = fLEX (ρ) − 1. The other equations are symmetric.
Without loss of generality, assume ρ1 = ×. For each i (1 ≤ i ≤ n), define the number of
#’s minus the number of 4’s in {ρ1 , . . . , ρi } as the height of ρi . (So, a # is positive if and
only if its height is positive.) Let ρi be the CW first # with height 1. Let ρj be the CW
first 4 with height 0, i.e. the CW first CW-balanced 4. As illustrated in Figure 5, ρ×4
is constructed from ρ by swapping ρ1 with ρj . We shall prove that after the swapping, the
number of positive #’s decreases by 1. This follows from three observations:
(i) ρi = # is positive in ρ (with height 1) but not anymore in ρ×4 (with height 0).
(ii) For other #’s in ρ2 , . . . , ρj , their heights drop by 1, but their positivity do not change.
(iii) For the #’s in ρj+1 , . . . , ρ2k+1 , their heights and positivity stay the same as before. J
ρ1
X

ρi

◯

ρj
Δ

Figure 5 Illustration of the proof of fLEX (ρ×4 ) = fLEX (ρ) − 1. The dotted line indicates ρ×4 .

I Remark. Since the variation laws define the entire 1-factorization, designing a 1-factorization
of the general bipartite Kneser graph reduces to designing some compatible variation laws.

5

Explicit 1-factors of the bipartite Kneser graph

In this section, we demonstrate the construction of explicit 1-factors of the general bipartite
Kneser graph, which are also called antipodal matchings of the subset lattice. We construct

S WAT 2 0 1 8

23:10

1-factorizations of Middle Level Graph

n

two disjoint 1-factors γkn and γ 0 k of graph H(n, k). They can be used to design an optimum
explicit strategy for the restricted-supply hat-guessing games (Subsection 1.1) under the case
m = 2, g1 = g2 = 1 (two players and one guess for each). Such 1-factors can also be applied
in the following card game called Magician-assistant-audience. We then show connections
between γkn , lexical factorization, and a well-known decomposition of the subset lattice.
♠ Magician-assistant-audience. Suppose you are a magician who hired a beautiful
assistant. There are n = 2k + d distinct cards and you randomly ask one audience to pick any
k + d of them and discard the others. You don’t know which cards are picked or discarded,
but your assistant knows. She further discards d cards and gives you the remaining k cards.
By looking at these k cards, you must guess the k cards discarded by the audience. The
thing is that you can always guess right if you cooperate well with your assistant using a
predefined 1-factor of H(n, k). The trick is as follows. When a subset A0 of [n] is picked,
your assistant seeks the unique subset A that is matched to A0 in the 1-factor and discards
A0 − A. Inversely, you seek the unique subset A0 matched to A and answer [n] − A0 .
I Definition 13. Assume A ⊂ [n] and |A| ≤ n/2. By the following two steps, we can obtain
a subset A0 which has equal size as A and is disjoint with A, and we define it to be (A).
Step 1. Write down all the numbers in [n] to a cycle from 1 to n in CW order.
Step 2. Enumerate each number a in A, find the CCW first number from a that is not
contained in A ∪ A0 yet and add it to A0 . (Note: The order of this enumeration does not
matter. Take n = 10 and A = {1, 3, 8, 9} for example. In order 1, 3, 8, 9, the numbers added
to A0 would be 10, 2, 7, 6. In order 3, 9, 8, 1, the numbers added to A0 would be 2, 7, 6, 10.)
We define the CW-rotating-subset  (A) symmetrically (change CCW to CW in Step 2).
n
Assume k < n/2. For each A ⊂ Pk , define γkn (A) := [n]− (A) and γ 0 k (A) := [n]−  (A).
n
Obviously, γkn and γ 0 k are two disjoint 1-factors of H(n, k).
When n = 2k + 1, matching γkn is exactly the lexical matching L0 . Replace all
elements in A by # and all the elements in (A) by 4 and the remaining element by ×.
Clearly, this permutation is mapped to 0 under fLEX , because no # is positive. Similarly,
n
when n = 2k + 1, matching γ 0 k is exactly the lexical matching Lk .
Next, we show a connection between γkn and a chain-decomposition of the subset lattice.
Parenthesis sequence of each set. Given A ⊆ [n]. We can associate with A a sequence
of parentheses of length n. First, write down all numbers 1, . . . , n into a list. If x ∈ A, replace
x by a right parenthesis; otherwise, replace x by a left parenthesis. For example, if n = 10, the
sequence associated with A = {1, 3, 4, 8, 9} is )1 (2 )3 )4 (5 (6 (7 )8 )9 (10 .
This sequence of parentheses can be parenthesized uniquely in the usual way, and there
may remain several parenthesis unpaired. For the above example, “(2 ” is paired with “)3 ”,
“(6 ” is paired with “)9 ”, and “(7 ” is paired with “)8 ”. All the others are unpaired. Note that
all the unpaired right parentheses always occur to the left of the unpaired left parentheses.
Chain-decomposition of the subset lattice via parenthesizing[13]. Two subsets of
[n] are in the same chain, if and only if their associated parenthesis sequences contain the
same paired parenthesis. Equivalently, suppose A ⊂ [n] is associated with sequence S.
Replace the leftmost unpaired ’(’ in S by ’)’ and assume that the new sequence corresponds
to subset A0 . Then, A0 is the next member in the chain containing A. For the above example,
the leftmost unpaired ’(’ is (5 , so A0 = {1, 3, 4, 5, 8, 9}. The entire chain in this example is
{3, 8, 9} → {1, 3, 8, 9} → {1, 3, 4, 8, 9} → {1, 3, 4, 5, 8, 9} → {1, 3, 4, 5, 8, 9, 10}.
Clearly, all chains in this decomposition are symmetric – if a chain contains a member A,
it must contain a member with size n − |A|. So, this chain-decomposition implicitly defines
an antipodal matching βkn between the antipodal layers Pk and Pn−k for each k < n/2.

K. Jin

23:11

The entire chain-decomposition for n = 4:
∅→

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

→
→
→
→

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

→
→
→
→

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

→ {1, 2, 3, 4}

The matching β25 induced by the
chain-decomposition for n = 5:
{1, 2} → {1, 2, 3}
{1, 3} → {1, 3, 4}
{1, 4} → {1, 2, 4}
{1, 5} → {1, 2, 5}
{2, 3} → {2, 3, 4}

{2, 4} → {2, 4, 5}
{2, 5} → {2, 3, 5}
{3, 4} → {3, 4, 5}
{3, 5} → {1, 3, 5}
{4, 5} → {1, 4, 5}

Interestingly, it turns out that βkn is equivalent to γkn . Therefore, our definition of γkn
essentially gives an explicit definition of the antipodal matching βkn . (Note: By applying the
Cycle Lemma [7], [20] presented an even more explicit but more complicated definition of βkn .
Based on their definition, they further showed that βkn (A) can be computed in O(n) time.
They also gave an application of these antipodal matchings in coding theory.)
I Lemma 14. Assume k < n/2. We have βkn (A) = γkn (A) for any A ∈ Pk .
We put the proof in Appendix B due to limit of space. Here, we verify the case n = 5, j = 2.

Figure 6 Illustration of γ25 . The 1-st picture demonstrates that
({1, 2}) = {4, 5}, and so
= {1, 2, 3}; the 2-nd shows ({1, 3}) = {2, 5}, and so γ25 ({1, 3}) = {1, 3, 4}; etc. The gray
circle in each picture indicates the only element in γ25 (A) − A. It can be checked that γ25 = β25 .
γ25 ({1, 2})

Chain-decomposition via greedy algorithm. A few years earlier than [13], Aigner [2]
constructed a matching λk between two consecutive layers Pk , Pk+1 of the subset lattice
via the following greedy algorithm (Algorithm 2). The n matchings λ0 , . . . , λn−1 together
describe a chain-decomposition of the subset lattice, which turns out to be equivalent to the
above one via parenthesizing. This was not mentioned in [13], but was proved in [22, 25];
unfortunately, their proofs are obscure; so we present a much clearer proof in appendix C.
1
2

3

foreach member A of Pk in lexicographic order do
Find the lexicographic smallest unmatched member of Pk+1 which contains A. If
such a member of Pk+1 is found, match it to A.
end

Algorithm 2: Greedy algorithm for constructing a matching λk between Pk and Pk+1 .
Summary. We discover an intuitive tuple-counting definition of the modular factorization,
an inner structure and an optimum algorithm related to the lexical factorization, and their
so-called variation laws. Our results also make a few existing results more transparent. These
may be helpful in attacking the open problem mentioned in the front page of the paper.
Acknowledgements. We thank Professors Zhiyi Huang and Xiaoming Sun for discussions.
References
1

2

G. Aggarwal, A. Fiat, A.V. Goldberg, J.D. Hartline, N. Immorlica, and M. Sudan. Derandomization of auctions. In Proceedings of the Thirty-seventh Annual ACM Symposium on
Theory of Computing, STOC ’05, pages 619–625. ACM, 2005.
M. Aigner. Lexicographic matching in boolean algebras. Journal of Combinatorial Theory,
Series B, 14(3):187 – 194, 1973.

S WAT 2 0 1 8

23:12

1-factorizations of Middle Level Graph

3

4
5
6
7
8
9
10
11

12
13
14
15
16
17
18

19
20
21

22
23
24
25

J. Aspnes, R. Beigel, M. Furst, and S. Rudich. The expressive power of voting polynomials.
In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing,
STOC ’91, pages 402–409. ACM, 1991.
R.B. Bapat. Moore–penrose inverse of set inclusion matrices. Linear Algebra and its
Applications, 318(1):35 – 44, 2000.
O. Ben-Zwi, I. Newman, and G. Wolfovitz. Hats, auctions and derandomization. Random
Structures & Algorithms, 46(3):478–493, 2015.
S. Butler, M.T. Hajiaghayi, R.D. Kleinberg, and T. Leighton. Hat guessing games. SIAM
Review, 51(2):399–413, 2009.
N. Dershowitz and S. Zaks. The cycle lemma and some applications. European Journal of
Combinatorics, 11(1):35–40, 1990.
D.A Duffus, H.A Kierstead, and H.S Snevily. An explicit 1-factorization in the middle of
the boolean lattice. Journal of Combinatorial Theory, Series A, 65(2):334 – 342, 1994.
T. Ebert, W. Merkle, and H. Vollmer. On the autoreducibility of random sequences. SIAM
Journal on Computing, 32(6):1542–1569, 2003.
M. Gadouleau and N. Georgiou. New constructions and bounds for winkler’s hat game.
SIAM Journal on Discrete Mathematics, 29(2):823–834, 2015.
M. Gadouleau and S. Riis. Graph-theoretical constructions for graph entropy and network
coding based communications. IEEE Transactions on Information Theory, 57(10):6703–
6717, Oct 2011.
E. Ghorbani, G.B. Khosrovshahi, Ch. Maysoori, and M. Mohammad-Noori. Inclusion
matrices and chains. Journal of Combinatorial Theory, Series A, 115(5):878 – 887, 2008.
C. Greene and D. J Kleitman. Strong versions of sperner’s theorem. Journal of Combinatorial Theory, Series A, 20(1):80 – 88, 1976.
P. Hall. On representatives of subsets. Journal of the London Mathematical Society, s110(1):26–30, 1935.
H.A Kierstead and W.T Trotter. Explicit matchings in the middle levels of the boolean
lattice. Order, 5(2):163–171, 1988.
T. Ma, X. Sun, and H. Yu. A new variation of hat guessing games. In Computing and
Combinatorics, pages 616–626. Springer Berlin Heidelberg, 2011.
T. Mütze. Proof of the middle levels conjecture. Proc. of the London Mathematical Society,
112(4):677, 2016.
T. Mütze and J. Nummenpalo. A constant-time algorithm for middle levels gray codes.
In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17,
pages 2238–2253. Society for Industrial and Applied Mathematics, 2017.
T. Mütze and P. Su. Bipartite kneser graphs are hamiltonian. Electronic Notes in Discrete
Mathematics (EuroComb), 49:259 – 267, 2015.
E. Ordentlich and R. M. Roth. Low complexity two-dimensional weight-constrained codes.
IEEE Transactions on Information Theory, 58(6):3892–3899, June 2012.
The-New-York-Time.
Why mathematicians now care about their hat color.
Technical report, 2001.
URL: http://www.nytimes.com/2001/04/10/science/
why-mathematicians-now-care-about-their-hat-color.html.
D.E White and S.G Williamson. Recursive matching algorithms and linear orders on the
subset lattice. Journal of Combinatorial Theory, Series A, 23(2):117 – 127, 1977.
Wikipedia. Inversion. Technical report, 2018. URL: https://en.wikipedia.org/wiki/
Inversion_(discrete_mathematics).
R.M. Wilson. Incidence matrices of t-designs. Linear Algebra and its Applications, 46:73 –
82, 1982.
K.M. WingLeld. Modular and lexical matchings in the middle levels graph. Master dissertation, 2009.

K. Jin

A

23:13

Miscellaneous
n

Disclaimer. The two 1-factors γkn and γ 0 k have been introduced and used in another manuscript
of the author and that manuscript is still under reviewed. However, since they are strongly related
to the topic of this paper, we repeat this part of result in this exposition for completeness. In fact,
this manuscript was finished earlier but it encountered two rejections in the process of publishing.
Nevertheless, we declare that the common parts are no more than 10 percents of either paper.

Proof of Lemma 4. Assume S is a sequence of n = 2k + 1 parentheses, k of which are ‘)’s.
We are interested in finding a cyclic-shift of S in which the first 2k parentheses can be paired
up when parenthesizing.
5

13

5

10

15

20

25

30

35

40

S=( ( ) ) ) ( ( ( ) ) ( ) ) ( ( ) ( ( ) ( ( ) ) ) ( ( ( ) ) ( ) )
Figure 7 Illustration of Lemma 4. This figure draws Example 5.

Denote Hi = the number of ‘)’s − the number of ‘(’s in S1 , . . . , Si for each i. Draw points
{(i, Hi ) | 0 ≤ i ≤ n} in the Cartesian plane, as shown in Figure 7.
Select the highest point (j ∗ , Hj ∗ ); for a tie, select the rightmost one.
When j 6= j ∗ + 1, the cyclic-shift S (j) does not satisfy our requirement. This is because
when j 6= j ∗ + 1, the one shifted from Sj ∗ +1 , which is a left parenthesis, cannot be paired up.
When j = j ∗ + 1, the cyclic-shift S (j) satisfies our requirement. This is simply illustrated in
the figure. To complete the proof, we point out that index j ∗ + 1 can easily be computed in
O(k) time. We also note that this lemma is a simple application of the Cycle Lemma [7]. J
Proof of Lemma 11. Without loss of generality, assume that ρ1 = ×. For each i (1 ≤ i ≤ n),
define the height of ρi as the number of #’s minus the number of 4’s in {ρ1 , . . . , ρi }. (So, a
# is positive if and only if its height is positive.)
Proof of Claim 1. Assume fLEX (ρ) > 0. In this case there exists some # with positive
height. This implies that there exists a pair of (i, j) such that ρi = # has a height 1 while
ρj = 4 has a height 0. See Figure 5. Clearly, ρj is a CW-balanced 4 while ρi is a CCWbalanced #. On the other direction, the existence of a CW-balanced 4 or a CCW-balanced
# implies the existence of a positive #, which immediately implies that fLEX (ρ) > 0.
Claim 2 is symmetric to Claim 1; proof omitted.
J
I Lemma 15. Assume ρ is an arbitrary permutation of [k#, k4, 1×]. Then, we have
fLEX (ρ) + fLEX (ρ∗ )
∗

fMOD (ρ) + fMOD (ρ )

= k, and
= k

2

(mod k + 1).

(9)
(10)

The proof is trivial. See illustration of the first equation in Figure 8.

Figure 8 Illustration of fLEX (ρ) + fLEX (ρ∗ ) = k. The dotted line indicates ρ∗ .

S WAT 2 0 1 8

23:14

1-factorizations of Middle Level Graph

B

βkn = γkn – a simple proof

Recall the antipodal matching βkn (k < n/2) induces by the “chain-decomposition via
parenthesizing” between the two antipodal layers Pk and Pn−k (see Section 5). We shall
prove that
βkn (A) = [n]− (A) for any A ∈ Pk .
Here, we first prove it by an example and then give the formal proof.
Recall the parenthesis sequence associated with set A ⊂ [n] below Definition 13. For
convenience, denote it by PS(A).
I Example 16. n = 11, A = {1, 3, 4, 8, 9}. The sequence of parentheses associated with A is:
PS(A) =

)

1

(2

)3

)

4

(

5

(6

(7

)8

)9

(

10

(

11

.

The unpaired parentheses are boxed for ease of distinction.
There are two unmatched right parentheses and three unmatched left parentheses. According to the definition of the chain-decomposition, in its symmetric member β511 (A) we
should replace the first unmatched left parenthesis by a right parenthesis. So,
PS(β511 (A)) =

)

(2

1

)3

)

4

)

5

(6

(7

)8

)9

(

10

(

11

.

Then, let us also compute (A) and [n]− (A). (In the following, the positions of boxes
stay the same as above; they do not indicate the unpaired parentheses.)
PS(

(A)) =

(

PS([n]−

(A)) =

)

1

1

)2

(3

(

(2

)3

)

We see PS(β511 (A)) = PS([n]−

4

4

(
)

5

5

)6

)7

(8

(9

)

(6

(7

)8

)9

(

(A)). Therefore, β511 (A) = [n]−

10

10

)
(

11

.

11

.

(A).

Proof. For any i ∈ [n], we shall prove that
(X) i ∈ βkn (A) if and only if i ∈ [n]−

(A).

We discuss two cases distinguished by whether i belongs to U , where U denotes the set
of unpaired positions of PS(A) (the positions of a sequence are indexed by 1, . . . , n).
Case 1: i ∈
/ U . Then, the i-th parenthesis of PS(A) is paired. It will not change within
the chain containing A and βkn (A). Therefore, (I) i ∈ βkn (A) if and only if i ∈ A. On the
other hand, by the definition of (A), it easily follows that i ∈ (A) if and only if i ∈
/ A.
(In the example above, the paired number 3 in A will go to 2 in (A), the paired numbers
8 and 9 will go to 6 and 7 in
(A). So i ∈ (A) if and only if i ∈
/ A.) Therefore, (II)
i ∈ [n]− (A) if and only if i ∈ A. Combine (I) and (II), we get statement (X).
Case 2: i ∈ U . Assume PS(A) has r unpaired right parentheses and l unpaired left
parentheses. For any sequence S with length n, let S (U ) denote the subsequence of S that
are located at U . We state the following arguments about the parentheses locating at U .
1. PS(A)(U ) starts by r ‘)’s and is followed by l ‘(’s.
2. PS(βkn (A))(U ) starts by l ‘)’s and is followed by r ‘(’s.
3. PS( (A))(U ) starts by l ‘(’s and is followed by r ‘)’s.
4. PS([n]− (A))(U ) starts by l ‘)’s and is followed by r ‘(’s.
The first argument is according to the assumption of l and r. The second follows by 1
and the fact that βkn (A) is the symmetric member of A in the chain containing them. The
third follows by 1 and the definition of the CCW-rotating-subset. The last follows by the
third. According to 2 and 4, we obtain (X) for those i in U altogether.
J

K. Jin

C

23:15

Equivalence of two chain-decompositions

In this appendix, we prove that the chain-decomposition of the subset lattice of [n] given by
λ0 , . . . , λn−1 is equivalent to the decomposition via parenthesizing (see Section 5). Our proof
is based on the following observation of λ0 , . . . , λn−1 (Lemma 17) which was proved in [2].
I Lemma 17. [2] Assume A = {a1 , . . . , am } ⊂ [n], where a1 < . . . < am and m > 0. Denote
a0 = 0. Define φ(A) to be the largest index j ∗ in 0, . . . , m such that
aj ∗ − 2j ∗ = min{aj − 2j | 0 ≤ j ≤ m}.

Then

λm (A) = A ∪ {aφ(A) + 1}, aφ(A) < n;
λm (A) is undefined,
aφ(A) = n.

I Example 18. For n = 5, we have
A
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{2, 3}

φ(A)
2
2
1
1
2

λ2 (A)
{1, 2, 3}
{1, 3, 4}
{1, 2, 4}
{1, 2, 5}
{2, 3, 4}

A
{2, 4}
{2, 5}
{3, 4}
{3, 5}
{4, 5}

φ(A)
2
1
2
0
0

λ2 (A)
{2, 4, 5}
{2, 3, 5}
{3, 4, 5}
{1, 3, 5}
{1, 4, 5}

I Definition 19. Given A ⊂ [n]. Recall the sequence of parenthesis associated with A (see
Section 5). Define ParentAdd(A) to be the position of the first unpaired left parenthesis when
parenthesizing; define it as n + 1 if all the left parentheses are paired.
Define GreedyAdd(A) = aφ(A) + 1.
10

9

8

7

Using the above definitions together with Lemma 17, proving the equivalence of the two
decompositions reduces to proving the following lemma.
6

5

I Lemma 20. For any subset A ⊂ [n], ParentAdd(A) = GreedyAdd(A).
4

3

2

)

1

8

6

4

2
1

2

(

2

4

( ) ( )

)

6

) ( ) (
i* ( )
8

10

12

14

16

18

20

22

24

26

n=13,A={3,5,6,7,8,10,13}

3

Figure 9 Illustration of the proof of Lemma 20
4

5

Proof. Assume A = {a1 , . . . , am }, where a1 < . . . < am . Assume a0 = 0.
For 1 ≤ i ≤ n, let bi = +1 if i ∈ A and bi = −1 if i ∈
/ A. Let Hi = b1 + . . . + bi .
Let i∗ be the largest index in 0, . . . , n such that Hi∗ = max{Hi | 0 ≤ i ≤ n}. Let j ∗ be
the largest index in 0, . . . , m such that Haj∗ = max{Haj | 0 ≤ j ≤ m}.
For each j (0 ≤ j ≤ m), we know Haj = 2j − aj , because there are j many +1s and
(aj −j) many −1s in {b1 , . . . , baj }. Therefore, we have φ(A) = j ∗ . Therefore, GreedyAdd(A) =
aφ(A) + 1 = aj ∗ + 1 = i∗ + 1. (Notice that aj ∗ = i∗ by the definition of i∗ , j ∗ .)
Clearly, in the parenthesis associated with A, the first unpaired left parenthesis appears at
position i∗ + 1. This is trivial and is illustrated in Figure 9. Therefore ParentAdd(A) = i∗ + 1.
Together, ParentAdd(A) = GreedyAdd(A).
J
6

7

8

Yet Another definition of the chain-decomposition. Recently, [12] proposed another
alternative definition for the above chain-decomposition. However, their definition looks
extremely complicated. We do not introduce it in detail in this manuscript.

S WAT 2 0 1 8

