Bipartite subgraphs and quasi-randomness (Q1889833)

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 probability \(0\). Then, when the colours are hidden, the overall probability any edge arises is easily seen to be \(p\), so that there are indeed likely to be \((1+o(1))p{n\choose 2}\) edges: but of course the graph is bipartite, so the number of odd cycles is 0, much less than its expected value. However this graph is not a \(p\)-quasi random: for example, it (typically) has far more \(4\)-cycles than a random graph \(G(n,p)\). However it was noted in the work of Chung et al. that even cycles and complete bipartite graphs \(K_{2,t}\) are in \({\mathcal L}_{w}(p)\). In the paper under review, the main result is that complete bipartite graphs \(K_{a,b}\) are in \({\mathcal L}_{w}(p)\) for all \(a,b\geq 2\) and \(0<p<1\). For the proof, we first need a variant of Jensen's inequality, which says (crudely speaking) that if Jensen's inequality \[ \frac{\sum_{i=1}^{n}a_{i}^{k}}{n}\geq \left(\frac{a_{1}+\cdots+ a_{n}}{n}\right)^{k} \] is close to being an equality, then almost all \(a_{i}\)s are very close to the average of the \(a_{i}\)s. More precisely, it is shown that if \(0<\delta<1\) and \(k\geq 2\), there is \(\varepsilon >0\) and \(A_{k}>0\) such that, for non-negative reals \(a_{1},a_{2},\ldots a_{n},a\) with \(a_{i}>A_{k}\) for all \(i\) and \(a>A_{k}\), if \(\sum_{i=1}^{n}a_{i}\geq (1-\varepsilon)na\) and \(\sum_{i=1}^{n}{a_{i}\choose k}<(1+\varepsilon)n{a\choose k}\), we have \[ | \{i:\,| a-a_{i}| <\delta a\}|>(1-\delta)n. \] To complete the (sketch) proof, we now \` tidy up locally\'\ so that, for any set \(S_{a}\) of \(a\) vertices, there are \(\geq A_{a}\) vertices adjacent to every vertex of \(S_{a}\), where \(A_{a}\) is as above. (This can be done by adding at most \(o(n^{2})\) edges, so does not affect the quasi-randomness.) Hence, as the number of (not necessarily induced) copies of \(K_{a,b}\) in \(G\) is \[ \sum_{X\in [V(G)]^{a}}a!b!{{\text{ deg}_{G}(X)}\choose b}, \] Jensen's inequality and the fact that \(e(G)\geq (1+o(1))p{n\choose 2}\) yield that the number of copies of \(K_{a,b}\) \textit{equals} \((1+o(1))p^{ab}n^{a+b}\). The lemma of the previous paragraph now implies most \(X\in [V(G)]^{a}\) have \((1+o(1))p^{a}n\) neighbours. Further use of the same sorts of tricks shows that any \(2a\) vertices have about \((1+o(1))p^{2a}n\) neighbours: now one of the equivalent definitions of \(p\)-quasi randomness yields the result. The authors close by remarking that they are not aware of a bipartite graph \(H\) (with at least one cycle) which is not in \({\mathcal L}_{w}(p)\). This question appears to be related to a (seemingly deep) conjecture of \textit{A. F. Sidorenko} [Bolyai Soc. Math. Stud. 3, 423--455 (1994; Zbl 0832.05062)], and a conjecture of the reviewer (in a submitted paper) about models of random graphs like those described in the second paragraph. This topic appears to be difficult at present. The authors also show that the analogues of their theorem for \textit{induced} subgraphs are false: this is a familiar problem in this area, see e.g. \textit{M. Simonovits} and \textit{V. T. Sós} [Combinatorica 17, 577--596 (1997; Zbl 0906.05066)].