Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-18T02:19:51.238Z Has data issue: false hasContentIssue false

DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS

Published online by Cambridge University Press:  19 August 2019

DHRUV MUBAYI
Affiliation:
DEPARTMENT OF MATHEMATICS, STATISTICS, AND COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT CHICAGO 851 S MORGAN STREET CHICAGO, IL60607, USA E-mail: mubayi@uic.edu
CAROLINE TERRY
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CHICAGO 5734 S UNIVERSITY AVENUE CHICAGO, IL60637, USA E-mail: caterry@uchicago.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Fix an integer $r \ge 3$. We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots ,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left( {\matrix{ n\cr2\cr} } \right) + o\left( {n^2 } \right)} .$

Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. 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\left( {n^2 } \right)$ to $o\left( 1 \right)$, and also show a labeled first-order 0-1 law in the language ${\cal L}_r $, 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 $\left\{ {r/2, \ldots ,r} \right\}$.

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.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2019