Interesting Esoterica

The topology of competitively constructed graphs

Article by Frieze, Alan and Pegden, Wesley
  • Published in 2013
  • Added on
We consider a simple game, the $k$-regular graph game, in which players take turns adding edges to an initially empty graph subject to the constraint that the degrees of vertices cannot exceed $k$. We show a sharp topological threshold for this game: for the case $k=3$ a player can ensure the resulting graph is planar, while for the case $k=4$, a player can force the appearance of arbitrarily large clique minors.

Links

Other information

pages
9

BibTeX entry

@article{Frieze2013,
	title = {The topology of competitively constructed graphs},
	author = {Frieze, Alan and Pegden, Wesley},
	url = {http://arxiv.org/abs/1312.0964 http://arxiv.org/pdf/1312.0964v2},
	urldate = {2013-12-30},
	abstract = {We consider a simple game, the {\$}k{\$}-regular graph game, in which players take turns adding edges to an initially empty graph subject to the constraint that the degrees of vertices cannot exceed {\$}k{\$}. We show a sharp topological threshold for this game: for the case {\$}k=3{\$} a player can ensure the resulting graph is planar, while for the case {\$}k=4{\$}, a player can force the appearance of arbitrarily large clique minors.},
	comment = {},
	month = {dec},
	pages = 9,
	year = 2013,
	archivePrefix = {arXiv},
	eprint = {1312.0964},
	primaryClass = {math.CO},
	collections = {Games to play with friends,Protocols and strategies}
}