{"ID":2835953,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.22387","arxiv_id":"2511.22387","title":"Are Large Random Graphs Always Safe to Hide?","abstract":"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.","short_abstract":"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 conditi...","url_abs":"https://arxiv.org/abs/2511.22387","url_pdf":"https://arxiv.org/pdf/2511.22387v1","authors":"[\"Sourav Chakraborty\",\"Sujata Ghosh\",\"Smiha Samanta\"]","published":"2025-11-27T12:15:57Z","proceeding":"cs.LO","tasks":"[\"cs.LO\",\"cs.GT\"]","methods":"[]","has_code":false}