| Affiliation: | (1) Microsoft Research, Microsoft Corporation, Redmond, WA 98052, USA;(2) Department of Mathematics, UCSD, La Jolla, CA 92093, USA |
| Abstract: | In the late 1950 s, B. Segre introduced the fundamentalnotion of arcs and complete arcs [48,49]. An arc in a  niteprojective plane is a set of points with no three on a line andit is complete if cannot be extended without violating thisproperty. Given a projective plane  , determining  , the size of itssmallest complete arc, has been a major open question in finitegeometry for several decades. Assume that  has orderq, it was shown by Lunelliand Sce [41], more than 40 years ago, that  . Apart from this bound,practically nothing was known about  , except for the case  is the Galois plane. Forthis case, the best upper bound, prior to this paper, wasO(q 3/4)obtained by Sz nyi using the properties of the Galois fieldGF(q).In this paper, we prove that  for any projective plane of orderq, wherec is a universal constant.Together with Lunelli-Sces lower bound, our result determines  up to a polylogarithmicfactor. Our proof uses a probabilistic method known as thedynamic random construction or Rödls nibble. The proof alsogives a quick randomized algorithm which produces a smallcomplete arc with high probability.The key ingredient of our proof is a new concentrationresult, which applies for non-Lipschitz functions and is ofindependent interest.* Research supported in part by grant RB091G-VU fromUCSD, by NSF grant DMS-0200357 and by an A. Sloanfellowship.Part of this work was done at AT&T Bell Labs andMicrosoft Research |
