Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 521.05004
Autor: Erdös, Paul; Silverman, R.; Stein, A.
Title: Intersection properties of families containing sets of nearly the same size. (In English)
Source: Ars Comb. 15, 247-259 (1983).
Review: This paper addresses the question: one wants to choose a set S of points in a projective plane of order n such that every line contains at least one point of S, and such that no line has more than x members of S. How small can x be: It is shown that x can be chosen of the order c log n. One can argue as follows: if one chooses every point with probability P at random, the distribution of the number of points on any line obeys a binomial distribution and can be explicitly evaluated. If p is chosen such that the probability of obtaining either 0 or x or more points on a line is less than (\frac{1}{n2+n+1}) or (\frac{1}{n2+n+1})-1, then there is a finite probability that no line in the plane falls to intersect the chosen points in at least one, but x or fewer, points. This paper contains detailed computations showing that this occurs for x = c log n and appropriate c. It also contains discussion of a less efficient constructive example.
Reviewer: D.Kleitman
Classif.: * 05A05 Combinatorial choice problems
05B25 Finite geometries (combinatorics)
60C05 Combinatorial probability
Keywords: families of finite sets; projective plane; binomial distribution
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag