Name
Abstract | ||
|---|---|---|
In this paper we investigate a parameter defined for any graph, known as the Vapnik Chervonenkis dimension (VC dimension). For any vertex x of a graph G , the closed neighborhood 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 ∩ N ( x ) for some vertex x of G . The VC dimension of G is defined to be the largest cardinality of a shattered set of vertices. 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 . |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0012-365X(94)00187-N | Discrete Mathematics |
Keywords | Field | DocType |
random graph,vapnik-chervonenkis dimension,vc dimension | Wheel graph,Discrete mathematics,Combinatorics,VC dimension,Bound graph,Graph power,Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
138 | 1 | Discrete Mathematics |
Citations | PageRank | References |
8 | 0.83 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Anthony | 1 | 329 | 141.99 |
| Graham Brightwell | 2 | 306 | 37.33 |
| Colin Cooper | 3 | 287 | 30.73 |