For sets $A_1, \ldots, A_k$, with $n^2$ different elements, $|A_i| \geq 2n$, and every set pair $A_i, A_j$ shares at most 1 element, show $k \leq n$

Question

Given positive integers $n, k$, and:

$$ \left| \bigcup_{i = 1}^{k} A_i \right| = n^2$$

$$ \left| A_i \right| \geq 2n, \quad 1 \leq i \leq k$$

$$ \left| A_i \cap A_j \right| \leq 1, \quad 1 \leq i < j \leq k$$

We must show that $k \leq n$ in such a scenario.

I am going to attempt to prove this in two different ways:

1) What is the minimum number of unshared elements that every set must contain? To figure this out, we must minimize the total number of elements in every set (i.e. take every set to have $2n$ elements), and maximize the number of shared elements (i.e. every set must have one element shared for each remaining $k - 1$ sets). Thus, the minimum number of unshared elements must be:

$$ 2n - (k - 1) $$

Meanwhile, the average number of elements per set must be $n^2/k$, but this average must be greater than (or equal to, if $k = 1$), the minimum number of unshared elements in a set:

\begin{align*} &\quad \frac{n^2}{k} \geq 2n - k + 1 \\ &\Rightarrow \frac{n^2}{k} \geq 2kn - k^2 + 1 \\ &\Rightarrow n^2 \geq 2kn - k^2 + k \end{align*}

Assume that $k = n + 1$, in other words, that $k > n$. Then:

\begin{align*} &\quad n^2 \geq 2n(n + 1) - (n + 1)^2 + n + 1 \\ &\Rightarrow n^2 \geq 2n^2 + 2n - n^2 - 2n - 1 + n + 1 \\ &\Rightarrow n^2 \geq (2n^2 - n^2) + (2n - 2n + n) + (1 - 1) \\ &\Rightarrow n^2 \geq n^2 + n \\ &\Rightarrow 0 \geq n \end{align*}

But this condition is trivially false since $n$ is positive, so we have reached a contradiction, thus $k \leq n$.

2) Take the case where no elements are shared between any pair of sets, and every set has the minimum number of elements, $2n$. Then the total number of elements if there are $k$ sets will be exactly $2kn$, so we have:

\begin{align*} &\quad n^2 \geq 2kn \\ &\Rightarrow n \geq 2k \\ &\Rightarrow n > k \end{align*}

It this condition did not hold, we would not be able to construct the above scenario, which is clearly valid. Thus, we must have that $k < n$ (note the strict inequality!)

---

Note that proof 2 does not show that $k \leq n$, but instead shows strict inequality. Is proof 2 correct in showing a stronger inequality than proof 1, or am I doing something wrong in proof 2?

Answer 1

Suppose we build up the sets one at a time. So A_1 brings 2n elements, A_2 can being 2n-1, etc. We see that the total size is (2n) + (2n-1) + ... + (2n - k + 1). Set this to = n^2 and solve for k

This is 2kn - k(k-1)/2 = n^2. k^2 - 4(n+1)k + 2n^2 = 0. K < 2(n+1) - sqrt(2)(n+1) < 0.6(n+1)

As an example, take n=5. {1-10}, {1, 11-19} {2, 11, 20-28}. We're already over our limit. The equation there is k^2 - 21k + 50 = 0, first solution is when you run out of k, which is a little less than 3.

Edit: noticed this was proof review:

Your first proof is interesting, although second step could do with maybe a slicker argument. For example with k=n, you would also see that n >= n+1 which is a contradiction too. Second proof doesn't work because you aren't packing the sets as tightly as you can? Imagine if we were to allowed intersect in all but 1 element for example. Then we could have something like k = (n - 1)^2

Answer 2

Work in progress ...

Using inclusion-exclusion principle and $$\left|\bigcup\limits_{i=1}^{k}A_i\right|\leq \sum\limits_{i=1}^{k}\left|A_i\right| \tag{1}$$

Case 1 $$\left|A_i\bigcup A_j\right|=\left|A_i\right|+\left|A_j\right|-\left|A_i\bigcap A_j\right|\geq 2n+2n-(2-1)$$

Case 2 $$\left|A_i\bigcup A_j\bigcup A_t\right|=\left|A_i\bigcup A_j\right|+\left|A_t\right|-\left|\left(A_i \bigcup A_j\right)\bigcap A_t\right|=\\ \left|A_i\bigcup A_j\right|+\left|A_t\right|-\left|\left(A_i \bigcap A_t\right) \bigcup \left(A_j \bigcap A_t\right)\right| \overset{(1)}{\geq}\\ \left|A_i\bigcup A_j\right|+\left|A_t\right|-\left|A_i \bigcap A_t\right| - \left|A_j \bigcap A_t\right|\geq\\ 2n+2n-(2-1)+2n-(3-1)$$

By induction $$\left|\bigcup\limits_{i=1}^{k}A_i\right|=\left|\bigcup\limits_{i=1}^{k-1}A_i\right|+\left|A_k\right|-\left|\left(\bigcup\limits_{i=1}^{k-1}A_i\right)\bigcap A_k\right|=\\ \left|\bigcup\limits_{i=1}^{k-1}A_i\right|+\left|A_k\right|-\left|\bigcup\limits_{i=1}^{k-1}\left(A_i \bigcap A_k\right)\right| \overset{(1)}{\geq} \left|\bigcup\limits_{i=1}^{k-1}A_i\right|+\left|A_k\right|-\sum\limits_{i=1}^{k-1}\left|A_i \bigcap A_k\right|\geq \\ \left|\bigcup\limits_{i=1}^{k-1}A_i\right|+2n-(k-1) \geq \left|\bigcup\limits_{i=1}^{k-2}A_i\right|+2n-(k-1-1)+2n-(k-1)\geq \\ ... \geq 2kn - (1+2+...+k-1)=2kn-\frac{(k-1)k}{2}$$

Altogether $$n^2 \geq 2kn-\frac{(k-1)k}{2} \Rightarrow k^2-(4n+1)k+2n^2 \geq 0$$

$$k\geq\frac{(4n+1)+\sqrt{(4n+1)^2-8n^2}}{2}= \frac{(4n+1)+\sqrt{8n^2+8n+1}}{2}>3n \tag{2}$$ $$0<k\leq\frac{(4n+1)-\sqrt{8n^2+8n+1}}{2}<n \tag{3}$$

Now see if you can rule out case $(2)$