My question is inspired by the following observation:


**Claim:** It is *not* possible to choose $n$ subsets of the universe $[n]$, each of size $\Omega(n)$, such that for each subset $S$ and each element $s \in S$, there is another subset $S'$ such that $S \cap S' = \{s\}$.


**Proof:** Suppose, towards a contradiction, that this system of subsets exists. First, build a bipartite graph, in which nodes on the left side of the partition correspond to subsets, nodes on the right side of the partition correspond to members of the universe, and edges correspond to set membership. Next, add an edge between each pair of subsets that intersects on exactly one element. Note that this graph contains $\Omega(n^2)$ triangles, and each edge that participates in any of these triangles participates in *exactly one* triangle.


We now obtain a contradiction by applying the Triangle Removal Lemma, which states: for all $\epsilon > 0$, there is a $\delta > 0$ such that any graph with at most $\delta n^3$ triangles can be made triangle-free by removing at most $\epsilon n^2$ edges. Our graph has $\Theta(n^2)$ triangles, so it satisfies the premise regardless of the value of $\delta$. Thus, we can make the graph triangle-free by removing $\epsilon n^2$ edges, for any $\epsilon > 0$. By choosing $\epsilon$ so small that the graph has more than $\epsilon n^2$ edge-disjoint triangles, we obtain a contradiction.



> 
> **My Question:** Suppose that we are now choosing $n$ subsets, each of size $\Omega(n)$, out of a universe $[u]$. How large does $u$ have to be such that it *is* possible that for each $s \in S$, there exists $S'$ with $S \cap S' = \{s\}$?
> 
> 
> 


The above proof shows that $u = \omega(n)$. The trivial upper bound -- which I have not been able to beat -- is $u = O(n^2)$. I am interested in improving either of these bounds. I am especially interested in whether $u = \Omega(n^{1 + c})$ for some absolute $c > 0$ (i.e. a polynomial increase in $u$ is required).



How often can subsets of a universe intersect exactly once?
It seems that for every $k\geq 2$, there exists a desired cpllection of $6k$ subsets of $[3k]$ with size $k$ each. 


Let $a\_1$, $a\_2$, $a\_3$ be three rays with a common origin $O$, and let $s\_1,\dots,s\_k$ be $k$ different circles centered at $O$. Denote $x\_{ij}=a\_i\cap s\_j$; we may identify $[3k]$ with the set of all the $x\_{ij}$.


Now take $6k$ sets as follows. Each set consists of all the points on one of the rays $a\_i$ except for some element $x\_{ij}$, this element being replaced with some $x\_{i'j}$, $i'\neq i$. It seems that this collection satisfied all the requirements.


One may also restrict to the sets with $i'=i+1\mod 3$.


So, if I'm right, there is something wrong with the proof of the claim.


