37
$\begingroup$

Let $\mathcal F$ be a family of nonempty subsets of $X=\{1,2,\ldots, N\}$, such that for any three distinct $A,B,C \in \mathcal F$ we have $A \cap B \cap C = \varnothing$. What is the maximum cardinality of $\mathcal F$?

I suspect the answer is about $3N/2$ and can be obtained from for example $$\mathcal F = \{\{1\},\{2\},\ldots , \{N\}, \{1,2\}, \{3,4\},\ldots, \{N-1,N\}\} \text{ assuming even } N.$$

But so far I can only prove the upper bound of $2N-1$. This is obtained by considering the function that takes every set in $\mathcal F$ to its minimum element. The fibres over $1,2,\ldots, N-1$ can each contain at most two sets, as otherwise we would get three sets with a shared element, which is not allowed. The fibre over $N$ can contain at most the set $\{N\}$. Hence we get the bound $2(N-1)+1=2N-1$.

$\endgroup$
0

4 Answers 4

39
$\begingroup$

Yes, the maximum possible size of $\newcommand\F{\mathcal F}\F$ is $\lfloor 3n/2\rfloor$.

Consider the $n\times |\F|$ incidence matrix for this set family. Each row corresponds to a number in $\{1,\dots,n\}$, and each column corresponds to a subset in $\F$. The entry is $1$ if the subset contains that number, and $0$ otherwise.

Let us count the number of ones in this matrix in two ways. For each $k\in \{1,\dots,n\}$, let $f_k$ be the number of subsets in $\F$ with cardinality $k$. On the one hand, there are exactly $f_1+2f_2+3f_3+\dots+nf_n$ ones in the matrix, counting by columns. On the other hand, the condition that $A\cap B\cap C=0$ implies there are at most two ones in each row, so at most $2n$ ones total. This proves $$ f_1+2f_2+\dots+nf_n\le 2n $$ Conclude as follows: $$ \begin{align} |\F| &=f_1+f_2+\dots+f_n \\&= \frac12f_1+ \frac12(f_1+2f_2+2f_3+\dots+2f_n) \\&\le \frac12f_1+\frac12(f_1+2f_2+\color{blue}3f_3+\dots+\color{blue}nf_n) \\&\le \frac12\cdot n+\frac12\cdot 2n \end{align} $$ This inequality, combined with the fact that $|\F|$ is an integer, implies $|\F|\le \lfloor 3n/2\rfloor$. The construction in your post achieves this bound exactly, so it is optimal.

$\endgroup$
18
$\begingroup$

We note that we can pick $\mathcal{F}$ to consist only of sets of size one or two, for if $\mathcal{F}$ contains $A = \{a_1,\dots, a_r\}$ for $r\geq 3$, we can replace $A$ by either $\{a_1\}$ or $\{a_1, a_2\}$, as at least one of these is not in $\mathcal{F}$. This maintains the triple intersection property. We can also choose $\mathcal{F}$ to be downward closed, as replacing a set by one of its subsets not in $\mathcal{F}$ maintains the triple intersection property. Finally, in such an $\mathcal{F}$ any 2-element sets are disjoint. This shows your example is optimal.

$\endgroup$
11
$\begingroup$

Let $m$ be the maximum possible size of such a family. Among all such families of size $m$, consider a family $\mathcal F$ which minimizes the quantity $\sum_{X\in\mathcal F}|X|$.

Note that, if $X\in\mathcal F$, then all nonempty subsets of $X$ must also belong to $\mathcal F$; for if some nonempty subset $Y$ of $X$ did not belong to $\mathcal F$ we could replace $X$ with $Y$.

It follows that every element of $\mathcal F$ has at most two elements; for if a set $X\in\mathcal F$ contained three distinct elements $a.b.c$ then $\mathcal F$ would contain four sets $\{a,b,c\},\{a,b\},\{a,c\},\{a\}$ with nonempty intersection. Moreover, the $2$-element member of $\mathcal F$ must be pairwise disjoint; if $\{a,b\}\in\mathcal F$ and $\{a,c\}\in\mathcal F$, then $\mathcal F$ contains three sets $\{a,b\},\{a,c\},\{a\}$ with nonempty intersection.

Hence $\mathcal F$ contains at most $N$ $1$-element sets and at most $\left\lfloor\frac N2\right\rfloor$ $2$-element sets, so that $m=|\mathcal F|\le N+\left\lfloor\frac N2\right\rfloor=\left\lfloor\frac{3N}2\right\rfloor$.

More generally, suppose $2\le k\in\mathbb N$. If $\mathcal F$ is a family of nonempty subsets of the $n$-element set $V=\{1,\dots,n\}$ such that the intersection of any $k$ distinct elements of $\mathcal F$ is empty, then $|\mathcal F|\le\left\lfloor\frac{kn}2\right\rfloor$; moreover, this bound is attained if $n\ge k-1$.

