Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-11T02:45:15.690Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Bollobás–Eldridge Conjecture for Bipartite Graphs

Published online by Cambridge University Press:  01 September 2007

B. CSABA
B. CSABA*
Affiliation:
Analysis and Stochastics Research Group of the Hungarian Academy of Sciences, Hungary
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 G be a simple graph on n vertices. A conjecture of Bollobás and Eldridge [5] asserts that if $\delta (G)\geq \frac{kn-1}{k+1}$ then G contains any n vertex graph H with Δ(H) = k. We prove a strengthened version of this conjecture for bipartite, bounded degree H, for sufficiently large n. This is the first result on this conjecture for expander graphs of arbitrary (but bounded) degree. An important tool for the proof is a new version of the Blow-Up Lemma.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 5 , September 2007 , pp. 661 - 691
Copyright
Copyright © Cambridge University Press 2007

References

[1]Aigner, M. and Brandt, S. (1993) Embedding arbitrary graphs of maximum degree two. J. London Math. Soc. 48 39–51.CrossRefGoogle Scholar
[2]Alon, N. and Fischer, E. (1996) 2-factors in dense graphs. Discrete Math. 152 13–23.CrossRefGoogle Scholar
[3]Azuma, K. (1967) Weighted sums of certain dependent variables. Tohoku Math. J. 3 357–367.Google Scholar
[4]Bollobás, B. (1978) Extremal Graph Theory, Academic Press.Google Scholar
[5]Bollobás, B. and Eldridge, S. E. (1978) Packing of graphs and applications to computational complexity. J. Combin. Theory Ser. B 25 105–124.CrossRefGoogle Scholar
[6]Corrádi, H. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Hung. 14 423–439.CrossRefGoogle Scholar
[7]Csaba, B. (2003) The Bollobás–Eldridge conjecture for graphs of maximum degree four. Manuscript.Google Scholar
[8]Csaba, B., Shokoufandeh, A. and Szemerédi, E. (2003) Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three. Combinatorica 23 35–72.CrossRefGoogle Scholar
[9]Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of Erdős. In Combinatorial Theory and its Applications II (P. Erdős and V. T. Sós, eds), Colloquia Mathematica Societatis János Bolyai, North-Holland, Amsterdam/London.Google Scholar
[10]Hajnal, P. (1991) An $\Omega(n^{\frac{4}{3}})$lower bound on the randomized decision tree complexity of graph properties. Combinatorica 11 131–143.CrossRefGoogle Scholar
[11]Hajnal, P. and Szegedy, M. (1992) On packing bipartite graphs. Combinatorica 12 295–301.CrossRefGoogle Scholar
[12]Hoeffding, W. (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13–30.CrossRefGoogle Scholar
[13]Komlós, J., Sárközy, G. N. and Szemerédi, E. (1997) Blow-Up Lemma. Combinatorica 17 109–123.CrossRefGoogle Scholar
[14]Komlós, J., Sárközy, G. N. and Szemerédi, E. (1998), An algorithmic version of the Blow-Up Lemma. Random Struct. Alg. 12 297–312.3.0.CO;2-Q>CrossRefGoogle Scholar
[15]Komlós, J. and Simonovits, M. (1993), Szemerédi's Regularity Lemma and its applications in graph theory. In Combinatorics: Paul Erdős is Eighty, 2 (Keszthely, 1993), pp. 295–352.Google Scholar
[16]Sauer, N. and Spencer, J. (1978), Edge-disjoint placements of graphs. J. Combin. Theory Ser. B 25 295–302.CrossRefGoogle Scholar
[17]Szemerédi, E. (1976) Regular partitions of graphs. Colloques Internationaux CNRS No 260: Problèmes Combinatoires et Théorie des Graphes, Orsay, 399–401.Google Scholar