Universality of graphs with few triangles and anti-triangles

Journal article

We study 3-random-like graphs, that is, sequences of graphs in which the densities of triangles and anti-triangles converge to 1/8. Since the random graph n,1/2 is, in particular, 3-random-like, this can be viewed as a weak version of quasi-randomness. We first show that 3-random-like graphs are 4-universal, that is, they contain induced copies of all 4-vertex graphs. This settles a question of Linial and Morgenstern [10]. We then show that for larger subgraphs, 3-random-like sequences demonstrate completely different behaviour. We prove that for every graph H on n ⩾ 13 vertices there exist 3-random-like graphs without an induced copy of H. Moreover, we prove that for every ℓ there are 3-random-like graphs which are ℓ-universal but not m-universal when m is sufficiently large compared to ℓ.

Authors: Hefetz, D; Tyomkyn, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Combinatorics, Probability and Computing
• Volume: 25
• Issue: 4
• Pages: 560-576
• Publication date: 2015-07-29
• Acceptance date: 2015-01-19
• DOI: 10.1017/S0963548315000188
• EISSN: 1469-2163
• ISSN: 0963-5483
• Language: English