✦ LIBER ✦

The vapnik-chervonenkis dimension of a random graph

✍ Scribed by Martin Anthony; Graham Brightwell; Colin Cooper

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 652 KB
Volume: 138
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00187-n

No coin nor oath required. For personal study only.

✦ Synopsis

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 = Dc~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.

📜 SIMILAR VOLUMES

The Vapnik-Chervonenkis dimension of dec

The Vapnik-Chervonenkis dimension of decision trees with bounded rank

✍ Hans Ulrich Simon 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 599 KB

The rotational dimension of a graph

✍ Frank Göring; Christoph Helmberg; Markus Wappler 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

The circular dimension of a graph

✍ Robert B. Feinberg 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 484 KB

A graph is a pair (V, I), V being the vertices and I being the relation of adjacency on V. Given a grqh G, then a collection of functions (fi}~ ,, each fi mapping each vertex of V into an arc on a fixed circle, is said to define an m-arc intersection model for G if for all x, y E V, xly e=, (Vi~ml(f

The frame dimension and the complete ove

The frame dimension and the complete overlap dimension of a graph

✍ Jeffrey E. Steif 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 715 KB

Roberts (F. S. Roberts, On the boxicity and cubicity of a graph. In Recent Progress in Cornbinarorics, W. T. Tutte, ed. Academic, New York (1 969)), studied the intersection graphs of closed boxes (products of closed intervals) in Euclidean n-space, and introduced the concept of the boxicity of a gr

The divider dimension of the graph of a

The divider dimension of the graph of a function

✍ Steven R Dunbar; Rod W Douglass; W.J Camp 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 483 KB

On the euclidean dimension of a complete

On the euclidean dimension of a complete multipartite graph

✍ Hiroshi Maehara 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 272 KB

The euclidean dimension of a graph G, e(G), is the minimum n such that the vertices of G can be placed in euclidean n-space, R", in such a way that adjacent vertices have distance 1 and nonadjacent vertices have distances other than 1. Let G = K(n,, . , ns+,+J be a complete (s + t + u)-partite graph