Lower bounds for r2(K1+G) and r3(K1+G) from Paley graph and generalization
Lower bounds for r2(K1+G) and r3(K1+G) from Paley graph and generalization
复制标题
DOI：
10.1016/j.ejc.2014.02.007
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Qizhong Lin;Yusheng Li;Jian Shen
中科院分区：
文献类型：
--
作者：
Qizhong Lin;Yusheng Li;Jian Shen
设q ∈ 1（mod 4）是素数幂，Pq是q阶Paley图.证明了若Pq不含G的拷贝，其中δ（G）≥ 1，则r2（K1 + G）≥ 2 q+ 1.特别地，如果4 n+ 1是素数幂，则r2（K3 + K <$n）≥ 8 n+ 3。进一步地，将Paley图Pq（q= 1（mod 6））推广到H 0（q），H1（q）和H2（q），它们是（q− 1）/3-正则的，彼此同构，构成Kq的边染色.证明了若H 0（q）不含G的拷贝且δ（G）≥ 1，则r3（K1 + G）≥ 3q + 1.此外，H 0（q）中的每对相邻顶点具有相同数量的公共邻居。我们将对许多H 0（p）计算这个数，其中p是一个素数，以方便算法。每一个计算数据都给出了一些三色Ramsey数的下界。
Abstract Let q≡ 1 (mod 4) be a prime power and P q the Paley graph of order q. It is shown that if P q contains no copy of G, where δ (G)≥ 1, then r 2 (K 1+ G)≥ 2 q+ 1. In particular, if 4 n+ 1 is a prime power, then r 2 (K 3+ K¯ n)≥ 8 n+ 3. Furthermore, the Paley graph P q for q= 1 (mod 6) is generalized to H 0 (q), H 1 (q) and H 2 (q), which are (q− 1)/3-regular, isomorphic to each other and form an edge-coloring of K q. It is shown that if H 0 (q) contains no copy of G with δ (G)≥ 1, then r 3 (K 1+ G)≥ 3 q+ 1. Also, each pair of adjacent vertices in H 0 (q) has the same number of common neighbors. We shall compute this number for many H 0 (p), where p is a prime for convenience of the algorithm. Each of computing data gives lower bounds for some three-color Ramsey numbers.