Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-02-06T14:06:12.326Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Extremal combinatorics Graph theory

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
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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