A construction for large families of k-element sets having the Erdős intersection property (Q1065799)

It is known that the largest collection of k-element sets with the property that no one contains the intersection of two others, has, for large k, size \(c^ k\) with \((1+\sqrt{2})/2<C<27/16\), but no explicit construction is known for collections near this size for large k. This paper contains description of a simple construction that produces a collection whose size is on the order of \(2^{\sqrt{2k}}\) (actually it can be improved slightly to roughly \(2^{2\sqrt{k}}).\) The construction is based on the idea that given such a collection of size m for a given set size k, one can construct one of size 2m and set size \(k+u\) whenever the binomial coefficient C(2u,u)\(\geq 2m\), by adding to each of the m original k-sets a unique u-element subset of 2u new elements, and also adding the complement of this set in the 2u elements to it.