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
• DOI: 10.1016/s0166-218x(96)00076-5

✦ 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.