Timeline for Sets of points containing permutations - a Ramsey-type question
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2016 at 14:25 | comment | added | Ben Barber | @LászlóKozma, please do post an answer if you'd like to explain the connection. | |
| Apr 16, 2016 at 12:47 | comment | added | László Kozma | It seems that the asymptotics of $f(n)$ is $n^2$, up to a polylog factor, 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 18:25 | comment | added | László Kozma | Very nice - so, together with Ilya Bogdanov's answer the bounds $3n-\epsilon < f(n) \leq n^2$ follow. It seems interesting now to try narrowing the gap. | |
| Jan 31, 2015 at 3:52 | comment | added | The Masked Avenger | It breaks down at n=2, with a coloring in which l is at most 1 and k at most 2. Take the main and lower diagonals as 7 elements of one color. | |
| Jan 30, 2015 at 19:37 | comment | added | Gerhard Paseman | Try the following induction and see where it breaks down: Every coloring of a 2n by 2n square has all k permutations contained by blacks squares and all l permutations contained by white squares, where k+l >= 2n. Gerhard "It Can't Be That Easy?" Paseman, 2015.01.30 | |
| Jan 30, 2015 at 18:59 | comment | added | Tony Huynh | Nice. Much better than my answer. | |
| Jan 30, 2015 at 18:09 | history | answered | Ben Barber | CC BY-SA 3.0 |