Timeline for A Ramsey avoidance game
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2014 at 12:50 | vote | accept | Daniel Soltész | ||
| Jun 22, 2014 at 12:50 | history | edited | Daniel Soltész | CC BY-SA 3.0 |
deleted 1095 characters in body
|
| Jun 10, 2014 at 1:23 | comment | added | Nate Eldredge | @zack: Ah, thanks. I misunderstood the game. I'll delete my comment. | |
| Jun 9, 2014 at 22:17 | comment | added | Zack Wolske | @Nate: Both players have the option to use either colour, so the number of sequences (with $m={n \choose 2 }=|E|$) is $2^m \cdot m!$. That's $3.7$ billion for $n=5$, though you can immediately drop a factor of $2m$ and make a few further simplifications from symmetries. It's small enough to brute force with $k=3$ (the hard part was combining moves into a readable strategy), but $k=4$, $n \leq 17$ is a long way off. | |
| Jun 9, 2014 at 20:00 | comment | added | The Masked Avenger | Even using naive optimization techniques (e.g. not labeling vertices until they have been chosen), I suspect the game tree for n at most 10 to be computationally feasible. | |
| Jun 9, 2014 at 5:58 | answer | added | Zack Wolske | timeline score: 20 | |
| Oct 2, 2013 at 6:01 | comment | added | domotorp | Maybe you know it, but in the $k=3, n=6$ game, the second player loses if he starts with an edge independent to the first player's first move. This is because the first player can pick the third edge that makes a matching and then use a mirroring strategy. | |
| Sep 30, 2013 at 20:27 | comment | added | Flo Pfender | If the first player in the 5/3 has a winning strategy, it is to build a C_4 plus pending edge. No matter how stupid he plays, he will always be able to place a 4th edge without creating a triangle, so he can not lose before the 5th edge. And if he has an "at least tie" strategy, it is to build either C_4+pending or C_5. | |
| Sep 30, 2013 at 14:21 | comment | added | Suvrit | @Ben: Ah...ok! thanks for the clarification. | |
| Sep 30, 2013 at 9:17 | comment | added | Ben Barber | @suvrit The Ramsey game is different: there you have players Red and Blue who take turns to choose edges of their own colour, and whose goal is to create a monochromatic clique. The Ramsey game (for equal clique sizes) can never be a second player win, by strategy stealing (which does not work here). | |
| Sep 30, 2013 at 1:34 | comment | added | Daniel Soltész | @NoamD.Elkies Well, i think the $2$ player game is hard enough. It would also be interesting if there are games with the same rules, but more players, and one of them has a winning strategy for a smaller graph than the corresponding Ramsey number. But honestly, i feel a little uncomfortable for asking even this question because of its difficulty. | |
| Sep 30, 2013 at 1:33 | comment | added | Suvrit | Perhaps you already know this: Except for an inverted definition of winning, this seems to be the "Ramsey game" defined on page 3 of sciencedirect.com/science/article/pii/0097316573900058 --- where they also mention the case when the game is a draw (which by symmetry should also hold for your game?) ... | |
| Sep 30, 2013 at 0:55 | comment | added | Noam D. Elkies | Why use only two equivalent colors? A natural generalization: fix $c\geq 2$ and $k_1,\ldots,k_c$ each at least $3$; two players alternate coloring a previously uncolored edge one of $c$ colors, and lose by completing a monochromatic $K_{k_i}$ of color $i$. The case $c=k_1=k_2=k_3=3$, $n=17$ is mentioned in the Wikipedia page en.wikipedia.org/wiki/Sim_(pencil_game) . One could also ask the same question for the game where one wins by completing a a monochromatic $K_{k_i}$ of color $i$. | |
| Sep 30, 2013 at 0:26 | comment | added | Daniel Soltész | No, if we color vertices the game (sadly) is not that interesting. I corrected the 'mistyped' word. Thank you! | |
| Sep 30, 2013 at 0:24 | history | edited | Daniel Soltész | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Sep 30, 2013 at 0:16 | comment | added | Joseph O'Rourke | "...coloring its edges": You mean: "coloring its vertices"? | |
| Sep 30, 2013 at 0:01 | history | edited | Daniel Soltész | CC BY-SA 3.0 |
added 17 characters in body
|
| Sep 29, 2013 at 22:27 | history | asked | Daniel Soltész | CC BY-SA 3.0 |