On the number of 5-cycles in a tournament. (English) Zbl 1375.05118
Summary: We find a formula for the number of directed 5-cycles in a tournament in terms of its edge scores and use the formula to find upper and lower bounds on the number of 5-cycles in any \(n\)-tournament. In particular, we show that the maximum number of 5-cycles is asymptotically equal to \(\frac34\binom{n}{5}\), the expected number 5-cycles in a random tournament \((p=\frac12)\), with equality (up to order of magnitude) for almost all tournaments.
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C38 | Paths and cycles |
| 05C30 | Enumeration in graph theory |
| 05C35 | Extremal problems in graph theory |
| 05C80 | Random graphs (graph-theoretic aspects) |
References:
| [1] | L. W.Beineke and F.Harary, The maximum number of strongly connected subtournaments, Canad Math Bull8(4) 1965. · Zbl 0132.21303 |
| [2] | L. W.Beineke and K. B.Reid, Tournaments, Academic Press, London, 1978. |
| [3] | David M.Berman, On the number of 5‐cycles in a tournament, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 101-108. Congressus Numerantium, No. XIV. Utilitas Math., Winnipeg, Man., 1975. · Zbl 0321.05116 |
| [4] | D. M.Berman, The Number of 5‐cycles in a Tournament, PhD thesis, University of Pennsylvania, 1973. |
| [5] | S. A.Burr and V.Rosta, On the Ramsey multiplicities of graph problems and recent results, J Graph Theory4 (1980), 347-361. · Zbl 0455.05046 |
| [6] | D.Conlon, J.Fox, and B.Sudakov, An approximate version of Sidorenko’s conjecture, Geometric Funct Anal20(6) (2010), 1354-1366. · Zbl 1228.05285 |
| [7] | P.Erdös, On the number of complete subgraphs contained in certain graphs, Publ Math Inst Hung Acad Sci2(A3) (1962), 459-464. · Zbl 0116.01202 |
| [8] | A. W.Goodman, On sets of acquaintances and strangers at any party, Amer Math Monthly66 (1959), 778-783. · Zbl 0092.01305 |
| [9] | C.Jagger, P.Stovicek, and A. G.Thomason, Multiplicities of subgraphs, Combinatorica16 (1996), 123-141. · Zbl 0846.05061 |
| [10] | M. G.Kendall and B. B.Smith, On the method of paired comparisons, Biometrika (31) (1940), 324-345. · Zbl 0023.14803 |
| [11] | G.Lorden, Blue‐empty chromatic graphs, Amer Math Monthly69 (1962), 114-120. · Zbl 0108.18303 |
| [12] | J. W.Moon, On subtournaments of a tournament, Canad Math Bull9(3) (1966), 297-301. · Zbl 0141.41204 |
| [13] | J. W.Moon, Topics on Tournaments, Holt, Rinehart, and Winston, USA, 1968. · Zbl 0191.22701 |
| [14] | J. W.Moon, Uncovered nodes and 3‐cycles in tournaments, Australasian J Combin1993, 157-173. · Zbl 0781.05027 |
| [15] | K. B.Reid, Three problems on tournaments, Ann NY Acad Sci576 (1989), 466-473. |
| [16] | S. V.Savchenko, On 5‐cycles and 6‐cycles in regular n‐tournaments, J Graph Theory83(1) (2016), 44-77. · Zbl 1346.05098 |
| [17] | A. G.Thomason, Blue‐empty chromatic graphs: a disproof of a conjecture of Erdös in Ramsey Theory, J London Math Soc39(2) (1989), 246-255. · Zbl 0638.05037 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
