divisibility independence The following is a standard combinatorics question:

Any set of $n+1$ numbers from $1, \dotsc, 2n$ contains a pair of
  numbers $a, b$ where $a \left| b \right.$

The argument is by pigeonhole principle: consider $A_i = \{2^k (2i-1), k\in \mathbb{N}\}.$ The sets $A_i$ cover $1, \dotsc, 2n,$ and there are $n$ of them. 
The question is this: to find the maximal division-free set, the obvious way is to do the following (in Mathematica):
divGraph[n_] := With[{pairs = Subsets[Range[n], {2}]},
  With[{divis = Select[pairs, Mod[#[[2]], #[[1]]] == 0 &]},
   Graph[Apply[Rule, #] & /@ divis]]]

FindIndependentSet[divGraph[n]]

Now, when one runs this for smallish numbers one sees that the maximal set $S_m(2n)$ always has cardinality $n,$ but also, the minimum of $S_m(2n)$ is equal to 


*

*1 once

*2 thrice

*4 nine times

*8 $27$ times

*16 $81$ times

*32 $243$ times


And so on. The question is: what is going on? Is this the true size of the minimal element of $S_m?$ As Vladimir Dotsenko points out, the obvious example has the minimum equal to $n+1.$
 A: First, I ran some bruteforce myself (I don't have access to Mathematica at the moment), and I'm fairly sure the mysterious numbers obtained in OP ($1, 2, 2, 2, 4\ldots$) are the minimal possible numbers that are present in any $S_m(2n)$. I'm going to explain the pattern in this assumption.
Long story short, the minimal possible number in $S_m(n)$ is $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor}$.
As follows from the OP's explanation, for any odd number $x \leq n$ there is exactly one representative of form $x 2^k$ in any $S_m(n)$. Let us call the exponent $k = d(x)$ the degree of $x$ in a particular $S_m(n)$. Obviously, for non-equal $x \vert y$ we must $d(x) > d(y)$.
One can see that the "critical" values where the OP's minimal numbers change are exactly $\frac{3^k + 1}{2}$, that is, the minimum changes whenever a new power of 3 arrives in the set. One can indeed see that in any $S_m(n)$ we have $d(1) \geq \left\lfloor \frac{\log n}{\log 3} \right\rfloor = k_0$ by simply applying the inequality above for a divisor chain $1 \vert 3 \vert \ldots \vert 3^{k_0}$. The numbers $2^{k_0}$ follow the OP's pattern exactly.
But why any number that is not a binary power cannot be less than $2^{k_0}$ in an $S_m(n)$? Let $1 < x \leq n$ be an odd number. Then for any $S_m(n)$ the numbers $\{2^{d(x)}, 3\cdot 2^{d(3x)}, \ldots\}$ must be an $S_m(\left\lfloor \frac{n}{x} \right\rfloor)$. As we have shown above, that implies $d(x) \geq \left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right \rfloor$. It suffices to show $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor} < x \cdot 2^{\left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor}$. But $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor - \left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor} \leq 2^{\frac{\log x}{\log 3} + 1} = 2 \cdot x^{\frac{\log 2}{\log 3}} < x$ for all $x > 5$ (for $x = 3, 5$ we may still have the claim by handling the rounding error more carefully).
To finish the proof, notice that the set $\{x \cdot 2^{\left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor}\}$ with $x$ ranging over odd numbers at most $n$ is an $S_m(n)$. Note that this set is minimal with respect to any measure, e.g. no proper divisor of any of its elements can be in an $S_m(n)$, hence it's also lexicographically minimal when sorted.
