Probabilistic constructions in generalized quadrangles

We study random constructions in incidence structures, and illustrate our techniques by means of a well-studied example from finite geometry. A maximal partial ovoid   of a generalized quadrangle is a maximal set of points no two of which are collinear. The problem of determining the smallest size of a maximal partial ovoid in quadrangles has been extensively studied in the literature. In general, theoretical lower bounds on the size of a maximal partial ovoid in a quadrangle of order (s,t)(s,t) are linear in ss. In this paper, in a wide class of quadrangles of order (s,t)(s,t) we give a construction of a maximal partial ovoid of size at most s⋅polylog(s)s⋅polylog(s), which is within a polylogarithmic factor of theoretical lower bounds. The construction substantially improves previous quadratic upper bounds in quadrangles of order (s,s2)(s,s2), in particular in the well-studied case of the elliptic quadrics Q−(5,s)Q−(5,s).