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?

  • $\begingroup$ And what have you tried so far? $\endgroup$ – awllower Feb 20 '13 at 11:48

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)$.

  • $\begingroup$ i got an idea for the construction, shall i post it ? $\endgroup$ – Dominic Michaelis Feb 20 '13 at 12:08
  • $\begingroup$ I do have a construction that works. I'm currently trying to figure out the best way to describe it. You can post yours if you want. $\endgroup$ – Ivan Loh Feb 20 '13 at 12:18
  • $\begingroup$ done it maybe it helps $\endgroup$ – Dominic Michaelis Feb 20 '13 at 12:19
  • $\begingroup$ My construction doesn't for $n=5$ sorry :( $\endgroup$ – Dominic Michaelis Feb 20 '13 at 12:56

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.


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.


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.