Search

We prove that with high probability G (3) (n , n - 1 + o (1)) contains a spanning Steiner triple system for n ≡ 1 , 3 (mod 6) , establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park. [ABSTRACT FROM AUTHOR]

Let ξ be a non-constant real-valued random variable with finite support and let M n (ξ) denote an n × n random matrix with entries that are independent copies of ξ . For ξ which is not uniform on its support, we show that P [ M n (ξ) is singular ] = P [ zero row or column ] + (1 + o n (1)) P [ two equal (up to sign) rows or columns ] , thereby confirming a folklore conjecture. As special cases, we obtain: For ξ = Bernoulli (p) with fixed p ∈ (0 , 1 / 2) , P [ M n (ξ) is singular ] = 2 n (1 - p) n + (1 + o n (1)) n (n - 1) (p 2 + (1 - p) 2) n , which determines the singularity probability to two asymptotic terms. Previously, no result of such precision was available in the study of the singularity of random matrices. The first asymptotic term confirms a conjecture of Litvak and Tikhomirov. For ξ = Bernoulli (p) with fixed p ∈ (1 / 2 , 1) , P [ M n (ξ) is singular ] = (1 + o n (1)) n (n - 1) (p 2 + (1 - p) 2) n. Previously, only the much weaker upper bound of (p + o n (1)) n was known due to the work of Bourgain–Vu–Wood. For ξ which is uniform on its support: We show that P [ M n (ξ) is singular ] = (1 + o n (1)) n P [ two rows or columns are equal ]. Perhaps more importantly, we provide a sharp analysis of the contribution of the 'compressible' part of the unit sphere to the lower tail of the smallest singular value of M n (ξ) . [ABSTRACT FROM AUTHOR]