The polynomial-to-factorial speed jump for hereditary properties of oriented graphs

Let cmathcalPcmathcal{P} be a hereditary property of oriented graphs, and let cmathcalPncmathcal{P}_n denote its members on nn vertices. Then either

Pn=Θ(nk)|\mathcal{P}_n|=\Theta(n^k)

for some kNk\in\mathbb{N}, or

PnFn|\mathcal{P}_n|\geq F_n^*

for every nNn\in\mathbb{N} with n4n\neq4.

Conjecture on oriented-graph speeds. This predicts a jump from polynomial to at least factorial speed for unlabelled hereditary properties of oriented graphs. The paper poses it as a possible extension of its tournament results, and no resolution is supplied.

Sources & referencesView supporting material

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.