Pure and Applied Mathematics Quarterly
Volume 18 (2022)
Special issue in honor of Fan Chung
Guest editors: Paul Horn, Yong Lin, and Linyuan Lu
Quasi-random graphs of given density and Ramsey numbers
Pages: 2537 – 2549
A cornerstone contribution due to Chung, Graham and Wilson (1989) implies that many graph properties of different nature are equivalent. Graphs that satisfy any (and thus all) of the properties are called quasi-random graphs. In this paper, we construct families of quasi-random graphs for any given edge density, which are regular but not strongly regular. Moreover, we obtain a lower bound for Ramsey number $r (K_1 + G)$ in which the graph $G$ contains no isolated vertex, which extends a classical result by Shearer (1986) and independently Mathon (1987).
Ramsey number, quasi-randomness, Weil bound
2010 Mathematics Subject Classification
In honor of Professor Fan Chung on the occasion of “the Conference on Graph Theory and its Applications: a Tribute to Professor Fan Chung”.
Qizhong was supported in part by NSFC (No. 12171088, 12226401) and NSFFJ (No. 2022J02018).
Yusheng Li was supported in part by NSFC (No. 11931002, 11871377).
Received 2 March 2021
Received revised 28 February 2022
Accepted 24 March 2022
Published 29 March 2023