Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
| dc.creator | Yuster, Raphael | |
| dc.date | 2008-04-04 | |
| dc.date.accessioned | 2026-07-07T09:30:30Z | |
| dc.date.available | 2026-07-07T09:30:30Z | |
| dc.description | For every fixed graph $H$ and every fixed $0 < α< 1$, we show that if a graph $G$ has the property that all subsets of size $αn$ contain the ``correct'' number of copies of $H$ one would expect to find in the random graph $G(n,p)$ then $G$ behaves like the random graph $G(n,p)$; that is, it is $p$-quasi-random in the sense of Chung, Graham, and Wilson. This solves a conjecture raised by Shapira and solves in a strong sense an open problem of Simonovits and Sós. | |
| dc.description | 7 pages | |
| dc.identifier | https://arxiv.org/abs/0804.0753 | |
| dc.identifier | http://arxiv.org/abs/0804.0753 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158141 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80 | |
| dc.title | Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets | |
| dc.type | text |