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

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.


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.

Tags:

Optimization

Combinatorics

Extremal Combinatorics

Discrete Optimization

Related

What is the meaning of subtracting from the identity matrix? What is the meaning of $1/(D+a)$, where $D$ is the derivative operator? $\arctan x=\frac{1}{2}i[\ln(1-ix)-\ln(1+ix)]$ $A = \sum_{n=0}^\infty a_n$ and $b_n \to B$ implies $\sum_{k=0}^n a_k b_{n-k} \to AB$ Is there an elegant way to evaluate $ I={ \int \sqrt[8]{\frac{x+1}{x}} \ \mathrm{d}x}$? Prove ${2\over \pi}\int_{0}^{\infty}\prod_{k=1}^{n\ge1}{k^2\over k^2+x^2}dx={n\over 2n-1}$ How can I find an explicit expression for this recursively defined sequence? integral inequality for $f(x)$ and $f(\sqrt{x})$ Find a continuous function $f:[1,\infty)\to\Bbb R $ such that $f(x) >0 $, $\int_1^\infty f(x)\,dx $ converges and $\int_1^\infty f(x)^2\,dx$ diverges Prove $\int_{0}^{\infty}{1\over (1+{\phi^{-2}}x^2)(1+{\phi^{-4}}x^2)}dx={\pi\over 2}$ Limit of the solutions of a trigonometric equation How to Axiomize the Notion of "Continuous Space"?

Recent Posts