2021/08/25 by Li, Tianyu, Lin, Qizhong, Peng, Xing
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.11201
A book Bn is a graph which consists of n triangles sharing a common edge. In this paper, we study Ramsey numbers of quadrilateral versus books. Previous results give the exact value of r(C4,Bn) for 1≤ n≤ 14. We aim to show the exact value of r(C4,Bn) for infinitely many n. To achieve this, we first prove that r(C4,B(m-1)2+(t-2))≤ m2+t for m≥4 and 0 ≤ t ≤ m-1. This improves upon a result by Faudree, Rousseau and Sheehan (1978) which states that r(C4,Bn)≤ g(g(n)), where g(n)=n+\lfloor√(n-1)\rfloor+2. Combining the new upper bound and constructions of C4-free graphs, we are able to determine the exact value of r(C4,Bn) for infinitely many n. As a special case, we show r(C4,Bq2-q-2) = q2+q-1 for all prime power q≥4.