Quasi-randomness and the distribution of copies of a fixed graph
type: Item
instance of: scholarly article
title: Quasi-randomness and the distribution of copies of a fixed graph
zbMATH Open document ID: 1196.05090
author: Asaf Shapira
published in: Combinatorica
publication date: 2009-12-28T00:00:00Z
review text: 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.
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5651823
zbMATH Keywords: quasi-random
zbMATH Keywords: subgraphs
MaRDI profile type: Publication
full work available at URL: s00493-008-2375-0
OpenAlex ID: W1981155052
cites work: A note on the ranks of set-inclusion matrices
cites work: Quasi-Random Set Systems
cites work: Quasi-random tournaments
cites work: Quasi-random hypergraphs
cites work: Quasi-random graphs
cites work: A Certain Class of Incidence Matrices
cites work: Quasirandom Groups
cites work: Generalized quasirandom graphs
cites work: Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
cites work: Q3825110
cites work: A diagonal form for the incidence matrices of \(t\)-subsets vs. \(k\)- subsets
DOI: 10.1007/S00493-008-2375-0
Recommended article: Quasirandomness in Graphs
Recommended article: Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
Recommended article: Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets
Recommended article: Quasi-random graphs
Recommended article: Quasirandomness in hypergraphs
Recommended article: Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions
Recommended article: Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
description: scientific article; zbMATH DE number 5651823