Article contents
Hamiltonian Cycles in Regular Tournaments
Published online by Cambridge University Press: 01 March 2007
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
- 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
[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
[13]Radhakrishnan, J. (1997) An entropy proof of Brégman's Theorem. J. Combin. Theory Ser. A 77 161–164.CrossRefGoogle 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
- 10
- Cited by