The Stanley–Wilf conjecture for hereditary properties of tournaments

From papers

Let cmathcalPcmathcal{P} be a hereditary property of tournaments, and let cmathcalPncmathcal{P}_n denote the tournaments in cmathcalPcmathcal{P} on nn vertices. There exists a constant calpha>0calpha>0 and a function F(n)=ncalphan+o(n)F(n)=n^{calpha n+o(n)} such that, for every hereditary property of tournaments cmathcalPcmathcal{P}, either

Pncn|\mathcal{P}_n|\leq c^n

for every nNn\in\mathbb{N} and some constant c=c(P)c=c(\mathcal{P}), or

PnF(n)|\mathcal{P}_n|\geq F(n)

for every nNn\in\mathbb{N}. This conjectures a jump from exponential to factorial speed; the paper presents it as a tournament analogue of the Stanley–Wilf conjecture, and the general assertion remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

József Balogh, Béla Bollobás and Robert Morris, “Hereditary properties of tournaments”, arXiv:math/0702371 (2007).

Solutions 0

No solutions have been posted yet.