As far as I know, it is an unsolved question whether or not this is true:
If $G$ is
a directedan oriented graph, $G^2$ always has some node whose outdegree is at least double that of its outdegree in $G$.
For example, below vertex $10$ has outdegree $3$ in $G$ and $5$ in $G^2$. The maximum outdegree-ratio increase of $3.5$ is achieved by vertex $15$, which has outdegree $2$ in $G$ and $7$ in $G^2$. Of course there are also vertices, such as $2$ in $G$, that have zero-outdegree, and so their outdegree trivially doubles and satisfies the above hypothesis.
A directed graph $G$ on $n=15$ nodes; and $G^2$.
My question is:
Q. Is the expected maximum (finite) outdegree increase from $G$ to $G^2$ known to grow logarithmically in $n$, for random directed graphs generated by including each of the $2\binom{n}{2}$ directed edges with fixed probability $p$?
Simulations suggest this may be true:
The maximum (finite) outdegree ratio increase, for $n$-node random graphs, each edge included with probability 3%.
Each point is an average of $5$ simulations. The illustrated curve is logarithmic.