The game of plates and olives

• Published in 2017
• Added on 2017-11-30

The game of plates and olives, introduced by Nicolaescu, begins with an empty table. At each step either an empty plate is put down, an olive is put down on a plate, an olive is removed, an empty plate is removed, or the olives on one plate are moved to another plate and the resulting empty plate is removed. Plates are indistinguishable from one another, as are olives, and there is an inexhaustible supply of each. The game derives from the consideration of Morse functions on the $2$-sphere. Specifically, the number of topological equivalence classes of excellent Morse functions on the $2$-sphere that have order $n$ (that is, that have $2n+2$ critical points) is the same as the number of ways of returning to an empty table for the first time after exactly $2n+2$ steps. We call this number $M_n$. Nicolaescu gave the lower bound $M_n \geq (2n-1)!! = (2/e)^{n+o(n)}n^n$ and speculated that $\log M_n \sim n\log n$. In this note we confirm this speculation, showing that $M_n \leq (4/e)^{n+o(n)}n^n$.

Links

• http://arxiv.org/abs/1711.10670v1
• http://arxiv.org/pdf/1711.10670v1

Other information

BibTeX entry

@article{Thegameofplatesandolives,
	key = {Thegameofplatesandolives},
	type = {article},
	title = {The game of plates and olives},
	author = {Teena Carroll and David Galvin},
	abstract = {The game of plates and olives, introduced by Nicolaescu, begins with an empty
table. At each step either an empty plate is put down, an olive is put down on
a plate, an olive is removed, an empty plate is removed, or the olives on one
plate are moved to another plate and the resulting empty plate is removed.
Plates are indistinguishable from one another, as are olives, and there is an
inexhaustible supply of each.
  The game derives from the consideration of Morse functions on the {\$}2{\$}-sphere.
Specifically, the number of topological equivalence classes of excellent Morse
functions on the {\$}2{\$}-sphere that have order {\$}n{\$} (that is, that have {\$}2n+2{\$}
critical points) is the same as the number of ways of returning to an empty
table for the first time after exactly {\$}2n+2{\$} steps. We call this number {\$}M{\_}n{\$}.
  Nicolaescu gave the lower bound {\$}M{\_}n \geq (2n-1)!! = (2/e)^{\{}n+o(n){\}}n^n{\$} and
speculated that {\$}\log M{\_}n \sim n\log n{\$}. In this note we confirm this
speculation, showing that {\$}M{\_}n \leq (4/e)^{\{}n+o(n){\}}n^n{\$}.},
	comment = {},
	date_added = {2017-11-30},
	date_published = {2017-12-07},
	urls = {http://arxiv.org/abs/1711.10670v1,http://arxiv.org/pdf/1711.10670v1},
	collections = {Attention-grabbing titles,Easily explained,Food},
	url = {http://arxiv.org/abs/1711.10670v1 http://arxiv.org/pdf/1711.10670v1},
	urldate = {2017-11-30},
	archivePrefix = {arXiv},
	eprint = {1711.10670},
	primaryClass = {math.CO},
	year = 2017
}