Sets with small intersections
Task number: 4043
Prove that there exists a constant \( c \) satisfying the following statement. In each collection \( S_1,…, S_n \) of subsets of the set \( \{1, ,…, n \} \), where \( n \) is a positive integer, satisfying \( | S_i \cap S_j | \le 1\) for all \( i, j \) such that \( 1 \leq i < j \leq n \), \( S_i \) can be found with at most \( c \sqrt n \) elements.
Hint
Examine a bipartite graph with parts \( \{1,…, n \} \) and \( {S_1,…, S_n} \).
Solution
The incidence graph cannot contain a four-cycle, so it has at most \(O(n^{3/2}) \) edges. The average degree is \(O(\sqrt{n}) \) and there is necessarily a vertex whose degree does not exceed the average.
