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?

  • $\begingroup$ The most trivial one is the family of all singletons. It has the same $\ n\ $ members. $\endgroup$ – 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.

  • 2
    $\begingroup$ Why not add A to it for a slightly larger set? Not to mention the empty set. $\endgroup$ – The Masked Avenger Jan 13 '15 at 17:56
  • $\begingroup$ @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. $\endgroup$ – Włodzimierz Holsztyński Jan 13 '15 at 19:56
  • $\begingroup$ @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). $\endgroup$ – Włodzimierz Holsztyński Jan 13 '15 at 19:59
  • 1
    $\begingroup$ You can also add all the singleton sets (and the empty set) to your solution. This gives $\binom{n}{2}+n+1$ sets. $\endgroup$ – Tony Huynh Jan 14 '15 at 13:15
  • $\begingroup$ @TonyHuynh -- with your approval, I'd add an extra EDIT note, which would state your addition (and I'd mention TMA too :-). $\endgroup$ – Włodzimierz Holsztyński Jan 14 '15 at 22:36

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.