Ramsey Numbers of Books and Quasirandomness
Ramsey Numbers of Books and Quasirandomness
复制标题
DOI：
10.1007/s00493-021-4409-9
复制
发表时间：
2020-01
期刊：
影响因子：
1.1
通讯作者：
D. Conlon;J. Fox;Yuval Wigderson
中科院分区：
文献类型：
--
作者：
D. Conlon;J. Fox;Yuval Wigderson
图书图由n个Kk +1的拷贝沿沿着一个公共Kk连接而成。已知的拉姆齐数与集团的经典拉姆齐数有很强的联系。最近，第一作者确定了这些Ramsey数的渐近阶为fixedk，从而回答了一个老问题的Erdés，Faudree，Rousseau，和Schelp。在本文中，我们首先提供了一个简单的证明这个定理。接下来，回答第一作者的一个问题，我们提出了一个不同的证明，避免使用Szemerédi的正则引理，从而提供更严格的控制误差项。最后，我们证明了一个猜想Nikiforov，卢梭和Schelp证明，所有极值着色这个拉姆齐问题是拟随机的。
Thebook graphconsists ofncopies ofKk+1joined along a commonKk. The Ramsey numbers ofare known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixedk, thus answering an old question of Erdős, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemerédi’s regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom.