Quasi-randomness and the distribution of copies of a fixed graph (Q1046741): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:00, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Quasi-randomness and the distribution of copies of a fixed graph |
scientific article |
Statements
Quasi-randomness and the distribution of copies of a fixed graph (English)
0 references
28 December 2009
0 references
The notion of quasi-randomness is due to \textit{A. Thomason} [Surveys in combinatorics 1987, Pap. 11th Br. Combin. Conf., London/Engl. 1987, Lond. Math. Soc. Lect. Note Ser. 123, 173--195 (1987; Zbl 0672.05068)]. By the subsequent work of \textit{F. R. K. Chung, R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, No. 4, 345--362 (1989; Zbl 0715.05057)] it turned out that a sequence of graphs is quasi-random if it exhibits some behavior of random graph properties asymptotically, and in fact a number of equivalent properties ensure this. For graphs \(H\) and \(G\) and \(U \subset V(G)\), let \(H(U)\) be the number of labeled copies of \(H\) spanned by \(U\). Two properties that Chung et al gave were \({\mathcal P}_1(t)\) and \({\mathcal P}_2\). \textit{M. Simonovits} and \textit{V. T. Sós} [Combinatorica 17, No. 4, 577--596 (1997; Zbl 0906.05066)] gave a different notion, which allowed a generalization of these results. For a fixed graph \(H\) on \(h\) vertices, the sequence \(G_n\) has the property \({\mathcal P}_H\) if (1) \(H(U)=p^{e(H)}| U| ^h+o(n^h)\) for all \(U \subset V(G_n)\). They showed that for any fixed \(H\) with \(e(H) >0\), property \(\mathcal P_H\) is quasi-random. However, it was left open if one really needs the property \({\mathcal P}_H\) for all \(U \subset V(G_n)\), and they asked if less assumptions on \(U\) was enough for quasi-randomness. The author of this paper shows that the quasi-randomness of a sequence \(G_n\) follows if for a fixed, non-empty graph \(H\) (1) holds for \(U \subset V(G_n)\), \(| U| =\lfloor n/(h+1) \rfloor\), where \(h=| V(H)| \). The proof utilizes simple counting arguments and an old result of \textit{D. H. Gottlieb} [Proc. Am. Math. Soc. 17, 1233--1237 (1966; Zbl 0146.01302)] on the rank of incidence matrices.
0 references
quasi-random
0 references
subgraphs
0 references