Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-17T08:21:27.385Z Has data issue: false hasContentIssue false
  • English
  • Français

The Proofs of Two Directed Paths Conjectures of Bollobás and Leader

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  22 May 2017

TREVOR PINTO
TREVOR PINTO*
Affiliation:
School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

Let A and B be disjoint sets, of size 2k, of vertices of Qn, the n-dimensional hypercube. In 1997, Bollobás and Leader proved that there must be (n − k)2k 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ás 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.

MSC classification

Primary: 05C38: Paths and cycles
Secondary: 05D05: Extremal set theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 5 , September 2017 , pp. 762 - 774
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Bollobás, B. (1998) Modern Graph Theory, Vol. 184 of Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[2] Bollobás, B. and Leader, I. (1997) Matchings and paths in the cube. Discrete Appl. Math. 75 1–8.CrossRefGoogle Scholar
[3] Bernstein, A. J. (1967) Maximally connected arrays on the n-cube. SIAM J. Appl. Math. 15 1485–1489.CrossRefGoogle Scholar
[4] Cameron, P. J. (2005) Problems from the 16th British Combinatorial Conference. Discrete Math. 293 313–320.CrossRefGoogle Scholar
[5] Chung, F. R. K., Füredi, Z., Graham, R. L. and Seymour, P. D. (1988) On induced subgraphs of the cube. J. Combin. Theory Ser. A 49 180–187.CrossRefGoogle Scholar
[6] Harper, L. H. (1964) Optimal assignments of numbers to vertices. SIAM J. Appl. Math. 12 131–135.CrossRefGoogle Scholar
[7] Harper, L. H. (1966) Optimal numberings and isoperimetric problems on graphs. J. Combin. Theory 1 385–394.CrossRefGoogle Scholar
[8] Hart, S. (1976) A note on the edges of the n-cube. Discrete Math. 14 157–163.CrossRefGoogle Scholar
[9] Lindsey, J. H. (1964) Assignment of numbers to vertices. Amer. Math. Monthly 71 508–516.CrossRefGoogle Scholar
[10] Lovász, L. (1993) Combinatorial Problems and Exercises, North-Holland.Google Scholar