Consider the poset such that $a$ is related to $b$ iff $a$ divides it. then there is an antichain of size $n+1$ or a chain of size $n+1$. since there is no antichain, because they say that if i pick $n+1$ elements there are always to related, then there is a chain of size $n+1$, and this chain gives the desired set...I think it already appeared in the forum, right?

Allow me please to express my sincere doubts about the quality of the given problems.

harazi wrote: Allow me please to express my sincere doubts about the quality of the given problems. he-he

I feel some irony around...

Pascual2005 wrote: Consider the poset such that $a$ is related to $b$ iff $a$ divides it. then there is an antichain of size $n+1$ or a chain of size $n+1$. How can you prove this?

perfect_radio wrote: Pascual2005 wrote: Consider the poset such that $a$ is related to $b$ iff $a$ divides it. then there is an antichain of size $n+1$ or a chain of size $n+1$. How can you prove this? Did you see topic's title? It is "dilworth particularization"!!!

-feels out of depth-

Whats "dilworth particularization"? In the fact we must prove that $r(n,n+1)\geq n^2+1$!!($r(k,l)$ are Ramsey's numbers).

Just use Dilworth's Theorem on the poset of the divisibility lattice. By Dilworth's Theorem the smallest partitioning of $X$ into chains has a number of elements equal to the cardinality of same antichain. As we are given no antichains have more than $n$ elements, it follows by pigeonhole some chain has at least $\left \lceil \frac{n^2+1}{n} \right \rceil = n+1$ elements, as desired.

Valentin Vornicu wrote: Let $n\geq 1$ be an integer and let $X$ be a set of $n^2+1$ positive integers such that in any subset of $X$ with $n+1$ elements there exist two elements $x\neq y$ such that $x\mid y$. Prove that there exists a subset $\{x_1,x_2,\ldots, x_{n+1} \} \in X$ such that $x_i \mid x_{i+1}$ for all $i=1,2,\ldots, n$. Consider the problem setup in graph theoretical language. A directed edge $x \rightarrow y$ is drawn iff $x \mid y$. Now from the given condition we have that the size of the maximal anti-chain of the graph is, clearly, at most $n$. So by Dilworth's theorem it follows that the minimum number of disjoint directed paths the graph can be split into is at most $n$. Consequently, one of them contains a chain of size $\left\lfloor \frac{n^2+1}{n} \right\rfloor\ = n+1.$

Suppose there is no $n+1$-size subset $\{x_1,x_2,\ldots, x_{n+1} \}$such that no $x_i|x_{i+1}$ for all $i$. We claim that all the points of $X$ can be partitioned into $n$ subsets such that in each subset we can't find two $a,b$ such that $a|b$. Proof:Proceed by induction on $n$.Suppose $X$ has no subset $\{x_1,x_2,...,x_{m+1}\}$ of size $m+1$ such that $x_i|x_{i+1}$.Consider all the subsets of $X$ with maximum length such that each subset is a $chain$; meaning if $\{x_1,x_3,...,x_r\}$ is a such subset then $x_i|x_{i+1}$ Now let $S$ be the set with all maximum number from each maximum chain.We note that in $S$ no two elements devide one another. If $X-S$ has a $m$- length chain then this is a maximum chain in $X$ also since $X$ has no $m+1$- length chain.So maximum of this chain $a$ is in $S$ as well.So it's not in $X-S$.Contradiction.So $X-S$ has no chain with length $m$.By induction hypothesis, $X-S$ is union of $m-1$ length set in which no $a|b$.And together with $S$ ,$X=X-S\cup S$ is union of $m$ such subset. So X is union of $n$ subsets in each which no $a|b$.So by php one of them is of length $\left\lfloor \frac{n^2+1}{n} \right\rfloor\ = n+1.$ Contradiction. So our initial assumption was wrong.

Wonderful application and a Direct Consequence of Dilworth's Theorem - Dilworth Theorem - Consider graph $\mathcal{G}$ ,which is directed acyclic , then consider a set of vertices $\mathcal{V}$ of $\mathcal{G}$ such that there doesn't exist any directed path between any $2$ vertices in $\mathcal{V}$. Then maximum possible size of $\mathcal{V}$ is same as minimum number of disjoint paths , in which $\mathcal{G}$ can be decomposed. Now , suppose we represent $n^2+1$ numbers as vertices in $\mathcal{G}$ , and there is a directed edge from $V_i$ to $V_j$ if and only if $ i \mid j $ , so for any subgraph $\mathcal{S}$ of $\mathcal{G}$ , with $n+1$ vertices, there exist atleast one directed edge. $\clubsuit$ Now we want a path of size atleast $n+1$ in $\mathcal{G}$ , suppose assume the opposite . Then suppose minimum number of disjoint paths in which $\mathcal{G}$ can be decomposed is $k$ , then from our assumption $ nk \ge n^2 + 1$ , or $k \ge n +1$ . Now we claim that there doesn't exist an directed cycle in $\mathcal{G}$ , suppose it exist , let vertex encountered be $x_1 , x_2 , .... x_i$ , then from definition of $\mathcal{G}$ , $x_1 \mid x_2 \mid x_3 ,........\mid x_i \mid x_1$ , but this leads to all numbers being equal , A contradiction. Now from Dilworth's Theorem ,we get a subgraph $\mathcal{X}$ of $\mathcal{G}$ such that there is no directed edge between any $2$ vertices , having size atleast $k = n+1$. A Contradiction to $\clubsuit$. Hence we are done.

Let $G$ be the directed graph on $X$ such that an edge $x \rightarrow y$ is placed iff $x \mid y$. The problem condition implies that the maximum antichain of $G$ has size at most $n$. Thus, Dilworth's theorem yields that the minimum number of disjoint chains $G$ can be split into is at most $n$, so by Pigeonhole there is some chain of size at least $\left \lceil \frac{n^2+1}{n} \right \rceil = n+1$, as desired.

storage