On the size of temporal cliques in subcritical random temporal graphs

Source abstract

Abstract A random temporal graph is an Erdős-Rényi 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 \in S$ , there is an increasing path from $u$ to $v$ . Becker, Casteigts, Crescenzi, Kodric, Renken, Raskin and Zamaraev [(2023) Giant components in random temporal graphs. arXiv,2205.14888] proved that if $p=c\log n/n$ for $c\gt 1$ , then, with high probability, there is a temporal clique of size $n-o(n)$ . On the other hand, for $c\lt 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\lt 1$ , the largest temporal clique is of constant size with high probability.