Thresholds in the Lattice of Subspaces of (F_q)^n

10/01/2019

∙

by   Benjamin Rossman, et al.

∙

0

∙

share

Let Q be an ideal (downward-closed set) in the lattice of linear subspaces of (F_q)^n, ordered by inclusion. For 0 < k < n, let μ_k(Q) denote the fraction of k-dimensional subspaces that belong to Q. We show that these densities satisfy μ_k(Q) = 1/1+z μ_k+1(Q) <1/1+qz. This implies a sharp threshold theorem: if μ_k(Q) < 1-ε, then μ_ℓ(Q) <ε for ℓ = k + O(log_q(1/ε)).