zbMATH — the first resource for mathematics

On the connectivity of random subsets of projective spaces. (English) Zbl 0939.51012
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)\).

51E20 Combinatorial structures in finite projective spaces
05B35 Combinatorial aspects of matroids and geometric lattices
05B25 Combinatorial aspects of finite geometries
Full Text: DOI
[1] Bollobás, B., Random graphs, (1985), Academic Press London · Zbl 0567.05042
[2] Bollobaś, B.; Thomason, A., Random graphs of small order, Ann. discrete math., 28, 47-97, (1995)
[3] Erdös, P.; Rényi, A., On the strength of connectedness of a random graph, Acta math. acad. sci. hung., 12, 261-267, (1961) · Zbl 0103.16302
[4] Hirschfeld, J.W.P., Projective geometries over finite fields, (1979), Clarendon Press Oxford · Zbl 0418.51002
[5] Kelly, D.G.; Oxley, J.G., Asymptotic properties of random subsets of projective spaces, (), 119-130 · Zbl 0479.05024
[6] Kordecki, W.; Łuczak, T., On random subsets of projective spaces, Coll. math., LXII, 353-356, (1991) · Zbl 0782.60018
[7] Łuczak, T., Cycles in random graphs, Discrete math., 98, 231-236, (1991) · Zbl 0766.05047
[8] Oxley, J.G., Matroid theory, (1992), Oxford University Press Oxford · Zbl 0784.05002
[9] Welsh, D.J.A., Matroid theory, (1976), Academic Press London · Zbl 0343.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.