Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-02T20:28:11.971Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

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]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