Bipartite subgraphs and quasi-randomness
type: Item
instance of: scholarly article
title: Bipartite subgraphs and quasi-randomness
zbMATH Open document ID: 1054.05091
author: J. Skokan
author: Luboš Thoma
published in: Graphs and Combinatorics
publication date: 2004-12-13T00:00:00Z
review text: The concept of a pseudo-random graph is now firmly established as a useful one in combinatorics and theoretical computer science. The essential idea is that such a graph should have the properties of a typical random graph \(G(n,p)\) with the same density of edges. Various attempts have been made to formalise this notion: one of these was in \textit{F. R. K. Chung, R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, 345--362 (1989; Zbl 0715.05057)] where a graph \(G\) on \(n\) vertices satisfying any of several equivalent properties was said to be \(p\)-quasi-random (here \(0<p<1\) is fixed). One of the equivalent properties was that the number of copies of a fixed graph \(H\) in \(G\) should be \((1+o(1))\) times the expected number of copies of \(H\) in a random graph \(G(n,p)\) on \(n\) labelled vertices, where each edge arises with probability \(p\) independent of all other edges. Here \(n\rightarrow\infty\) with \(| H|\) fixed. In the paper under review, the authors consider for which graphs \(H\) on \(t\) vertices the following property is equivalent to \(p\)-quasi-randomness: the number of edges is \(\geq (1+o(1))p{n\choose 2}\) and the number of (not necessarily induced) copies of \(H\) in \(G\) is \(\leq (1+o(1))p^{e(H)}n^{t}\). Here \(e(H)\) denotes the number of edges of \(H\). The class of all \(H\) for which this property does indeed imply that \(G\) is \(p\)-quasi random is denoted by \({\mathcal L}_{w}(p)\). The naive hope might be, in the light of the result in the first paragraph, that all graphs are in \({\mathcal L}_{w}(p)\). However it has been known for some time -- see, e.g., the paper of Chung et al. above -- that odd cycles are an infinite family of counterexamples. One easy way to see this is to consider a random graph where each vertex independently is coloured red or blue (equally probably), and then edges from red vertices to blue vertices arise with probability \(2p\) and those between vertices of the same colour arise with probabi…
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 2121764
zbMATH Keywords: pseudorandom graph
zbMATH Keywords: bipartite graph
reviewed by: David B. Penman
MaRDI profile type: Publication
full work available at URL: s00373-004-0556-1
OpenAlex ID: W2094884500
DOI: 10.1007/S00373-004-0556-1
description: scientific article; zbMATH DE number 2121764