Combinatorics Seminar

When: Sunday, December 28, 10am Where: Schreiber 309 Speaker: Dan Hefetz, University of Birmingham Title: Universality of graphs with few triangles and anti-triangles

Abstract:

In this talk we will discuss 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 G(n,1/2) is, in particular, 3-random-like, this can be viewed as a weak version of quasirandomness. 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. We then show that for larger subgraphs, 3-random-like sequences demonstrate a completely different behaviour. We show that for every graph H on n≥13 vertices there exist 3-random-like graphs without an induced copy of H. Moreover, we show that for every ℓ there are 3-random-like graphs which are ℓ-universal but not m-universal when m is sufficiently large compared to ℓ.

Based on joint work with Mykhaylo Tyomkyn.