On the connectivity of random subsets of projective spaces (Q1297410)

Let \(PG(r-1,q)\) be the projective space of dimension \(r-1\) over the Galois field \(GF(q)\). Let \(S\) be a subset of points of \(PG(r-1,q)\). The subset \(S\) is said to be independent if it spans a subspace of dimension \(|S|-1\). If \(T\) is any subset of points of \(PG(r-1,q)\), the rank \(\rho (T)\) of \(T\) is the size of the largest independent set contained in \(T\). The pair \((PG(r-1,q), \rho)\) can be viewed as a matroid and so it is natural to consider the connectivity of subsets of \(PG(r-1,q)\). A subset \(T\) of \(PG(r-1,q)\) such that \(\rho (T) =r\) is said to be \(k\)-separable for \(k\geq 1\) if there exists a separator \(S\subseteq T\) such that \(|S|\leq k\) and \(\rho (T\setminus S)<r\). If \(k\geq 2\) and \(T\) is not \(k-1\)-separable then \(T\) is said to be \(k\)-connected. The main result in the paper under review is that with probability tending to one as \(r\) tends to infinity, a random subset \({\omega}_ r(n)\) of cardinality \(n\) of \(PG(r-1,q)\) becomes \(k\)-connected when \( n=r+(k-1)\log _q(r) + O(1)\).