Abstract:
Let $\mathcal{S} = \{S_1,S_2,\dots,S_n\}$ be a family of finite sets. A maximal independent set in $\mathcal{S}$ is a set $X \subseteq \bigcup_{i = 1}^n S_i$ such that for all $i = 1,2,\dots,n$, $S_i \not \subseteq X$. We consider a variety of methods for finding maximal independent sets in graphs using randomness, and in particular, a simple random process for producing a maximal independent set in a family $\mathcal{S}$ of sets based on restrictions on the intersections between the sets in the family. In particular, the following theorem is a corollary, addressing a long-standing problem of Segre (1952) and improving earlier results of Kim and Vu:
Theorem. There exists a constant $c > 0$ such that in any projective plane of order $q$, there exists a set $X$ of at most $c\sqrt{q}\log q$ points such that every line contains at most two of the points, but the addition of any point to $X$ gives a line containing two elements of $X$ plus the additional point.
In the language of finite geometry, this is to say that every projective plane of order $q$ contains a {\em maximal arc} of size of order at most $c\sqrt{q}\log q$.
Joint work with Jeroen Schillewaert