Abstract.
We say that a family of graphs 
is p-quasi-random, 0<p<1, if it shares typical properties of the random graph G(n,p); for a definition, see below. We denote by 
the class of all graphs H for which 
and the number of not necessarily induced labeled copies of H in G
n
is at most (1+o(1))p
e(H)
n
v(H) imply that 
is p-quasi-random. In this note, we show that all complete bipartite graphs K
a,b
, a,b≥2, belong to for all 0<p<1.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Additional information
Acknowledgments We would like to thank Andrew Thomason for fruitful discussions and Yoshi Kohayakawa for organizing Extended Workshop on Combinatorics in eq5 Paulo, Ubatuba, and Rio de Janeiro, where a part of this work was done. We also thank the referees for their careful work.
The first author was partially supported by NSF grant INT-0072064
The second author was partially supported by NSF grants DMS-9970622, DMS-0301228 and INT-0072064
Final version received: October 24, 2003
Rights and permissions
About this article
Cite this article
Skokan, J., Thoma, L. Bipartite Subgraphs and Quasi-Randomness. Graphs and Combinatorics 20, 255–262 (2004). https://doi.org/10.1007/s00373-004-0556-1
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00373-004-0556-1