Pure and Applied Mathematics Quarterly

Volume 18 (2022)

Number 6

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

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a9

Authors

Qizhong Lin (Center for Discrete Mathematics, Fuzhou University, Fuzhou, China)

Yusheng Li (School of Mathematics, Tongji University, Shanghai, China)

Abstract

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).

Keywords

Ramsey number, quasi-randomness, Weil bound

2010 Mathematics Subject Classification

05D10

Full Text (PDF format)

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