On the Number of 4‐Cycles in a Tournament. Issue 3 (8th October 2015)

• Record Type: Journal Article
• Authors: Linial, Nati; Morgenstern, Avraham
• Is Part Of: Journal of graph theory. Volume 83:Issue 3(2016)
• Page Start: 266
• Page End: 276
• Publication Date: 2015-10-08
• Subjects: local graph theory -- tournaments -- extremal combinatorics -- small cycles in tournaments; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21996
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: If T is an n ‐vertex tournament with a given number of 3‐cycles, what can be said about the number of its 4‐cycles? The most interesting range of this problem is where T is assumed to have c · n 3 cyclic triples for some c > 0 and we seek to minimize the number of 4‐cycles. We conjecture that the (asymptotic) minimizing T is a random blow‐up of a constant‐sized transitive tournament. Using the method of flag algebras, we derive a lower bound that almost matches the conjectured value. We are able to answer the easier problem of maximizing the number of 4‐cycles. These questions can be equivalently stated in terms of transitive subtournaments. Namely, given the number of transitive triples in T, how many transitive quadruples can it have? As far as we know, this is the first study of inducibility in tournaments.