On the connectivity of random subsets of projective spaces
type: Item
instance of: scholarly article
title: On the connectivity of random subsets of projective spaces
zbMATH Open document ID: 0939.51012
DOI: 10.1016/S0012-365X(98)00201-5
author: Wojciech Kordecki
author: Tomasz Łuczak
published in: Discrete Mathematics
publication date: 2000-07-02T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 51E20
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05B25
zbMATH DE Number: 1321776
zbMATH Keywords: random subsets
zbMATH Keywords: connectivity
zbMATH Keywords: matroid
reviewed by: Antonio Cossidente
MaRDI profile type: Publication
cites work: Q3682518
cites work: Q3715148
cites work: On the strength of connectedness of a random graph
cites work: Q3851217
cites work: Asymptotic properties of random subsets of projective spaces
cites work: On random subsets of projective spaces
cites work: Cycles in random graphs
cites work: Q3135082
cites work: Q4111952
description: scientific article; zbMATH DE number 1321776