Question about members in sets

Question

Let $A_1,A_2,...,A_n$ be sets with $k$ members in $A_i$ for every $1\le i\le n$. Suppose that the $A_i$ satisfy:

1) $|A_i\cap A_j| = 1$ for all $i\ne j$,

2) $A_1\cap A_2\cdots\cap A_n =\emptyset$.

What is the largest $n$ for every $k\in \mathbb{Z}^+$?

Somebody told me that the largest $n$ is $(k-1)^2+k$ when $k=1,2,3,4$. How can one prove this?

Answer 1

I haven't come up with a general construction yet, but I believe the answer is $n=k^2-k+1$. I will prove that $n \leq k^2-k+1$. I will edit in the construction in a while when I get it.

WLOG let $A_1=\{1, 2, \ldots , k\}$, and let $x_a$ be the number of $j \not =1$ such that $a \in A_j$, where $1 \leq a \leq k$.

Observe that if $x_a \geq k$, then WLOG let $a \in A_{j}$ for $2 \leq j \leq x_a+1$.

By condition 1), each $A_j, 1 \leq j \leq x_a+1$ has only $a$ in common.

By condition 2), $x_a+1<n$. Consider any $l>x_a+1$, then $A_l$ does not contain $a$. Thus $A_l \cap (A_j \setminus a)=\{a_j\}, 1 \leq j \leq x_a+1$, where $a_j$ are distinct.

Therefore $|A_l| \geq x_a+1 \geq k+1$, a contradiction.

Thus $x_a \leq k-1$, so $n=1+\sum\limits_{a=1}^{k}{x_a} \leq 1+k(k-1)$.

Answer 2

We can follow @Ivan's answer, to give a construction with $k(k-1)+1$ sets. It was shown that each element cannot be present in more than $k$ sets, this construction has each element occurring in exactly $k$ sets.

Let $A_1 = \{1,2,\ldots ,k\}$. Let the next $k-1$ sets $A_2, A_3, \ldots , A_k$ contain element $k$. As they all now have a common element $k$, the remaining $(k-1)^2$ elements must be distinct. Let them be $k+1, k+2, \ldots , k+(k-1)^2$, distributed among the $k-1$ sets sequentially, i.e., for $j=2,3, \ldots k$, $A_j = \{j(k-1)+2, j(k-1)+3, \ldots , j(k-1)+k\}$.

The remaining $(k-1)^2$ sets $A_{i(k-1)+j+1}$ (where $i,j=1,2, \ldots , k-1$) are described by

1. $i \in A_{i(k-1)+j+1}$
2. $p,q \in A_{i(k-1) + j+1} \Leftrightarrow (p-q) \mod (k+j-2) \equiv 0$

i.e., $A_{i(k-1)+j+1} = \{[i+r(k+j-2)] \mod ((k-1)^2 + k): r=0,1,\ldots ,k-2\}$. It is easy to verify that these sets satisfy the required constraints.

Answer 3

Somebody told me that the largest $n$ is
$(k−1)^2+k$ when $k=1,2,3,4$. How can one prove this?

That is the bound from taking the sets to be the $q^2+q+1$ lines in a projective plane with coordinates from the field with $q$ elements, with $q=k-1$. The finite field exists when $k-1$ is a prime power, which covers the cases $k=3,4,5,6$. Your informant was thinking of this construction for the special case where $q$ is prime so that one can use integers mod $q$ as coordinates instead of talking about finite fields. This works for $q \leq 3$, or $k=3,4$. There is no solution for $k=1$ and the solution for $k=2$ satisfies the same bound. This explains why your source gave the answer up to $k=4$ only.