Are Large Random Graphs Always Safe to Hide?
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908679258767360 |
|---|---|
| author | Chakraborty, Sourav Ghosh, Sujata Samanta, Smiha |
| author_facet | Chakraborty, Sourav Ghosh, Sujata Samanta, Smiha |
| contents | We discuss winning possibilities of players in various variants of cops and robber game played on large random graphs, a testbed for various kinds of network queries, search problems in particular. We explore the use of logic frameworks to investigate such results; in particular, we show that whenever a winning condition for either player can be expressed as a certain kind of formula in first-order logic, that player almost always wins. In the process, we obtain more insight into the logic-game connection from the zero-one law perspective. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22387 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Are Large Random Graphs Always Safe to Hide? Chakraborty, Sourav Ghosh, Sujata Samanta, Smiha Logic in Computer Science Computer Science and Game Theory We discuss winning possibilities of players in various variants of cops and robber game played on large random graphs, a testbed for various kinds of network queries, search problems in particular. We explore the use of logic frameworks to investigate such results; in particular, we show that whenever a winning condition for either player can be expressed as a certain kind of formula in first-order logic, that player almost always wins. In the process, we obtain more insight into the logic-game connection from the zero-one law perspective. |
| title | Are Large Random Graphs Always Safe to Hide? |
| topic | Logic in Computer Science Computer Science and Game Theory |
| url | https://arxiv.org/abs/2511.22387 |