5
$\begingroup$

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).

$\endgroup$
6
  • 1
    $\begingroup$ Why does any edge belong to exactly one triangle? It is of course so for subset-subset edges, but how for subset-element edges? You should use somewhere that your sets are large, else this is just false. $\endgroup$ Feb 2 '16 at 2:18
  • $\begingroup$ @FedorPetrov Thank you, you are right of course. I misstated the claim in a critical way. I've edited my main post to state a different question, which I meant to ask in the first place. $\endgroup$
    – GMB
    Feb 2 '16 at 5:54
  • 2
    $\begingroup$ I still do not understand the same thing as before. $\endgroup$ Feb 2 '16 at 8:42
  • $\begingroup$ Would you kindly define notation big-$\Omega$ in your post? $\endgroup$ Feb 2 '16 at 8:56
  • $\begingroup$ @Włodzimierz usually $A=\Omega(B)$ means that $B=O(A)$, and $A=\Theta(B)$ means that both $A=O(B)$ and $B=O(A)$. $\endgroup$ Feb 2 '16 at 11:37
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you (and sorry for the delayed acceptance) -- it seems to me that you are right, and that I'm phrased the claim wrong. I'll think more about what I'm trying to say here and re-pose the question if needed. $\endgroup$
    – GMB
    Feb 7 '16 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.