Title: On the size of temporal cliques in subcritical random temporal graphs Show Chinese title

Title: 关于次临界随机时间图中时间团的大小

Abstract: A \emph{random temporal graph} is an Erd\H{o}s-R\'enyi random graph $G(n,p)$, together with a random ordering of its edges. A path in the graph is called \emph{increasing} if the edges on the path appear in increasing order. A set $S$ of vertices forms a \emph{temporal clique} if for all $u,v \in S$, there is an increasing path from $u$ to $v$. \cite{Becker2023} 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 \emph{constant} size with high probability. Show Chinese abstract

Abstract: 一个\emph{随机时间图}是一个Erdős-Rényi随机图$G(n,p)$，连同其边的随机排序。 图中的路径如果边按递增顺序出现，则称为\emph{增加的}。 一个顶点集合 $S$ 形成一个 \emph{时间团簇} 当且仅当对于所有的 $u,v \in S$，存在从 $u$ 到 $v$ 的一条递增路径。 \cite{Becker2023} 证明了如果对于$c>1$，$p=c\logn/n$成立，则以高概率存在一个大小为$n-o(n)$的时间动态完全图。 另一方面，对于$c<1$，以高概率，最大的时间动态完全图的大小为$o(n)$。 在这篇笔记中，我们通过证明对于$c<1$，最大的时间性 clique 的大小以高概率为\emph{常数}，从而改进了后者的界。