Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T18:05:49.163Z Has data issue: false hasContentIssue false
  • English
  • Français

Hamiltonian Cycles in Regular Tournaments

Published online by Cambridge University Press:  01 March 2007

BILL CUCKLER
BILL CUCKLER*
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, NJ08854, USA (e-mail: cuckler@math.rutgers.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.

We show that every regular tournament on n vertices has at least n!/(2 + o(1))n Hamiltonian cycles, thus answering a question of Thomassen [17] and providing a partial answer to a question of Friedgut and Kahn [7]. This compares to an upper bound of about O(n0.25n!/2n) for arbitrary tournaments due to Friedgut and Kahn (somewhat improving Alon's bound of O(n0.5n!/2n)). A key ingredient of the proof is a martingale analysis of self-avoiding walks on a regular tournament.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 2 , March 2007 , pp. 239 - 249
Copyright
Copyright © Cambridge University Press 2006

References

[1]Adler, I., Alon, N. and Ross, S. M. (2001) On the maximum number of Hamiltonian paths in tournaments. Random Struct. Alg. 18 291–296.CrossRefGoogle Scholar
[2]Alon, N. (1990) The maximum number of Hamiltonian paths in tournaments. Combinatorica 10 319–324.Google Scholar
[3]Alon, N. and Spencer, J. (2000) The Probabilistic Method, 2nd edn, Wiley-Interscience, New York.CrossRefGoogle Scholar
[4]Bollobás,, B. (1988) Martingales, isoperimetric inequalities and random graphs. In Combinatorics (Hajnal, A., Lovász, L. and Sós, V. T., eds), Vol. 52 of Colloq. Math. Soc. János Bolyai, North Holland.Google Scholar
[5]Brégman, L. (1973) Some properties of nonnegative matrices and their permanents. Math. Doklady 14 945–949.Google Scholar
[6]Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. 1, Wiley, New York.Google Scholar
[7]Friedgut, E. and Kahn, J. (2005) On the number of Hamiltonian cycles in a tournament. Combin. Probab. Comput. 14 769–781.CrossRefGoogle Scholar
[8]Grimmett, G. (1999) Percolation, 2nd edn, Springer, New York.CrossRefGoogle Scholar
[9]Kahn, J. and Kim,, J. H. (1998) Random matchings in regular graphs. Combinatorica 8 201–226.Google Scholar
[10]Kemeny, J. and Snell, J. (1960) Finite Markov Chains, Van Nostrand Reinhold, New York.Google Scholar
[11]McDiarmid, C. J. H. (1989) On the method of bounded differences. In Surveys in Combinatorics 1989: Invited Papers at the 12th British Combinatorial Conference (Siemons, J., ed.), Cambridge University Press, pp. 148–188.CrossRefGoogle Scholar
[12]Moon, J. (1968) Topics on Tournaments, Holt, Rinehart and Winston, New York.Google Scholar
[13]Radhakrishnan, J. (1997) An entropy proof of Brégman's Theorem. J. Combin. Theory Ser. A 77 161–164.CrossRefGoogle Scholar
[14]Radhakrishnan, J. Entropy and counting, November 2001 Survey.Google Scholar
[15]Schrijver, A. (1978) A short proof of Minc's conjecture. J. Combin. Theory Ser. A 25 80–83.CrossRefGoogle Scholar
[16]Szele, T. (1943) Kombinatorikai vizsgalatok az iranyitott teljes graffal. kapcsolatban, Mt. Fiz. Lapok 50 223–256.Google Scholar
[17]Thomassen, C. (1985) Hamilton circuits in regular tournaments. Annals Discrete Math. 27 159–162.Google Scholar
[18]Thomassen, C. (1980) Hamiltonian-connected tournaments J. Combin. Theory Ser. B 28 142–163.Google Scholar
[19]West, D. (1991) Open Problem Column 3. SIAM Activity Group Newsletter in Discrete Mathematics, Summer 1991.Google Scholar
[20]Wormald, N. Tournaments with many Hamiltonian cycles. Preprint.Google Scholar