Department of

April 2015 May 2015 June 2015 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 1 2 1 2 3 4 5 6 5 6 7 8 9 10 11 3 4 5 6 7 8 9 7 8 9 10 11 12 13 12 13 14 15 16 17 18 10 11 12 13 14 15 16 14 15 16 17 18 19 20 19 20 21 22 23 24 25 17 18 19 20 21 22 23 21 22 23 24 25 26 27 26 27 28 29 30 24 25 26 27 28 29 30 28 29 30 31

Monday, May 11, 2015

**Abstract:** In this talk we give an overview of some examples of logical zero-one laws, all of which are consequences of theorems in extremal combinatorics characterizing the asymptotic structure of families of finite graphs. We then present a new example of a logical zero-one law which also relies on techniques from extremal combinatorics for its proof. In particular, given integers $r,n\geq 3$, define $M_r(n)$ to be the set of metric spaces with underlying set $\{1,\ldots, n\}$ and with distances in $\{1,\ldots, r\}$. We present results describing the approximate structure of these metric spaces when$r$ is fixed and $n$ is large. As consequences of these structural results, we obtain an asymptotic enumeration for $M_r(n)$, and in the case when $r$ is even, a logical zero-one law. This is joint work with Dhruv Mubayi.