Timeline for Chains or Antichains slowly increasing
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 23, 2013 at 22:26 | answer | added | Douglas Zare | timeline score: 4 | |
| Apr 23, 2013 at 0:44 | vote | accept | ilcapu | ||
| Apr 22, 2013 at 23:07 | answer | added | Gerhard Paseman | timeline score: 3 | |
| Apr 22, 2013 at 20:26 | comment | added | Gerhard Paseman | The problem is to make a subsequence with indices that do not grow quickly. Suppose I decide to make an increasing sequence and pick a_1000. If the next 2^1000 terms are less than sigma(a_1000), I am unlikely to pick a_1001 to look like (1001)^2. Having finitely many obstructions like this does not matter, but since his step size is recursively bounded, I can come up with infinitely many such obstructions and eventually defeat his O condition. There may be a version which defeats arbitrary recursive bounds too. Gerhard "Or Try Sine Of Log" Paseman, 2013.04.22 | |
| Apr 22, 2013 at 19:52 | comment | added | François G. Dorais | Gerhard, I'm not convinced by your argument since every sequence of length $n$ has a monotone subsequence of length about $\sqrt{n}$. Still, I think $O(n^2)$ is too optimistic for the infinite case. | |
| Apr 22, 2013 at 18:43 | comment | added | Gerhard Paseman | Also, one can extend the example to find an injection sigma such that there is no set A with analogous properties, where n^2 is replaced by any primitive recursive function. Gerhard "That Should Make Enough Counterexamples" Paseman, 2013.04.22 | |
| Apr 22, 2013 at 18:24 | comment | added | Gerhard Paseman | Not likely. Consider listing the dyadic rationals by denominator first. Gerhard "Or Think Of Farey Fractions" Paseman, 2013.04.22 | |
| Apr 22, 2013 at 18:01 | history | asked | ilcapu | CC BY-SA 3.0 |