Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
复制标题
诱导 5 循环的最大密度是通过 5 循环的迭代吹胀实现的
DOI：
10.1016/j.ejc.2015.08.006
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Florian Pfender
中科院分区：
文献类型：
--
作者：
J. Balogh;Ping Hu;Bernard Lidický;Florian Pfender
令 C (n) 表示 n 个顶点上的图中 5 循环的诱导副本的最大数量。对于足够大的 n，我们证明 C (n)= a⋅ b⋅ c⋅ d⋅ e+ C (a)+ C (b)+ C (c)+ C (d)+ C (e)，其中 a+ b+ c+ d+ e= n 且 a、b、c、d、e 尽可能相等。此外，对于 n 的 5 次幂，我们表明，在 n 个顶点上最大化诱导 5 循环数量的唯一图是 5 循环的迭代放大。该证明使用标志代数计算和稳定性方法。
Let C (n) denote the maximum number of induced copies of 5-cycles in graphs on n vertices. For n large enough, we show that C (n)= a⋅ b⋅ c⋅ d⋅ e+ C (a)+ C (b)+ C (c)+ C (d)+ C (e), where a+ b+ c+ d+ e= n and a, b, c, d, e are as equal as possible. Moreover, for n a power of 5, we show that the unique graph on n vertices maximizing the number of induced 5-cycles is an iterated blow-up of a 5-cycle. The proof uses flag algebra computations and stability methods.
排列中长度为 4 的单调子序列的最小数量
DOI：
10.1017/s0963548314000820
发表时间：
2014
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
BALOGH J
通讯作者：
BALOGH J