Quasi-randomness and the distribution of copies of a fixed graph |
| |
Authors: | Asaf Shapira |
| |
Affiliation: | (1) Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA |
| |
Abstract: | We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices. |
| |
Keywords: | KeywordHeading" >Mathematics Subject Classification (2000) 05C80 05C35 |
本文献已被 SpringerLink 等数据库收录! |
|