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$.Problem
Source: FKMO 2021 P3
Tags: FKMO, Korea, graph theory, combinatorics
20.07.2021 14:18
BUMP!!! it's a great hard problem to deal with...
28.09.2021 20:31
Nobody here? I want to find a solution to this problem.
03.01.2022 22:08
We prove the generalization with $2021$ replaced with $n$ and $4041$ replaced with $2n-1.$ We proceed with strong induction with base case trivial. Take a node $A_1.$ There are two sets that contain $A_1$'s two neighbors $B_1,B_2.$ So $A_1$ is joined to the two nodes $B_1,B_2.$ Otherwise, we put $A_1$ in $P,$ remove all instances of $A_1$ or its neighbors, and induct down. There are three sets that contain $3$ nodes $A_1,A_2,A_3$ that are neighbors of at least one of $B_1,B_2.$ Since $B_1,B_2$ are already joined to $A_1,$ each of the two neighbors of $B_1,B_2$ must be in $A_1,A_2,A_3.$ Otherwise, put $B_1,B_2$ in $P,$ remove all instances of $B_1,B_2$ or their neighbors, and induct down. There are four sets that contain $4$ nodes $B_1,B_2,B_3,B_4$ that are neighbors of at least one of $A_1,A_2,A_3.$ Since $A_1$'s two neighbors are $B_1,B_2$ and $A_2,A_3$ are each joined to one of $B_1,B_2$ each of the two neighbors of $A_1,A_2,A_3$ must be in $B_1,B_2,B_3,B_4.$ Otherwise, put $A_1,A_2,A_3$ in $P,$ remove all instances of $A_1,A_2,A_3$ or their neighbors, and induct down. There are five sets that contain $5$ nodes $A_1,A_2,A_3,A_4,A_5$ that are neighbors of at least one of $B_1,B_2,B_3,B_4.$ Since $B_1,B_2$ are each joined to two of $A_1,A_2,A_3,$ and $B_3,B_4$ are each joined to one of $A_1,A_2,A_3$ each of the two neighbors of $B_1,B_2,B_3,B_4$ have to be in $A_1,A_2,A_3,A_4,A_5.$ Otherwise, put $B_1,B_2,B_3,B_4$ in $P,$ remove all instances of $B_1,B_2,B_3,B_4$ or their neighbors, and induct down. There are six sets that contain $6$ nodes $B_1,B_2,B_3,B_4,B_5,B_6$ that are neighbors of at least one of $A_1,A_2,A_3,A_4,A_5.$ Since $A_1,A_2,A_3$ are each joined to two of $B_1,B_2,B_3,B_4$ and $A_4,A_5$ are each joined to one of $B_1,B_2,B_3,B_4,$ each of the two neighbors of $A_1,A_2,A_3,A_4,A_5$ must be in $B_1,B_2,B_3,B_4,B_5,B_6.$ Otherwise, put $A_1,A_2,A_3,A_4,A_5$ in $P,$ remove all instances of $A_1,A_2,A_3,A_4,A_5$ or their neighbors, and induct down. Continue the process until we get an opportunity to induct downward, or we get $n$ independent sets that each contain the same group of $n$ nodes, but then that's just our $P.$ $\square$
15.08.2022 02:23
My solution is essentially same as the above post, but just posting it as I solved and might help understanding for someone-else. Problem. $G$ be a simple graph with degree of every vertex is $\leq 2$. If there are $2n-1$ independent sets of size $\geq n$, namely $\mathcal{F} = \{X_1 ,\cdots X_{2n-1}\}$ (not necessarily distinct). Then, one can choose independent $n$ vertices from $n$ distinct $I_i$'s. Note that we can assume $V(G)=\cup\mathcal{F}$, since considering induced subgraph of $\cup\mathcal{F}$ makes no difference. Proof. Suppose not. Among counterexamples, choose an instance with smallest $n$. Since the assertion is obviously for $n=1$, $n\geq 2$. If there is a vertex $v$ with degree $\leq 1$, then delete $v$ and neighbor of $v$ (if exists). All sets in $\mathcal{F}$ remain size $\geq n-1$ after the deletion. Choose a set $v\in X$ in $\mathcal{F}$. By minimality of $n$, we can choose independent $n-1$ vertices all from different sets in $\mathcal{F}$ except $X$. Add $v\in X$ makes contradiction! Hence degree of every vertex is $2$ and thus $G$ is a disjoint union of cycles. Claim. If there is a path $P = v_1 \cdots v_{2k-1}$, then there exists at least $k$ sets in $\mathcal{F}$ which contains all $k$ odd-indexed vertices. (name this subfamily of sets by $\mathcal{O}$) proof of claim. Induct in $k$. It's obvious for $k=1$. Assume the assertion holds for $k-1$ and suppose it does not for $k$. Delete vertices $v_1,\cdots,v_{2k-1}$. All sets in $\mathcal{F}\setminus\mathcal{O}$ remain size $\geq n-k+1$ after the deletion. By the induction hypothesis, we can choose $k-1$ even-indexed vertices from $k-1$ sets in $\mathcal{F}$. At least $2n-1-(k-1)-(k-1)=2(n-k+1)-1$ independent sets left after disgarding $\mathcal{O}$ and the sets used for the induction hypothesis. Thus, we can choose $n-k+1$ elements outside $P$ properly. Summing up, we chosed independent $n$ vertices from $n$ sets. Contradiction! $\blacksquare$ Let $C = v_1\cdots v_{m}v_1$ be a cycle in $G$. By the previous claim, there are $[m/2]$ sets where each contain all $[m/2]$ even-indexed vertices. As we did before, we can properly select $n-[m/2]$ vertices outside $C$, not from the prescribed $[m/2]$ sets. Combining it with $[m/2]$ even-indexed vertices, we get contraction! $\square$
12.03.2023 17:12
can these be proved in probabilties method ?
17.12.2023 23:49
We use the graph theoretic interpretation, letting the graph be $G$. First, the degree condition implies any connected component has at most as many edges and vertices, hence is either a tree or a cycle with some (possibly none) disjoint trees attached. Then the degree condition used a bit more closely implies that any cycles can't have anything attached, and any trees must be paths. So the graph is a union of disjoint trees and path (as well as isolated vertices, which can fall under both). We strong induct on the claim that among any $2n-1$ independent sets $X_1,\ldots,X_{2n-1}$ of size $n$, we can pick an independent set $S$ of size $n$ with some matching between its vertices and the $2n-1$ original independent sets (i.e. we can assign each vertex to a different independent set it belongs to). The base case of $n=1$ is trivial. Pick some arbitrary vertex $v$ in some independent set and. We try to add it to $S$, "using" (and thus deleting) some $X_i$. Consider the set $T$ containing $v$ and its neighbors, so $|T| \leq 3$. If there's at most one $X_j$ that contains two vertices then delete this independent set as well, and for the rest remove either the unique vertex in $T \cap X_j$ or an arbitrary vertex and apply the inductive hypothesis, since we have $2n-3$ independent sets of size $n-1$, and all the vertices in them aren't adjacent to $v$. Otherwise, we need $v$ to have two vertices adjacent to it. Try to add the two vertices adjacent to $v$ to $S$, deleting two independent sets that contain both. We try remove $2$ vertices from every other independent subset, such that none of the $\leq 5$ vertices within distance $2$ of $v$ remain. We try to delete independent sets where this isn't possible (which must contain $v$ and both vertices distance $2$ from $v$), which is fine if there are at most $2$ of them. If there are at least $3$ of these "bad" independent sets we repeat the previous step, either finishing or getting at least $4$ of these independent sets. Repeating this over and over again, we eventually reduce to a smaller case covered by inductive hypothesis or find $n$ independent sets containing $n$ vertices (in particular, those whose distance from $v$ is at most $n-1$ and has the same parity as $n-1$); in the latter case we are simply done by taking these $n$ vertices, finishing the problem. $\blacksquare$