On the existence of $δ$-temporal cliques in random simple temporal graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916199934197760 |
|---|---|
| author | Mertzios, George B. Nikoletseas, Sotiris Raptopoulos, Christoforos Spirakis, Paul G. |
| author_facet | Mertzios, George B. Nikoletseas, Sotiris Raptopoulos, Christoforos Spirakis, Paul G. |
| contents | We consider random simple temporal graphs in which every edge of the complete graph $K_n$ appears once within the time interval [0,1] independently and uniformly at random. Our main result is a sharp threshold on the size of any maximum $δ$-clique (namely a clique with edges appearing at most $δ$ apart within [0,1]) in random instances of this model, for any constant~$δ$. In particular, using the probabilistic method, we prove that the size of a maximum $δ$-clique is approximately $\frac{2\log{n}}{\log{\frac{1}δ}}$ with high probability (whp). What seems surprising is that, even though the random simple temporal graph contains $Θ(n^2)$ overlapping $δ$-windows, which (when viewed separately) correspond to different random instances of the Erdos-Renyi random graphs model, the size of the maximum $δ$-clique in the former model and the maximum clique size of the latter are approximately the same. Furthermore, we show that the minimum interval containing a $δ$-clique is $δ-o(δ)$ whp. We use this result to show that any polynomial time algorithm for $δ$-TEMPORAL CLIQUE is unlikely to have very large probability of success. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07147 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the existence of $δ$-temporal cliques in random simple temporal graphs Mertzios, George B. Nikoletseas, Sotiris Raptopoulos, Christoforos Spirakis, Paul G. Combinatorics Discrete Mathematics We consider random simple temporal graphs in which every edge of the complete graph $K_n$ appears once within the time interval [0,1] independently and uniformly at random. Our main result is a sharp threshold on the size of any maximum $δ$-clique (namely a clique with edges appearing at most $δ$ apart within [0,1]) in random instances of this model, for any constant~$δ$. In particular, using the probabilistic method, we prove that the size of a maximum $δ$-clique is approximately $\frac{2\log{n}}{\log{\frac{1}δ}}$ with high probability (whp). What seems surprising is that, even though the random simple temporal graph contains $Θ(n^2)$ overlapping $δ$-windows, which (when viewed separately) correspond to different random instances of the Erdos-Renyi random graphs model, the size of the maximum $δ$-clique in the former model and the maximum clique size of the latter are approximately the same. Furthermore, we show that the minimum interval containing a $δ$-clique is $δ-o(δ)$ whp. We use this result to show that any polynomial time algorithm for $δ$-TEMPORAL CLIQUE is unlikely to have very large probability of success. |
| title | On the existence of $δ$-temporal cliques in random simple temporal graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2404.07147 |