|
NeuroCOLT
Technical Report NC-TR-95-025
The Vapnik-Chervonenkis
Dimension of a Random Graph
Martin
Anthony and Graham Brightwell
London School of Economics and Political Science
University of London
Colin
Cooper
University of North London
Abstract
In this paper we investigate a parameter defined for any graph, known
as the Vapnik-Chervonenkis dimension (or VC dimension).
For any vertex $x$ of a graph $G$, the closed neighbourhood $N(x)$
of $x$ is the set of all vertices of $G$ adjacent to $x$, together
with $x$. We say that a set $D$ of vertices of $G$ is shattered
if every subset $R$ of $D$ can be realised as $R=D \cap N(x)$ for
some vertex $x$ of $G$. The Vapnik-Chervonenkis dimension of $G$ is
defined to be the largest cardinality of a shattered set of vertices.
This parameter can be used to provide bounds on the complexity of
a learning problem on graphs. Our main result gives, for each positive
integer $d$, the exact threshold function for a random graph $G(n,p)$
to have VC~dimension $d$.
Download Compressed
Postscript
|