DIMACS logo

Jan Kára

I'm student of Computer science on Faculty of Maths and Physics of Charles university in Prague. I'm in the fifth year of the study, so I'm finishing my thesis now. I'm interested in graphs, combinatorics, computational complexity and discrete geometry.

I'm working together with Ales, Ida, Jakub, Robert, Tomas and Vitek. Our advisor is prof. Joseph Beck. The chief of our Prague group is Robert Samal.

Our REU project proposed to us by our mentor Joszef Beck is so called Clique Game. The game is played on the clique with infinitely many vertices (ie. graph with infinitely many vertices in which any two vertices are joined by an edge). The players are alternating in their moves and in each move player chooses uncolored edge and colors it with his/her color. The goal of each player is to create a K4 (complete graph on four vertices) in his color.

On finite board of sufficient size it is an easy consequence of Ramsey theorem that the first player must win. On infinite board however this is not known. The goal of our project is to determine whether the game on infinite board is also a first-player's win or if it is a draw. We would also like to find some easy-to-describe strategy either for the first player to win or for the second player to force a draw.

Currently it seems that the game on the infinite board is the first-player's win and we should be able to create reasonable strategy for him (this strategy will then be usable on a sufficiently large board which will solve other open problem). We are now working on simplifying and proving our strategy for the first player.

For our work we used the book being written by Joszef Beck: Combinatorial Games


You can look at my personal homepage, which is unfortunately in czech.