On the size of temporal cliques in subcritical random temporal graphs

• Authors: Caelan Atamanchuk, Luc P Devroye and Gábor Lugosi.
• Combinatorics, Probability and Computing, Vol. 34, No. 5, 671-679, June 2025.

A random temporal graph is an Erd?os-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 ? 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 >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