Sum of sizes of subsets which intersect at most one element

79 Views Asked by At

I have the following problem at hand (HW problem so please don't give me full solutions). We have a set $N$ with $n$ elements and $M=\{M_1,M_2,\dots,M_n\}$ such that each two intersect at at most one element. I am asked to ddetermine weather $\sum(|M_i|)= O(n^{4/3})$. My claim is that it is and I show it in the following way:

Place the points of $N$ in plane in such a way that points of $M_i$ are colinear, then construct a set of $n$ lines $L=\{l_1,\dots,l_n\}$ where $l_i$ correspond to $M_i$. Then $\sum(|M_i|)$ is exactly the number of incidences between $L$ and $N$ so by Szemeredi-Trotter we're done.

Is this the correct approach or do I need to change something?

1

There are 1 best solutions below

3
On BEST ANSWER

My previous version of this answer consisted of hints that were misleading.

You cannot prove that $\sum_i |M_i|$ is $O(n^{4/3})$. In the case where there exists a projective plane with $n$ points, and we let $M_i$ be the set of points on the $i^\text{th}$ line, then you would have $\sum_i |M_i|\in \Theta(n^{3/2})$. Precisely, when $n=q^2+q+1$ for some prime power $q$, then a projective plane exists, where each $|M_i|=q+1$, and each point is contained in $q+1$ lines/sets.

Regarding your attempted proof, this must mean that it is not always possible to realize the given list of sets as an incidence system of points and lines in the plane.