Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$

Question

Question:

Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$ there exist two of them which share at least $r$ elements.

By Now, I claim that $\color{red}{ r \le 200} $**

reasons were as follows

For all $ k \in \{1, 2, \dots, 10\} $ let $\color{red}{ A_k = \{100k - 99, 100k - 98, \dots, 100k\}}. $ Then if we look at the subsets $ A_1 \cup A_5 \cup A_6 \cup A_7 \cup A_9 $ and $ A_1 \cup A_2 \cup A_7 \cup A_8 \cup A_{10} $ and $ A_2 \cup A_3 \cup A_6 \cup A_8 \cup A_{9} $ and $ A_3 \cup A_4 \cup A_7 \cup A_9 \cup A_{10} $ and $ A_4 \cup A_5 \cup A_6 \cup A_8 \cup A_{10} $ we see that any two of these subsets share exactly $ 200 $ elements which implies that $\color{blue}{ r \le 200. }$

I conjecture $\color{red}{r_{\max}=200?}$ and I can't prove it.Thanks

Answer 1

You are indeed correct. This is really a question about coding theory. Call your family of sets $\mathcal{C}$, and to each set $A\in \mathcal{C}$ in your family you associate an indicator vector in $1_A\in\{0,1\}^{1000}$. Then the condition that for any $A,B\in \mathcal{C}$ that $A\cap B\ge r$ becomes $$d_H(1_A,1_B)=\Delta(A,B)= |A\cup B|-|A\cap B|=|A|+|B|-2|A\cap B|\le 1000-2r$$ where $d_H$ denotes Hamming distance, and $\Delta$ denotes disjoint union. So in other words we are looking for a code of constant weight 500, block length $n=1000$, and distance $d=1000-2r$.

The Plotkin bound says that if $d\ge 500$, then we have that $|\mathcal{C}|\le \frac{2d}{2d-n}$. Plugging in $r=200$ we get $d=600$, and therefore $|\mathcal{C}|\le \frac{1200}{200}=6$. Now note that throwing the all 0's vector into our code (equivalently the empty set into our set family) doesn't reduce the distance as all other codewords have weight 500. Therefore we find that in fact our set family has size at most 5. If you increase $r$ at all, then the Plotkin bound tightens and the size of our set family reduces to at most 4.

Answer 2

Observe that $|A \cap B| \geq 200$ is equivalent to $A \Delta B \leq 600$ here, where $A \Delta B=(A \setminus B) \cup (B \setminus A)$.

Consider the sum $S=\sum_{1 \leq i<j\leq 5}A_i \Delta A_j$. Each of the 1000 elements can contribute to at most 6 of the 10 terms (the max is achieved when an element is present in exactly 2 of the 5 sets or exactly 3 of the 5 sets). Thus $S \leq 6000$ and hence one of these symmetric differences must be at most 600.

Answer 3

I believe you may be correct. I'll leave it to others to judge the strength of my rationale.

Let $a_n$ be the number of elements that appear in $n$ sets. So we have

$$a_1+a_2+a_3+a_4+a_5=1000$$ $$a_1+2a_2+3a_3+4a_4+5a_5=2500$$

Subtracting, we get

$$a_2+2a_3+3a_4+4a_5=1500$$

Now consider a graph with 5 vertices, each corresponding to one of our subsets. Each edge of the graph has a weight equal to the number of elements the two subsets share. The sum of the weights of the $10$ edges is

$$a_2+3a_3+6a_4+10a_5$$

It seems reasonable that the way to minimize this value is to make $a_2$ as large as possible. The best solution appears to be $500$ values appearing twice and $500$ appearing $3$ times. This makes the sum of the weights equal $500+3(500)=2000$. Dividing this equally among each edge gives $10$ edges with a weight of $200$ each.

Answer 4

Take arbitrary $5$ subsets $A_1,A_2,A_3,A_4,A_5$ each with cardinality of $500$. Say $d_k$ is number of set which contains number $k$. Then we have $$ \sum_{i=1}^{1000}d_i = \sum _{i=1}^5|A_i| =2500$$

Connect a pair of sets with number $k$ iff $k$ is in their intersection and let $a_{i,j} = |A_i\cap A_j|$. Suppose $m= \max\{a_{i,j};i\ne j\}$. Then we have: $${5\choose 2}m\geq \sum a_{i,j} = \sum _{i=1}^{1000}{d_i\choose 2} \geq 500{3\choose 2}+ 500{2\choose 2} $$ from here we get $m\geq 200$.