Erdős Problem #1216 — The minimum guaranteed transitive subtournament

About 62 years old · traced to 1964

Let $f(n)$ be the largest integer such that every tournament on $n$ vertices contains a transitive subtournament on $f(n)$ vertices. Is $f(n)=⌊\log_2 n⌋+1$ ?

References

Primary source

P. Erdős and L. Moser, On the representation of directed graphs as unions of orderings, A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 9 (1964), 125–132.

Additional references

P. Erdős and L. Moser, On the representation of directed graphs as unions of orderings, A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 9 (1964), 125–132.

graph-theory ramsey-theory

InErdős Problems

Posted 1 month ago

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.

No solutions have been posted yet.