Problem

Source: FKMO 2021 P3

Tags: FKMO, Korea, graph theory, combinatorics



Let $P$ be a set of people. For two people $A$ and $B$, if $A$ knows $B$, $B$ also knows $A$. Each person in $P$ knows $2$ or less people in the set. $S$, a subset of $P$ with $k$ people, is called k-independent set of $P$ if any two people in $S$ don’t know each other. $X_1, X_2, …, X_{4041}$ are 2021-independent sets of $P$ (not necessarily distinct). Show that there exists a 2021-independent set of $P$, $\{v_1, v_2, …, v_{2021}\}$, which satisfies the following condition: For some integer $1 \le i_1 < i_2 < \cdots < i_{2021} \leq 4041$, $v_1 \in X_{i_1}, v_2 \in X_{i_2}, \ldots, v_{2021} \in X_{i_{2021}}$

HIDE: Graph Wording Thanks to Evan Chen, here's a graph wording of the problem Let $G$ be a finite simple graph with maximum degree at most $2$. Let $X_1, X_2, \ldots, X_{4041}$ be independent sets of size $2021$ (not necessarily distinct). Prove that there exists another independent set $\{v_1, v_2, \ldots, v_{2021}\}$ of size $2021$ and indices $1 \le t_1 < t_2 < \cdots < t_{2021} \le 4041$ such that $v_i \in X_{t_i}$ for all $i$.