Suppose $\mathcal F$ is a family of nonempty subsets of $V$ such that no element of $V$ belongs to $k$ elements of $\mathcal F$. Let $m=|\mathcal F_{\ge2}|$ where $\mathcal F_{\ge2}=\{F\in\mathcal F:|F|\ge2\}$; say $\mathcal F_{\ge2}=\{F_1,\dots,F_m\}$. We may assume that all $1$-element subsets of $V$ belong to $\mathcal F$, whence any element of $V$ belongs to at most $k-2$ elements of $\mathcal F_{\ge2}$. As in @Mike Earnest's answer, consider the $n\times m$ incidence matrix $$a_{i,j}=\begin{cases} 1\text{ if }i\in F_j,\\ 0\text{ if }i\notin F_j.\\ \end{cases}$$ Now $$2m\le\sum_{j=1}^m|F_j|=\sum_{j=1}^m\sum_{i=1}^na_{i,j}=\sum_{i=1}^n\sum_{j=1}^ma_{i,j}\le n(k-2),$$ whence $|\mathcal F_{\ge2}|=m\le\left\lfloor\frac{n(k-2)}2\right\rfloor$ and $|\mathcal F|=n+|\mathcal F_{\ge2}|\le n+\left\lfloor\frac{n(k-2)}2\right\rfloor=\left\lfloor\frac{kn}2\right\rfloor$.

If $n\ge k-1$ the bound can be attained as follows. Take a graph $G=(V,E)$, with $n$ vertices and $\left\lfloor\frac{n(k-2)}2\right\rfloor$ edges, having the degree sequence $d,d,\dots,d,d'$ where $d=k-2$ and $$d'=\begin{cases} d\ \ \ \ \ \ \ \ \text{ if }nd\text{ is even,}\\ d-1\ \text{ if }nd\text{ is odd.} \\ \end{cases}$$ Let $\mathcal F$ consist of the sets $\{v\}$ where $v\in V$ and the sets $\{u,v\}$ where $uv\in E$.

$\endgroup$
1
  • 1
    $\begingroup$ Ah I just wrote the same solution basically. Nice work! $\endgroup$ Commented Dec 31, 2024 at 23:22
8
$\begingroup$

For $S \subseteq \{1,\dots,n\}$, let binary decision variable $x_S$ indicate whether $S \in \mathcal F$. The problem is to maximize $\sum_S x_S$ subject to linear constraints $$\sum_{S: i \in S} x_S \le 2 \quad \text{for all $i\in\{1,\dots,n\}$} \tag1\label1$$ that prevent each $i$ from appearing more than twice.

It turns out that the linear programming (LP) relaxation obtained by ignoring integrality of $x_S$ yields maximum objective value $3n/2$, which implies an upper bound of $\lfloor 3n/2 \rfloor$ for the original problem. The LP dual variables provide a short certificate of optimality. Explicitly, take dual variable $1/2$ for the upper bound constraint $x_S \le 1$ on each $S$ such that $|S|=1$, dual variable $|S|/2-1$ for the lower bound constraint $-x_S \le 0$ on each $S$ such that $|S|\ge 2$, and dual variable $1/2$ for each constraint in \eqref{1}, yielding \begin{align} \sum_S x_S &= \sum_S \left(1 - \frac{|S|}{2} + \frac{|S|}{2}\right) x_S \\ &= \sum_S \left(1-\frac{|S|}{2}\right) x_S + \frac{1}{2}\sum_S \sum_{i\in S} x_S \\ &= \sum_{S:|S|=1} \left(1-\frac{|S|}{2}\right) x_S + \sum_{S:|S|\ge 2} \left(1-\frac{|S|}{2}\right) x_S + \frac{1}{2}\sum_S \sum_{i\in S} x_S \\ &= \sum_{S: |S|=1} \frac{1}{2} x_S + \sum_{S: |S| \ge 2} \left(\frac{|S|}{2}-1 \right) (-x_S) + \sum_{i=1}^n \frac{1}{2} \sum_{S:i\in S} x_S \\ &\le \sum_{S: |S|=1} \frac{1}{2} \cdot 1 + \sum_{S: |S| \ge 2} \left(\frac{|S|}{2}-1\right) 0 + \sum_{i=1}^n \frac{1}{2} \cdot 2 \\ &= \frac{n}{2} + 0 + n \\ &= \frac{3n}{2}. \end{align}


In retrospect, this is essentially the same argument as in Mike Earnest's answer. The correspondence is $f_k = \sum_{S: |S|=k} x_S$. Note that the LP dual variables arise automatically as a by-product of an LP solver call.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.