The polynomial-to-factorial speed jump for hereditary properties of oriented graphs
The polynomial-to-factorial speed jump for hereditary properties of oriented graphs
Let be a hereditary property of oriented graphs, and let denote its members on vertices. Then either
for some , or
for every with .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.