Timeline for Sets of points containing permutations - a Ramsey-type question
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 3, 2016 at 16:06 | comment | added | László Kozma | @IlyaBogdanov: Yes, the idea is to use the result from the paper that an (ordered) complete graph can be edge-colored with two colors, such that some ordered matching is avoided in both colors. If we restrict the complete graph to a complete bipartite graph, avoiding the matching should become easier. | |
| Jun 3, 2016 at 15:32 | comment | added | László Kozma | Sorry, I meant N(k) = k^2, over some polylog(k). I'll think through the argument again and add it as a solution if I can make sense of it. | |
| May 19, 2016 at 13:47 | comment | added | Ilya Bogdanov | @LászlóKozma: Surely $N(k)$ should be greater than $k$; dod you mean $k\sqrt{k}$, $k^2$ or something else? Also, I do not see how to apply the results; it seems that we need indeed find an ordered matching, but in a (trivially ordered) complete 2-partite graph. | |
| Apr 16, 2016 at 12:46 | comment | added | László Kozma | It seems that the asymptotics of N(k) is sqrt(k) up to polylog-factors, based on the results from "Ordered Ramsey numbers" by David Conlon, Jacob Fox, Choongbum Lee, Benny Sudakov. (hint from Martin Balko) arxiv.org/abs/1410.5292 | |
| Feb 1, 2015 at 19:21 | comment | added | Ilya Bogdanov | Still, perhaps it would be better to wait for a more sharp estimate. It is interesting to know the asymptotics of $N=N(k)$ such that in every black and white coloring of $N\times N$ square one of the colors contains every $k$-permutation. Not speaking on more colors... | |
| Feb 1, 2015 at 18:27 | comment | added | László Kozma | Very nice, I think I will accept this answer, as it disproves the original n/2 conjecture of the question. But now it seems interesting to try narrowing the gap between this and the one from Ben Barber's answer. | |
| Jan 31, 2015 at 18:03 | comment | added | The Masked Avenger | Interesting. I wonder how low (k+l) can go, using the notation in Paseman's comment. | |
| Jan 31, 2015 at 9:29 | comment | added | Wolfgang | I think you must switch "black" and "white". | |
| Jan 31, 2015 at 8:58 | history | answered | Ilya Bogdanov | CC BY-SA 3.0 |