2015/02/04 by Dhruv Mubayi, Mubayi, Dhruv, Caroline Terry +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #math.CO #math.LO
paper · pdf · doi:10.48550/arxiv.1502.01212
arxiv created 2015/02/09 · arxiv updated 2015/02/10
Fix an integer r≥ 3. We consider metric spaces on n points such that the distance between any two points lies in \1,..., r\. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is \lceil (r+1)/(2)\rceil ^n\choose 2 + o(n2). Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij. When r is even, our structural characterization is more precise, and implies that almost all such metric spaces have all distances at least r/2. As an easy consequence, when r is even we improve the error term above from o(n2) to o(1), and also show a labeled first-order 0-1 law in the language Lr, consisting of r binary relations, one for each element of [r]. In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in \r/2,..., r\. Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws.