Hostname: page-component-74656f9884-6grmk Total loading time: 0 Render date: 2026-11-06T00:34:40.074Z Has data issue: false hasContentIssue false
  • English
  • Français

Karp–Sipser on Random Graphs with a Fixed Degree Sequence

Published online by Cambridge University Press:  20 June 2011

TOM BOHMAN  and
ALAN FRIEZE
TOM BOHMAN
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: tbohman@math.cmu.edu, alan@random.math.cmu.edu)
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: tbohman@math.cmu.edu, alan@random.math.cmu.edu)
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 Δ ≥ 3 be an integer. Given a fixed z ∈ +Δ such that zΔ > 0, we consider a graph Gz drawn uniformly at random from the collection of graphs with zin vertices of degree i for i = 1,. . .,Δ. We study the performance of the Karp–Sipser algorithm when applied to Gz. If there is an index δ > 1 such that z1 = . . . = zδ−1 = 0 and δzδ,. . .,ΔzΔ is a log-concave sequence of positive reals, then with high probability the Karp–Sipser algorithm succeeds in finding a matching with n ∥ z ∥ 1/2 − o(n1−ε) edges in Gz, where ε = ε (Δ, z) is a constant.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 5 , September 2011 , pp. 721 - 741
Copyright
Copyright © Cambridge University Press 2011

References

[1]Aronson, J., Frieze, A. and Pittel, B. (1998) Maximum matchings in sparse random graphs: Karp–Sipser revisited. Random Struct. Alg. 12 111–178.Google Scholar
[2]Bollobás, B. (1980) A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combin. 1 311–316.CrossRefGoogle Scholar
[3]Bollobás, B. (1981) Random graphs. In Combinatorics (Temperley, H., ed.), Vol. 52 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 80–102.Google Scholar
[4]Bollobás, B. and Frieze, A. (1985) On matchings and Hamiltonian cycles in random graphs. Ann. Discrete Math. 28 23–46.Google Scholar
[5]Chung, F., Lu, L. and Vu, V. (2003) The spectra of random graphs with given expected degrees. Proc. National Acad. Sci. 100 6313–6318.Google Scholar
[6]Edmonds, J. (1965) Paths, trees and flowers. Canad. J. Math. 17 449–467.Google Scholar
[7]Erdős, P. and Rényi, A. (1966) On the existence of a factor of degree one of a connected random graph. Acta. Math. Acad. Sci. Hungar. 17 359–368.CrossRefGoogle Scholar
[8]Frieze, A. (1986) Maximum matchings in a class of random graphs. J. Combin. Theory Ser. B 40 196–212.CrossRefGoogle Scholar
[9]Frieze, A. (2005) Perfect matchings in random bipartite graphs with minimum degree 2. Random Struct. Alg. 26 319–358.CrossRefGoogle Scholar
[10]Frieze, A. and Pittel, B. (2004) Perfect matchings in random graphs with prescribed minimal degree. In Trends in Mathematics, Birkhäuser, pp. 95–132.Google Scholar
[11]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.CrossRefGoogle Scholar
[12]Karonski, M. and Pittel, B. (2003) Existence of a perfect matching in a random (1 + e −1)—out bipartite graph, J. Combin. Theory Ser. B 88 1–6.Google Scholar
[13]Karp, R. and Sipser, M. (1981) Maximum matchings in sparse random graphs. In Proc. 22nd IEEE Symposium on the Foundations of Computing, pp. 364–375.Google Scholar
[14]Micali, S. and Vazirani, V. (1980) An O|V|1/2|E|) algorithm for finding maximum matchings in general graphs. In Proc. 21st IEEE Symposium on the Foundations of Computing.Google Scholar
[15]Molloy, M. and Reed, B. (1995) A critical point for random graphs with a given degree sequence. Random Struct. Alg. 6 161–180.Google Scholar
[16]Shi, L. and Wormald, N. (2007) Colouring random 4-regular graphs. Combin. Prob. Comput. 16 309–344.Google Scholar
[17]Wormald, N. (1999) The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms (Karonski, M. and Promel, H. J., eds), pp. 73–155.Google Scholar
[18]Walkup, D. (1980) Matchings in random regular bipartite graphs. Discrete Math. 31 59–64.Google Scholar