On the size of temporal cliques in subcritical random temporal graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915496194998272 |
|---|---|
| author | Atamanchuk, Caelan Devroye, Luc Lugosi, Gabor |
| author_facet | Atamanchuk, Caelan Devroye, Luc Lugosi, Gabor |
| contents | A \emph{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 \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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04462 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the size of temporal cliques in subcritical random temporal graphs Atamanchuk, Caelan Devroye, Luc Lugosi, Gabor Probability A \emph{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 \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. |
| title | On the size of temporal cliques in subcritical random temporal graphs |
| topic | Probability |
| url | https://arxiv.org/abs/2404.04462 |