Ramsey non-goodness involving books
Ramsey non-goodness involving books
复制标题
DOI：
10.1016/j.jcta.2023.105780
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Chunchao Fan;Qizhong Lin
中科院分区：
文献类型：
--
作者：
Chunchao Fan;Qizhong Lin
摘要 1983年，Burr和Erdős开始了拉姆齐善良问题的研究。 Nikiforov 和 Rousseau (2009) 解决了 Burr 和 Erdős 提出的几乎所有善良问题，其中参数的界限是塔型的，因为他们的证明依赖于正则引理。令 B k, n 为 n 个顶点上的书籍图，由 K k+ 1 的 n− k 个副本组成，所有副本共享一个共同的 K k，并令 H= K p (a 1,…, a p) 为完整的 p 分图，部分大小为 a 1,…, a p。最近，为了避免使用正则引理，Fox、He 和 Wigderson（2023）重新审视了涉及书籍的一些拉姆齐善良结果。他们评论说，看看人们能将这些想法推向多远，这将是一件非常有趣的事情。特别是，他们推测对于所有整数 k、p、t≥ 2，存在一些 δ> 0，使得对于所有 n≥ 1、1≤ a 1≤⋯≤ a p− 1≤ t 和 a p≤ δ n，我们有 r (H, B k, n)=(p− 1)(n− 1)+ d k (n, Ka 1, a 2)+ 1，其中 d k (n, Ka 1，a 2) 是存在 (n+ d− 1) 顶点 K a 1 的最大 d，这是一个 2 无图，其中最多有 k− 1 个顶点的度数小于 d。当 a 1= a 2= 1 时，他们验证了猜想。我们反驳了 Fox 等人（2023）的猜想。在 Fox 等人的工作的基础上，我们迈出了实质性的一步，表明对于每个 k、p、t≥ 2，都存在 δ> 0，使得以下内容适用于所有大 n。令 1≤ a 1≤…≤ a p− 1≤ t 和 a p≤ δ n 为正整数。如果 a 1= 1，则 r (H, B k, n)≤(p− 1)(n− 1)+ k (p− 1)(a 2− 1)+ 1。如果 a 2|(n− 1− k)，则不等式是紧的。此外，我们证明，对于每个 k、a≥ 1 和 p≥ 2，存在 δ> 0，使得对于所有大 n 且 b≤ δ ln n, r (K p (1, a, b,…, b), B k, n)=(p− 1)(n− 1)+ k (p− 1)(a− 1)+ 1 如果 a|(n− 1− k)，其中 a= 1 时的情况为Nikiforov 和 Rousseau (2009) 使用正则引理证明了这一点。我们获得的 1/δ 的界限不是塔型的，因为我们的证明不依赖于正则引理。
Abstract In 1983, Burr and Erdős initiated the study of Ramsey goodness problems. Nikiforov and Rousseau (2009) resolved almost all goodness questions raised by Burr and Erdős, in which the bounds on the parameters are of tower type since their proofs rely on the regularity lemma. Let B k, n be the book graph on n vertices which consists of n− k copies of K k+ 1 all sharing a common K k, and let H= K p (a 1,…, a p) be the complete p-partite graph with parts of sizes a 1,…, a p. Recently, avoiding use of the regularity lemma, Fox, He and Wigderson (2023) revisit several Ramsey goodness results involving books. They comment that it would be very interesting to see how far one can push these ideas. In particular, they conjecture that for all integers k, p, t≥ 2, there exists some δ> 0 such that for all n≥ 1, 1≤ a 1≤⋯≤ a p− 1≤ t and a p≤ δ n, we have r (H, B k, n)=(p− 1)(n− 1)+ d k (n, K a 1, a 2)+ 1, where d k (n, K a 1, a 2) is the maximum d for which there is an (n+ d− 1)-vertex K a 1, a 2-free graph in which at most k− 1 vertices have degree less than d. They verify the conjecture when a 1= a 2= 1. We disprove the conjecture of Fox et al.(2023). Building upon the work of Fox et al., we make a substantial step by showing that for every k, p, t≥ 2, there exists δ> 0 such that the following holds for all large n. Let 1≤ a 1≤…≤ a p− 1≤ t and a p≤ δ n be positive integers. If a 1= 1, then r (H, B k, n)≤(p− 1)(n− 1)+ k (p− 1)(a 2− 1)+ 1. The inequality is tight if a 2|(n− 1− k). Moreover, we prove that for every k, a≥ 1 and p≥ 2, there exists δ> 0 such that for all large n and b≤ δ ln n, r (K p (1, a, b,…, b), B k, n)=(p− 1)(n− 1)+ k (p− 1)(a− 1)+ 1 if a|(n− 1− k), where the case when a= 1 has been proved by Nikiforov and Rousseau (2009) using the regularity lemma. The bounds on 1/δ we obtain are not of tower-type since our proofs do not rely on the regularity lemma.