The proofs of two directed paths conjectures of Bollobás and Leader

DOI10.1017/S0963548317000086zbMATH Open1371.05151arXiv1504.07079OpenAlexW2962790459WikidataQ113857421 ScholiaQ113857421MaRDI QIDQ5366965FDOQ5366965

Authors: Trevor Pinto 

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: Let $A$ and $B$ be disjoint sets, of size $2^k$, of vertices of $Q_n$, the $n$-dimensional hypercube. In 1997, Bollob'as and Leader proved that there must be $(n-k)2^k$ edge-disjoint paths between such $A$ and $B$. They conjectured that when $A$ is a down-set and $B$ is an up-set, these paths may be chosen to be directed (that is, the vertices in the path form a chain). We use a novel type of compression argument to prove stronger versions of these conjectures, namely that the largest number of edge-disjoint paths between a down-set $A$ and an up-set $B$ is the same as the largest number of directed edge-disjoint paths between $A$ and $B$. Bollob'as and Leader made an analogous conjecture for vertex-disjoint paths and we prove a strengthening of this by similar methods. We also prove similar results for all other sizes of $A$ and $B$.

Full work available at URL: https://arxiv.org/abs/1504.07079

Recommendations

• Matchings and paths in the cube
• Path partitions of hypercubes
• Disjoint paths in hypercubes with prescribed origins and lengths
• Paired many-to-many disjoint path covers of the hypercubes
• Edge‐cutsets in the directed hypercube

zbMATH Keywords

\(n\)-cubematchingsdirected paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Extremal set theory (05D05)

Cites Work

• Title not available (Why is that?)
• On induced subgraphs of the cube
• A note on the edges of the n-cube
• Maximally Connected Arrays on the n-Cube
• Optimal Assignments of Numbers to Vertices
• Title not available (Why is that?)
• Optimal numberings and isoperimetric problems on graphs
• Assignment of Numbers to Vertices
• Research problems from the 19th British Combinatorial Conference
• Matchings and paths in the cube

Cited In (2)

• A proof of the two-path conjecture
• Edge‐cutsets in the directed hypercube

This page was built for publication: The proofs of two directed paths conjectures of Bollobás and Leader

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366965)