# Common sizes of intersections

I'm trying to come up with the largest family of sets that obeys the following properties:

Consider $X = \{1,\dots,n\}$ and take $\mathcal{F} \subset 2^X$ such that for any three subsets $A,B,C \in \mathcal{F}$ we have that (at least) two of the numbers $|A \cap B|, |B \cap C|, |A \cap C|$ are the same size.

There is a trivial example here, $\{1\}, \{1,2\}, \{1,2,3\},\dots$ which gives a family $\mathcal{F}$ of size $n$, but I don't see how to do better (I've tried using modular arithmetic, which doesn't seem to help all that much.)

In this problem it doesn't particularly matter (to me at least) what $n$ is, eg, for the modular arithmetic way I was trying I set $n = L^2$ for some integer.

So, my question is as follows, is there a better choice for $\mathcal{F}$, eg, one that is larger than the trivial?

• The most trivial one is the family of all singletons. It has the same $\ n\$ members. – Włodzimierz Holsztyński Jan 13 '15 at 11:45

Consider $\ \binom A2\$ for an arbitrary finite set $\ A.\$ Then you get a proper family with $\ \binom n2\$ members for $\ n:=|A|.\$ You get an improvement for every $\ n>3$.

EDIT:   Let me coin the name "Three Is a Crowd" (or TIsC for short) for the families introduced in the Question by James Kilbane. Now thanks to the comments let me record certain improvements:

• The Masked Avenger has proposed to add the whole set $\ A,\$ and the empty set too--let's be greedy. Thus the enlarged Three Is a Crowd family looks like this:

$$\binom A2\cup\{A\,\ \emptyset\}$$

for a new record $\ \binom n2+2\$ for $\ n=|A|$.

• Tony Huynh has successfully added the singletons (and the empty set). This gives the following increased Three Is a Crowd family:

$$\binom{A}{2} \cup \binom A 1 \cup \binom A 0$$

for a new record $\ \binom {n+1}2$.

• The semi-dual example is just as good:

$$\binom A{n-2}\cup\binom A{n-1}\cup\{\emptyset\}$$

for $\ n:=|A|.\$ We get $\ \binom {n+1}2\$ different members again.

It'd be nice to find the maximum.

• Why not add A to it for a slightly larger set? Not to mention the empty set. – The Masked Avenger Jan 13 '15 at 17:56
• @TheMaskedAvenger -- I've answered the Question exactly, and without going into extra trivialities--the originator didn't bother with the empty set (and he could); thus there was an implied assumption that the sets should be non-empty (either way). My answer is the simplest so far. I followed the Kazimierz Kuratowski's principle: first of all an example should be as simple as possible. – Włodzimierz Holsztyński Jan 13 '15 at 19:56
• @TheMaskedAvenger -- you're welcome to add another, more advanced and sharper result (Especially that a simple answer is already present, making sense to develop the idea further). – Włodzimierz Holsztyński Jan 13 '15 at 19:59
• You can also add all the singleton sets (and the empty set) to your solution. This gives $\binom{n}{2}+n+1$ sets. – Tony Huynh Jan 14 '15 at 13:15
• @TonyHuynh -- with your approval, I'd add an extra EDIT note, which would state your addition (and I'd mention TMA too :-). – Włodzimierz Holsztyński Jan 14 '15 at 22:36