Why are non-deterministic Buchi automata factorially succinct when compared to deterministic Rabin Automata?

I am trying to demonstrate the following idea without success.


There are infinitely many $n \in \mathbb{N}$ such that: There is a
non-deterministic Buchi automata of size $n$ such that a deterministic Rabin Automata
accepting the same language has at least $n!$ states.

Any help would be appreciated

This is Theorem 1.30 in the chapter "Omega-Automata" in the book "Automata, Logics, and Infinite Games: A Guide to Current Research" edited by Erich Grädel, Wolfgang Thomas and Thomas Wilke. They have a proof as well (and a literature referene to the original publication).

Note that instead of the nondeterminstic Buchi automaton having $n$ states, it needs to have $O(n)$ states to make the proof work. The problem is then defined slightly differently to make this precise.

Note that it is a bit confusing if you write "Buchi automata" and "deterministic Rabin automata" in the same question if the former are meant to be "nondeterministic Buchi automata". There is ample work both on deterministic and non-deterministic Buchi automata, so spelling out which variant is meant is important.

StackExchange Computer Science Q#91159, answer score: 5