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

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the connectivity of random subsets of projective spaces
scientific article

    Statements

    On the connectivity of random subsets of projective spaces (English)
    0 references
    0 references
    0 references
    2 July 2000
    0 references
    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)\).
    0 references
    random subsets
    0 references
    connectivity
    0 references
    matroid
    0 references

    Identifiers