On the size of temporal cliques in subcritical random temporal graphs

A random temporal graph is an Erd{o}s-R\'enyi random graph $G(n,p)$, together with a random ordering of its edges. A path in the graph is called increasing if the edges on the path appear in increasing order. A set S of vertices forms a temporal clique if for all u,v ∈ S, there is an increasing path from u to v. {Becker2023} proved that if p=clog n/n for $c>1$, then, with high probability, there is a temporal clique of size $n-o(n)$. On the other hand, for $c<1$, with high probability, the largest temporal clique is of size $o(n)$. In this note we improve the latter bound by showing that, for $c<1$, the largest temporal clique is of constant size with high probability.