On the connectivity of random subsets of projective spaces. (English) Zbl 0939.51012

Kordecki, Wojciech; Łuczak, Tomasz

Discrete Math. 196, No. 1-3, 207-217 (1999).

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)\).

Reviewer: A.Cossidente (Potenza)

MSC:

51E20	Combinatorial structures in finite projective spaces
05B35	Combinatorial aspects of matroids and geometric lattices
05B25	Combinatorial aspects of finite geometries

Keywords:

random subsets; connectivity; matroid

References:

[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