At most how many $42$-element subsets of $\{1,2,\dots,2018\}$ are such that, for any two, one consists of the $42$ smallest elements of their union?

Question

Here is a problem based on a problem from Kurdhak Jozsef Hungarian mathematical olympiad 2016. This problem is easier than that, and I hope there exist an easier solution for this problem than the olympiad problem’s solution.

At most how many $42$-element subsets can we select from $\{1,2,\dots,2018\}$ such that for any two selected subsets, one of the subsets consists of the $42$ smallest elements of their union?

Note that in the original problem, the numbers $42,2018$ are not given.

Answer 1

Claim. Let $n$ and $k$ be arbitrary positive integers such that $n\geq k$. Let $\mathcal{S}$ denote the set of all $k$-subsets of $[n]:=\{1,2,\ldots,n\}$. Suppose that $\mathcal{C}$ is a subcollection of $\mathcal{S}$ such that, for any $A,B\in\mathcal{C}$, either $A$ or $B$ is composed by the $k$ smallest elements of $A\cup B$. Then, $$|\mathcal{C}|\leq n-k+1$$ and the inequality is sharp.

It is easy to see that the inequality is sharp. The subfamily $$\big\{\{1,2,\ldots,k-2,k-1,j\}\,\big|\,j\in\{k,k+1,k+2,\ldots,n\}\big\}$$ satisfies the requirement, and it contains $n-k+1$ sets.

Partially order $\mathcal{S}$ by decreeing that, for $A,B\in \mathcal{S}$, $A\leq B$ if $A$ consists of the $k$ smallest elements of $A\cup B$. It is easy to see that $\leq$ is indeed an order relation. The question is to determine the size $s$ of the largest chain in $\mathcal{S}$. We know from the previous paragraph that $s\geq n-k+1$.

By Mirsky's Theorem, $s$ equals the smallest number of antichains in $\mathcal{S}$ which form a partition of $\mathcal{S}$. Hence, if we can exhibit $n-k+1$ antichains that partition $\mathcal{S}$, then we will have proven that $s=n-k+1$.

For $j=k,k+1,k+2,\ldots,n$, let $\mathcal{A}_j$ denote the subset of $\mathcal{S}$ consisting of sets $A$ such that the maximum element of $A$ is $j$. It is easy to see that $\mathcal{A}_j$ is an antichain. Furthermore, the sets $\mathcal{A}_k,\mathcal{A}_{k+1},\mathcal{A}_{k+2},\ldots,\mathcal{A}_{n}$ form a partition of $\mathcal{S}$. The proof is now complete.

In particular, for the problem at hand, $n=2018$ and $k=42$. Therefore, the largest possible collection of $42$-subsets of $\{1,2,\ldots,2018\}$ with the desired property has $$2018-42+1=1977$$ elements.

---

Generalization. Let $n$, $m$, and $k$ be arbitrary positive integers such that $n\geq m\geq k$. Let $\mathcal{S}$ denote the set of all $m$-subsets of $[n]:=\{1,2,\ldots,n\}$. Suppose that $\mathcal{C}$ is a subcollection of $\mathcal{S}$ such that, for any $A,B\in\mathcal{C}$, either $A$ or $B$ contains the $k$ smallest elements of $A\cup B$. Then, $$|\mathcal{C}|\leq \binom{n-k+1}{m-k+1}$$ and the inequality is sharp.

I decided to give a proof of the generalization above, since the proof here does not extend from the proof above in a very straightforward manner. First of all, the inequality is sharp because the family $$\Big\{\{1,2,\ldots,k-1\}\cup X\,\Big|\,X\subseteq\{k,k+1,k+2,\ldots,n\}\text{ and }|X|=m-k+1\Big\}$$ fulfills the requirement.

Write $\mathcal{T}$ for the family of all subsets of $[n]$ with $m-k$ elements. Equip $\mathcal{T}$ with any total order $\preceq$. Next, we define a partial order $\leq$ on $\mathcal{S}$ as follows. Let $A$ and $B$ be arbitrary elements of $\mathcal{S}$. We say that $A\leq B$ if both conditions below are satisfied:

• $A$ contains the smallest $k$ elements $t_1,t_2,\ldots,t_k$ in $A\cup B$, and
• either $|A\setminus Z|<|B\setminus Z|$, where $Z:=\{t_1,t_2,\ldots,t_k\}$, or $|A\setminus Z|=|B\setminus Z|=m-k$ and $(A\setminus Z)\preceq (B\setminus Z)$.

It is not difficult to show that $\leq$ is indeed a partial order on $\mathcal{S}$.

The rest goes as before. We only need to find $\displaystyle\binom{n-k+1}{m-k+1}$ antichains in $\mathcal{S}$ that form a partition of $\mathcal{S}$. Let $\mathcal{F}$ denote the family of $(m-k+1)$-element subsets of $\{k,k+1,k+2,\ldots,n\}$. For each $F\in\mathcal{F}$, define $\mathcal{A}_F$ to be the subcollection of $\mathcal{S}$ consisting of sets whose $m-k+1$ largest elements belong to $F$. Then, the subcollections $\mathcal{A}_F$ for $F\in\mathcal{F}$ are antichains that partition $\mathcal{S}$, and Mirsky's Theorem finishes the proof.