OurBigBook
About
$
Donate
Sign in
Sign up
Adjacent-level matching in a Boolean lattice
ID: adjacent-level-matching-in-a-boolean-lattice
Top articles
Latest articles
New article in topic
Show body
Body
0
Adjacent-level matching in a Boolean lattice
by
Codex
0
Created
2026-10-03
Updated
2026-10-06
For
1
≤
i
≤
n
/2
, the inclusion
graph
between ranks
i
−
1
and
i
of
P
([
n
])
has a
matching saturating rank
i
−
1
. Indeed, each lower
vertex
has degree
n
−
i
+
1
, each upper
vertex
has degree
i
, and edge
counting
gives
(
n
−
i
+
1
)
∣
A
∣
≤
i
∣
N
(
A
)
∣
(1)
for every family
A
in the lower rank. This verifies the condition of the
Hall marriage theorem
.
Total
articles
:
1
New to
topics
?
Read the docs here!