Rainbow triangles in three-colored graphs
Rainbow triangles in three-colored graphs
复制标题
三色图中的彩虹三角形
DOI：
10.1016/j.jctb.2017.04.002
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Michael Young
中科院分区：
文献类型：
--
作者：
J. Balogh;Ping Hu;Bernard Lidický;Florian Pfender;Jan Volec;Michael Young
Erdés和Sós提出了确定n个顶点的3-边色完全图中彩虹三角形的最大数目F（n）的问题。证明了F（n）= F（a）+ F（B）+ F（c）+ F（d）+ a B c+ a B d+ a cd + B cd，其中a+ B+ c+ d= n，a，B，c，d尽可能相等.我们证明了当n足够大时，所得到的递推关系成立。我们还证明了对n= 4k的猜想，其中k≥ 0.这些结果意味着lim <$F（n）（n3）= 0.4，并确定了唯一的极限对象.在证明中，我们使用旗代数结合稳定性参数。
Erdős and Sós proposed the problem of determining the maximum number F (n) of rainbow triangles in 3-edge-colored complete graphs on n vertices. They conjectured that F (n)= F (a)+ F (b)+ F (c)+ F (d)+ a b c+ a b d+ a c d+ b c d, where a+ b+ c+ d= n and a, b, c, d are as equal as possible. We prove that the conjectured recurrence holds for sufficiently large n. We also prove the conjecture for n= 4 k for all k≥ 0. These results imply that lim F (n)(n 3)= 0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.
排列中长度为 4 的单调子序列的最小数量
DOI：
10.1017/s0963548314000820
发表时间：
2014
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
BALOGH J
通讯作者：
BALOGH J