On the Number of 4‐Cycles in a Tournament
On the Number of 4‐Cycles in a Tournament
复制标题
关于锦标赛中 4 周期的数量
DOI：
--
复制
发表时间：
2014
影响因子：
0.9
通讯作者：
Avraham Morgenstern
中科院分区：
文献类型：
--
作者：
N. Linial;Avraham Morgenstern
如果T是一个有给定数目的3圈的n顶点竞赛图，那么关于它的4圈的数目可以说什么？这个问题最有趣的范围是假设T有c·n3个循环三元组，其中某些c>0，我们寻求最小化4-循环的数量。我们猜想（渐近）最小化T是一个常数大小的传递竞赛图的随机爆破。利用旗代数的方法，我们得到了一个几乎与约束值相匹配的下界。我们能够回答最大化4周期数的简单问题。这些问题可以等价地表示为传递子竞赛图。也就是说，给定T中传递三元组的数量，它可以有多少传递四元组？据我们所知，这是第一次研究诱导比赛。
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·n3 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.