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

About 19 years old · traced to

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 k∈Nk\in\mathbb{N}, or

∣Pn∣≥Fn∗|\mathcal{P}_n|\geq F_n^*

for every n∈Nn\in\mathbb{N} with n≠4n\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.

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.