  We prove that a uniformly random automaton with $n$ states on a 2-letter
alphabet has a synchronizing word of length $O(n^{1/2}\log n)$ with high
probability (w.h.p.). That is to say, w.h.p. there exists a word $\omega$ of
such length, and a state $v_0$, such that $\omega$ sends all states to $v_0$.
Prior to this work, the best upper bound was the quasilinear bound
$O(n\log^3n)$ due to Nicaud (2016). The correct scaling exponent had been
subject to various estimates by other authors between $0.5$ and $0.56$ based on
numerical simulations, and our result confirms that the smallest one indeed
gives a valid upper bound (with a log factor).
  Our proof introduces the concept of $w$-trees, for a word $w$, that is,
automata in which the $w$-transitions induce a (loop-rooted) tree. We prove a
strong structure result that says that, w.h.p., a random automaton on $n$
states is a $w$-tree for some word $w$ of length at most
$(1+\epsilon)\log_2(n)$, for any $\epsilon>0$. The existence of the (random)
word $w$ is proved by the probabilistic method. This structure result is key to
proving that a short synchronizing word exists.
