On the number of 4-cycles in a tournament
Preprint
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\cdot 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.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- The clique density theoremAnnals of Mathematics, 2016
- On the Local Profiles of TreesJournal of Graph Theory, 2015
- Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐UniversalJournal of Graph Theory, 2014
- The number of cliques in graphs of given order and sizeTransactions of the American Mathematical Society, 2010
- On the Minimal Density of Triangles in GraphsCombinatorics, Probability and Computing, 2008
- Flag algebrasThe Journal of Symbolic Logic, 2007