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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page