Problem from a graph theory book

Question

Consider any $10$ different positive integers. Prove that you can choose four numbers out of the ten numbers ($a<b<c<d$), such that for any two numbers $x<y\in \{a,b,c,d\}$, $x|y$, or for any two numbers $x<y\in \{a,b,c,d\}$, $x$ is not a divisor of $y$.

Answer 1

This may go outside your view of this problem as a graph theory problem, but there's a more general concept that's being applied here known as Dilworth's Theorem. Think of these numbers forming a digraph, where $(x,y)$ is a directed edge if $x|y$. Note that this digraph has the transitive property, namely that if $(x,y)$ and $(y,z)$ are edges, then $(x,z)$ is also an edge, and the antisymmetric property, that if $(x,y)$ is an edge and $x\neq y$, then $(y,x)$ is not an edge. These all follows from our knowledge of divisibility.

We in fact have a poset structure here, where $x<y$ if $(x,y)$ is an edge. By Dilworth's theorem, the largest antichain is the size of the smallest partition of the poset into chains. If this size is at least $4$, then our size $4$ antichain is a set of elements none of which are related, i.e. none of which divides another. Then assume this size is less than $4$, i.e. at most $3$. Then one of our chains must have size at least $4$. If not, we'd have at most $3$ chains with at most $3$ elements each, meaning we have at most $9$ elements, a contradiction. Then our chain of size at least $4$ is a set of numbers where for each pair, one divides the other. This is where your intuition comes in- we need $10$ because it exceeds $3\times 3$.