Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not colored edge blue or red. The goal is to avoid monochromatic $K_k$. The first player who completes a monochromatic $K_k$ loses. If $n$ is large enough the Ramsey theorem ensures that there can be no draw. Therefore someone has a winning strategy. My question is that:

Is there any pair $(n,k)$ such that $n<R(k,k)$ but in the corresponding game one of the players has a winning strategy? (Since Ramsey type questions tend to be very hard, even non trivial heuristics are appreciated!)

Additional infrmation: For $k=3, n=6$ (it is different from the game called Sim!) we played it for a few hours, and found that the second player wins a lot more than the first. After that we found out that the very similar game Sim is solved by computer and the second player has a winning strategy (not presented in the paper): http://arxiv.org/pdf/cs/9911004v1.pdf
When playing with $k=3, n=5$ i think that there is no winning strategy for anyone, but i can't prove it yet. I think that this must be present somewhere in the literature. Interesting observations are: The maximal red subgraphs without a triangle are: a star, a cycle of length four plus a vertex adjacent to two nonadjacent vertices in the 4-cycle, and a cycle of length $5$. (Their maximal degrees are 4,3,2 respectively) I think that given enough time we could prove that the first player who makes a vertex with $3$ monochromatic edges loses. (Maybe with maintaining that the red and blue subgraphs are isomorphic.)

share|improve this question
    
"...coloring its edges": You mean: "coloring its vertices"? –  Joseph O'Rourke Sep 30 '13 at 0:16
    
No, if we color vertices the game (sadly) is not that interesting. I corrected the 'mistyped' word. Thank you! –  Daniel Soltész Sep 30 '13 at 0:26
2  
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$. –  Noam D. Elkies Sep 30 '13 at 0:55
1  
@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). –  Ben Barber Sep 30 '13 at 9:17
1  
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. –  domotorp Oct 2 '13 at 6:01
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.