2024/04/06 by Atamanchuk, Caelan, Devroye, Luc, Lugosi, Gabor · 2 citations
#FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2404.04462
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 ∈ S, there is an increasing path from u to v. \citeBecker2023 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.