论文标题
随机简单的时间图中的尖锐阈值
Sharp Thresholds in Random Simple Temporal Graphs
论文作者
论文摘要
边缘仅出现在某些时间点的图称为时间图（其他名称）。如果每个有序的顶点对通过按时间顺序（即时间路径）横穿边缘的路径连接，则将这样的图在时间上连接。在本文中，我们考虑了一个从erdős-rényi随机图获得的随机时间图的简单模型$ g〜g_ {n，p} $，通过考虑边缘的随机置换$π$，并将$π$中的等级解释为存在时间。该模型中的时间可达到性显示出令人惊讶的规则阈值序列。特别是，我们表明，在$ p = \ log n/n $上，任何固定对的顶点都可以A.A.S.彼此接触$ 2 \ log n/n $至少一个顶点（实际上，任何固定顶点）可以A.A.S.到达所有其他人； $ 3 \ log n/n $所有顶点都可以a.a.s.彼此触及，即该图是时间连接的。此外，该图在临时连接后立即承认了一个尺寸$ 2N+O（n）$的时间启动器，这几乎是最佳的，因为$ 2N-4 $是下限。该结果很重要，因为时间图通常不接受尺寸$ o（n）$的跨度（Kempe等，Stoc 2000）。实际上，他们甚至不承认$ o（n^2）$的跨度（Axiotis等，ICALP 2016）。因此，我们的结果意味着在这些作品中发现的障碍物，更普遍地，所有不可忽略的障碍物必须在统计学上微不足道：几乎最佳的跨度始终存在于随机的时间图中。上述所有阈值都很清晰。进一步进行时间跨度的研究，我们表明，关键的跨度 - 即，大小的跨度$ 2n-2 $由两个跨越的树木粘在一个顶点上（一个及时下降，另一个随后升高） - 存在于A.A.A.S. $ 4 \ log n/n $，此门槛也很清晰。最后，我们表明（尺寸为$ 2n-4 $）的最佳跨度也存在A.A.S.在$ p = 4 \ log n/n $。
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdős-Rényi random graph $G~G_{n,p}$ by considering a random permutation $π$ of the edges and interpreting the ranks in $π$ as presence times. Temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at $p=\log n/n$ any fixed pair of vertices can a.a.s. reach each other; at $2\log n/n$ at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at $3\log n/n$ all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size $2n+o(n)$ as soon as it becomes temporally connected, which is nearly optimal as $2n-4$ is a lower bound. This result is significant because temporal graphs do not admit spanners of size $O(n)$ in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size $o(n^2)$ (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all non-negligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners -- i.e., spanners of size $2n-2$ made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently) -- exist a.a.s. at $4\log n/n$, this threshold being also sharp. Finally, we show that optimal spanners (of size $2n-4$) also exist a.a.s. at $p = 4\log n/n$.
