𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Matchings and paths in the cube

✍ Scribed by Béla Bollobás; Imre Leader


Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
554 KB
Volume
75
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis


In this note we are concerned with the existence of matchings and families of disjoint paths between subsets of the n-dimensional discrete cube Qn. For example, we show that if A is a subset of Qn of size C:=,(;), where k c 4% then there is a matching from A to its complement of size at least (;).

We also present a conjecture concerning the existence of directed paths, and prove some related results.


📜 SIMILAR VOLUMES