The Vapnik-Chervonenkis dimension of a random graph (Q1842142)

A set \(D\) of vertices in a graph \(G\) is shattered if for each subset \(R\) of \(D\) there is a vertex \(v\) such that the closed neighbourhood of \(v\) intersects \(D\) exactly in \(R\). The Vapnik-Chervonenkis dimension of \(G\) is the maximum size of a shattered set of vertices. For each fixed positive integer \(d\), the exact threshold function is given for a random graph \(G(n, p)\) to have dimension at least \(d\). This turns out to be about \(n^{- 1/d}\) for large \(d\). The case of \(d\) going to \(\infty\) slowly with \(n\) is also considered.