Geodesic
The Shifted Turán Sieve Method on Tournaments
Canadian mathematical bulletin, Tome 62 (2019) no. 4, pp. 841-855

Voir la notice de l'article provenant de la source Cambridge University Press

We construct a shifted version of the Turán sieve method developed by R. Murty and the second author and apply it to counting problems on tournaments. More precisely, we obtain upper bounds for the number of tournaments which contain a fixed number of restricted $r$-cycles. These are the first concrete results which count the number of cycles over “all tournaments”.
DOI : 10.4153/S000843951900016X
Mots-clés : shifted Turán sieve, tournament, cycle 
Kuo, Wentang; Liu, Yu-Ru; Ribas, Sávio; Zhou, Kevin. The Shifted Turán Sieve Method on Tournaments. Canadian mathematical bulletin, Tome 62 (2019) no. 4, pp. 841-855. doi: 10.4153/S000843951900016X
@article{10_4153_S000843951900016X,
     author = {Kuo, Wentang and Liu, Yu-Ru and Ribas, S\'avio and Zhou, Kevin},
     title = {The {Shifted} {Tur\'an} {Sieve} {Method} on {Tournaments}},
     journal = {Canadian mathematical bulletin},
     pages = {841--855},
     year = {2019},
     volume = {62},
     number = {4},
     doi = {10.4153/S000843951900016X},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S000843951900016X/}
}
TY  - JOUR
AU  - Kuo, Wentang
AU  - Liu, Yu-Ru
AU  - Ribas, Sávio
AU  - Zhou, Kevin
TI  - The Shifted Turán Sieve Method on Tournaments
JO  - Canadian mathematical bulletin
PY  - 2019
SP  - 841
EP  - 855
VL  - 62
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S000843951900016X/
DO  - 10.4153/S000843951900016X
ID  - 10_4153_S000843951900016X
ER  - 
%0 Journal Article
%A Kuo, Wentang
%A Liu, Yu-Ru
%A Ribas, Sávio
%A Zhou, Kevin
%T The Shifted Turán Sieve Method on Tournaments
%J Canadian mathematical bulletin
%D 2019
%P 841-855
%V 62
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/S000843951900016X/
%R 10.4153/S000843951900016X
%F 10_4153_S000843951900016X

[1] Beineke, L. W. and Harary, F., The maximum number of strongly connected subtournaments . Canad. Math. Bull. 8(1965), 491–498. Google Scholar

[2] Chow, T. Y., The combinatorics behind number-theoretic sieves . Adv. Math. 138(1998), 293–305. Google Scholar

[3] Erdös, P. and Szekeres, G., A combinatorial problem in geometry . Compositio Math. 2(1965), 463–470. Google Scholar

[4] Gale, D., On the number of faces of a convex polygon . Canad. J. Math. 16(1964), 12–17. Google Scholar

[5] Gutin, G., Rafiey, A., and Yeo, A., On n-partite tournaments with unique n-cycle . Graphs Combin. 22(2006), 241–249. Google Scholar

[6] Hardy, G. H. and Ramanujan, S., The normal number of prime factors of a number n . Quart. J. Pure Appl. Math. 48(1917), 76–97. Google Scholar

[7] Kendall, M. G. and Babington Smith, B., On the method of paired comparisons . Biometrika 33(1940), 239–251. Google Scholar

[8] Kotzig, A., Sur le nombre des 4-cycles dans un tournoi . Mat. Časopis Sloven. Akad. Vied 18(1968), 247–254. Google Scholar

[9] Liu, Y.-R. and Murty, M. R., The Turán sieve method and some of its applications . J. Ramanujan Math. Soc. 14(1999), 21–35. Google Scholar

[10] Liu, Y.-R. and Murty, M. R., Sieve Methods in combinatorics . J. Combin. Theory Ser. A 111(2005), 1–23. Google Scholar

[11] Lovász, L., Combinatorial Problems and Exercises . North-Holland Pub. Co., Amsterdam, 1993. Google Scholar

[12] Moon, J. W., Topics on Tournaments . Holt, Rinehart and Winston Inc., New York, 1968. Google Scholar

[13] Moon, J. W., Uncovered nodes and 3-cycles in tournaments . Australas. J. Combin. 7(1993), 157–173. Google Scholar

[14] Moon, J. W., On the score sequence of an n-partite tournament . Canad. Math. Bull. 5(1962), 51–58. Google Scholar

[15] Moon, J. W. and Moser, L., On the distribution of 4-cycles in random bipartite tournaments . Canad. Math. Bull. 5(1962), 5–12. Google Scholar

[16] Moran, P. A. P., On the method of paired comparisons . Biometrika 34(1947), 363–365. Google Scholar

[17] Savchenko, S. V., On 5-cycles and 6-cycles in regular n-tournaments . J. Graph Theory 83(2016), 44–77. Google Scholar

[18] Szele, T., Kombinatorikai vizsgálatok az irányított teljes gráffal kapcsolatban . Mat. Fiz. Lapok 50(1943), 223–256. For a German translation, see Kombinatorische Untersuchungen über gerichtete vollständige Graphen, Publ. Math. Debrecen (1966), 145–168. Google Scholar

[19] Tabib, C., The number of 4-cycles in regular tournaments . Utilitas Math. 22(1982), 315–322. Google Scholar

[20] Turán, P., On a theorem of Hardy and Ramanujan . J. London Math. Soc. 9(1934), 274–276. Google Scholar

[21] Volkmann, L., On cycles in regular 3-partite tournaments . Discrete Math. 306(2006), 1198–1206. Google Scholar

[22] Volkmann, L., Longest cycles in almost regular 3-partite tournaments . Discrete Math. 306(2006), 2931–2942. Google Scholar

[23] Volkmann, L. and Winzen, S., Cycles through a given arc and certain partite sets in almost regular multipartite tournaments . Discrete Math. 283(2004), 217–229. Google Scholar

[24] Wilson, R. J., The Selberg sieve for a lattice. In: ‘Combinatorial Theory and Its Applications, Balatofüred (Hungary)’ . Colloq. Math. Soc. János Bolyai 4(1969), 1141–1149. Google Scholar

[25] Zhang, K. M., Vertex even-pancyclicity in bipartite tournaments . Nanjing Daxue Xuebao Shuxue Bannian Kan 1(1984), 85–88. Google Scholar

Cité par Sources :