tag:blogger.com,1999:blog-6555947.post2900514340494388961..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Metric spaces, VC-dimension, and metric entropy.Suresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6555947.post-6107204083206323772009-06-06T04:26:50.184-06:002009-06-06T04:26:50.184-06:00thanks ! that's very interesting...thanks ! that's very interesting...Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-30800786582987448532009-06-05T16:38:40.627-06:002009-06-05T16:38:40.627-06:00This is a very interesting question. In the rando...This is a very interesting question. In the random graph, with distance understood as graph distance, the balls of radius e would have infinite VC dimension for every e. On the other hand, for any metric definable in an o-minimal structure, the balls of radius e would have finite VC dimension for every e. You could go further and say that in any metric structure which is NIP (not the independence property) the balls of radius e will have finite VC dimension for every e. Unfortunately this is a bit tautologous, because NIP structures are precisely those in which all formulas have finite VC dimension.<br /><br />The challenge seems to be to relate the NIP condition to an ordinary classification characteristic of metric spaces. Looking at the wikipedia entry for Metric Space I see no promising properties. The usual labels of Separable, Connected, Compact, etc seem to be irrelevant. <br /><br /> Actually, I notice that in the random graph, all points are distance 0,1, or 2 apart. This may be relevant. <br /><br />It is worth noting that this question is equivalent to the question: For which metric spaces does the set of e balls have finite independence dimension? <br /><br />A simpler question to consider asking first is: what graphs, with distance understood as graph distance, have this property? <br /><br />In mathematical logic the idea of NIP is taken somewhat as a primitive. It is not known to be reducible to other seemingly orthogonal properties. One might consider reading Hans Adler's nice summary of what is known about equivalent conditions for NIP. <br /><br />A promising hunting ground seems to be new work in continuous logic, which is inherently metric. See the following for an overview: http://www.aimath.org/~skrantz/Blurbs/model.htmlsevenfactorialhttp://www.blogger.com/profile/15282594159814479813noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-76733868113422163622008-02-13T06:56:00.000-07:002008-02-13T06:56:00.000-07:00I had always thought that "metric entropy" was by ...I had always thought that "metric entropy" was by analogy to the Boltzmann entropy in statistical mechanics, which is the log of the number of microstates compatible with a given macroscopic state. (This actually predates the Gibbs-Shannon entropy.)Cosmahttp://bactra.org/weblog/noreply@blogger.com