All Questions
Tagged with combinatorial-game-theory graph-theory
4 questions
69
votes
7
answers
17k
views
What is a chess piece mathematically?
Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...
52
votes
4
answers
10k
views
Do there exist chess positions that require exponentially many moves to reach?
By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an $n\...
20
votes
1
answer
1k
views
A Ramsey avoidance game
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 ...
18
votes
2
answers
3k
views
Determine or estimate the number of maximal triangle-free graphs on $n$ vertices
Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
http://www.math.ucsd.edu/~erdosproblems/erdos/...