Hostname: page-component-7c8c6479df-94d59 Total loading time: 0 Render date: 2024-03-19T11:40:32.723Z Has data issue: false hasContentIssue false

Hamiltonian Cycles in Regular Tournaments

Published online by Cambridge University Press:  01 March 2007

BILL CUCKLER*
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, NJ08854, USA (e-mail: cuckler@math.rutgers.edu)

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
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 291296.Google Scholar
[2]Alon, N. (1990) The maximum number of Hamiltonian paths in tournaments. Combinatorica 10 319324.Google Scholar
[3]Alon, N. and Spencer, J. (2000) The Probabilistic Method, 2nd edn, Wiley-Interscience, New York.Google 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 945949.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 769781.Google Scholar
[8]Grimmett, G. (1999) Percolation, 2nd edn, Springer, New York.Google Scholar
[9]Kahn, J. and Kim,, J. H. (1998) Random matchings in regular graphs. Combinatorica 8 201226.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. 148188.Google 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 161164.Google 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 8083.Google Scholar
[16]Szele, T. (1943) Kombinatorikai vizsgalatok az iranyitott teljes graffal. kapcsolatban, Mt. Fiz. Lapok 50 223256.Google Scholar
[17]Thomassen, C. (1985) Hamilton circuits in regular tournaments. Annals Discrete Math. 27 159162.Google Scholar
[18]Thomassen, C. (1980) Hamiltonian-connected tournaments J. Combin. Theory Ser. B 28 142163.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