On the connectivity of random subsets of projective spaces

✍ Scribed by Wojciech Kordecki; Tomasz Łuczak

• Book ID: 104114186
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 628 KB
• Volume: 196
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(98)00201-5

✦ Synopsis

It is shown that with probability tending to 1 as r --+ 00 a random subset o,(n) of n elements of the projective space PG(r -1, q) becomes k-connected when n = r + (k -1) log, r + 0( 1). Furthermore, the cyclic structure of w,(n) is considered, and a similar very sharp threshold for the existence of circuits of length r is found. @ 1999 Elsevier Science B.V. All rights reserved ' Research partially supported by KBN grant 2 P03A 023 09.