Polynomial to exponential transition in Ramsey theory
Polynomial to exponential transition in Ramsey theory
复制标题
拉姆齐理论中的多项式到指数转变
DOI：
10.1112/plms.12320
复制
发表时间：
2020
影响因子：
1.8
通讯作者：
Razborov, Alexander
中科院分区：
文献类型：
--
作者：
Mubayi, Dhruv;Razborov, Alexander
给定，设是最小值，使得存在任意大一致超图，其独立数至多是顶点数的多对数，并且其中每个顶点跨越最多边。Erdés和Hajnal（1972）提出了一个可以用递归公式精确计算的公式，Erdés提供了500美元的证明。因为，这已经解决了许多价值观，包括权力的三，但它是不知道任何和。在这里，我们解决的猜想为所有。我们还回答了Bhat和Rödl的一个问题，对每一个都构造了一个具有正密度和至多上密度的均匀超图的拟随机序列。这个结果是尖锐的。
Given, letbe the minimumsuch that there exist arbitrarily large‐uniform hypergraphswhose independence number is at most polylogarithmic in the number of vertices and in which everyvertices span at mostedges. Erdős and Hajnal conjectured (1972) thatcan be calculated precisely using a recursive formula and Erdős offered $500 for a proof of this. For, this has been settled for many values ofincluding powers of three but it was not known for anyand.Here we settle the conjecture for all. We also answer a question of Bhat and Rödl by constructing, for each, a quasirandom sequence of‐uniform hypergraphs with positive density and upper density at most. This result is sharp.
登录
查看更多内容
图的可归纳性
DOI：
10.1016/0095-8956(75)90084-2
发表时间：
1975
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
N. Pippenger;M. Golumbic
通讯作者：
M. Golumbic
三色图中的彩虹三角形
DOI：
10.1016/j.jctb.2017.04.002
发表时间：
2014
期刊：
J. Comb. Theory B
影响因子：
--
作者：
J. Balogh;Ping Hu;Bernard Lidický;Florian Pfender;Jan Volec;Michael Young
通讯作者：
Michael Young
DOI：
10.1007/978-0-8176-8092-3
发表时间：
2021-06
期刊：
Complexity of Infinite-Domain Constraint Satisfaction
影响因子：
--
作者：
Lane Barton
通讯作者：
Lane Barton
关于几乎所有图的精确最大诱导密度及其诱导性
DOI：
10.1016/j.jctb.2018.09.005
发表时间：
2018
期刊：
J. Comb. Theory B
影响因子：
--
作者：
R. Yuster
通讯作者：
R. Yuster
诱导 5 循环的最大密度是通过 5 循环的迭代吹胀实现的
DOI：
10.1016/j.ejc.2015.08.006
发表时间：
2014
期刊：
Eur. J. Comb.
影响因子：
--
作者：
J. Balogh;Ping Hu;Bernard Lidický;Florian Pfender
通讯作者：
Florian Pfender