Find the maximal possible $n$, where $A_1, \dots, A_n \subseteq \{1, 2, \dots, 2016\}$ satisfy the following properties. - For each $1 \le i \le n$, $\lvert A_i \rvert = 4$. - For each $1 \le i < j \le n$, $\lvert A_i \cap A_j \rvert$ is even.
Problem
Source: Korean Summer Program Practice Test 2016 5
Tags: combinatorics, set
don2001
09.01.2017 18:41
Could you please give me some guidance ? Thank you.
rafayaashary1
09.01.2017 20:06
I used very sketchy methods to show that if we work in $[k]$, and $8\mid k$ then the answer is $\tfrac{k^2+2k}{16}$, so plugging in $2016$ gave $254268$, for which I have a construction. The form $\tfrac{1}{2}\tbinom{1009}{2}$ makes me suspect a nice solution.
My idea was: Consider the partition of the family $\mathcal{A}=\{A_1,A_2,\cdot A_n\}$ into disjoint basal sets $B_i\in \mathcal{A}$, defined so that $i\neq j\implies \not\exists A\in \mathcal A\text{ s.t. }A\cap B_i\neq \emptyset\text{ and }A\cap B_j\neq \emptyset$. Suppose there are $b$ basal sets, then there are $k-4b$ "leaves" (elements of $[k]$ not in any basal set). Now, consider some basal set $B$. Notice that if $A\cap B\neq \emptyset$ then there are $2$ possibilities for $A\cap B$. Consider such $A_1,A_2$. Then $A_1\setminus (A_1\cap B)$ and $A_2\setminus (A_2\cap B)$ are either disjoint or equal. Then there are at most $\tfrac{n-4k}{2}$ possibilities for such $A\setminus (A\cap B)$, and overall there are at most $2\cdot\tfrac{k-4b}{2}$ non-basal sets intersecting $B$. Summing over all basal sets, and including them in the count, we have $|\mathcal{A}|\leq b(k-4b+1)=-4b^2+(b+1)k$. Since $b$ is integral, and $8\mid k$, we have our maximum at $b=\tfrac{k}{8}\implies |\mathcal{A}|\leq \tfrac{k^2+2k}{16}$. The construction follows from the above.
rafayaashary1
12.01.2017 20:43
I think the above is poorly done, but on the right track. If I am not mistaken, the real answer is $\tbinom{1008}{2}$. The construction is simple: partition $\{1,2,\dots,2016\}$ into $1008$ sets of size two, and take the family of all pairwise unions. Denote the family of sets under consideration as $\mathcal{A}=\{A_1,A_2,\dots\}$. Again, we observe that if as $j$ spans the set of non-$i$ indices, $A_i\cap A_j$ has at most two disjoint nonempty outputs, all of whom have size $2$. With that end in mind, if $A_i\cap A_j=S$ where $i\neq j$ and $S\neq \emptyset$, then we assign the elements of $S$ a shared color distinct from any previously assigned colors, and carry out this process over all distinct $i,j$. If by the end $m$ colors are assigned, then $|\mathcal{A}|\leq \tbinom{m}{2}+\tfrac{2016-2m}{4}$. Furthermore, we have $m\leq 1008$, and it follows that the maximum occurs at $m=1008$, who gives the aforementioned construction $\Box$
math90
13.01.2017 16:27
The answer is $\binom{1008}{2}$. My construction is the same as rafayaashary1's. Suppose for contradiction that we have a family of $\binom{1008}{2}+1$ sets satisfying the condition. The total number of pairs of element and set which contains the element, is $4\left(\binom{1008}{2}+1\right)=2016\cdot 1007+4$ Hence by PHP there exists an element which belongs to at least $1008$ sets. WLOG the element is ${2016}$. Also WLOG $\{A_1,A_2,\dots,A_{1008}\}$ contain $\{2016\}$. For all $1\leq i\leq 1008$, let $B_i=A_i\setminus\{2016\}$. Since $|A_i|=4$, All $B_i$ are $3$-element subsets of $\{1,2,\dots,2015\}$. For all $i\neq j$, $A_i\cap A_j$ is even, so $B_i\cap B_j$ is odd. Hence $|B_i\cap B_j|=1$. But here we showed that there cannot be $1008$ $3$-element subsets of $\{1,2,\dots,2015\}$ such that every two subsets intersect in exactly one element.
PARISsaintGERMAIN
02.10.2017 19:39
this is almost erdos-ko-rado
rafayaashary1
03.10.2017 00:59
PARISsaintGERMAIN wrote: this is almost erdos-ko-rado How so? (Not trying to be rude, genuinely curious )
PARISsaintGERMAIN
07.10.2017 05:06
rafayaashary1 wrote: PARISsaintGERMAIN wrote: this is almost erdos-ko-rado How so? (Not trying to be rude, genuinely curious ) I was just saying that the condition looks similar...
rafayaashary1
07.10.2017 05:09
Ah, I was wondering if perhaps there was an EKR-style solution to the problem. (Even-ness plays a large role, so it seems unlikely :/)