| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6423939 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
The notion of forcing pairs is located in the study of quasi-random graphs. Roughly speaking, a pair of graphs (F,Fâ²) is called forcing if the following holds: suppose for a sequence of graphs (Gn) there is a p>0 such that the number of copies of F and the number of copies of Fâ² in every graph Gn of the sequence (Gn) is approximately the same as the expected value in the random graph G(n,p), then the sequence of graphs (Gn) is quasi-random in the sense of Chung, Graham and Wilson. We describe a construction which, given any graph F with at least one edge, yields a graph Fâ² such that (F,Fâ²) forms a forcing pair.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hiệp Hà n, Yury Person, Mathias Schacht,