The Stanley–Wilf conjecture for hereditary properties of tournaments

About 19 years old · traced to

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

∣Pn∣≤cn|\mathcal{P}_n|\leq c^n

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

∣Pn∣≥F(n)|\mathcal{P}_n|\geq F(n)

for every n∈Nn\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.