Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.01816 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909279474155520 |
|---|---|
| author | Lichev, Lyuben Sanhueza-Matamala, Nicolás |
| author_facet | Lichev, Lyuben Sanhueza-Matamala, Nicolás |
| contents | A set $V$ is said to be separated by subsets $V_1,\ldots,V_k$ if, for every pair of distinct elements of $V$, there is a set $V_i$ that contains exactly one of them. Imposing structural constraints on the separating subsets is often necessary for practical purposes and leads to a number of fascinating (and, in some cases, already classical) graph-theoretic problems.
In this work, we are interested in separating the vertices of a random graph by path-connected vertex sets $V_1,\ldots,V_k$, jointly forming a separating system. First, we determine the size of the smallest separating system of $G(n,p)$ when $np\to \infty$ up to lower order terms, and exhibit a threshold phenomenon around the sharp threshold for connectivity. Second, we show that random regular graphs of sufficiently high degree can typically be optimally separated by $\lceil \log_2 n\rceil$ sets. Moreover, we provide bounds for the minimum degree threshold for optimal separation of general graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_01816 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Vertex-separating path systems in random graphs Lichev, Lyuben Sanhueza-Matamala, Nicolás Combinatorics A set $V$ is said to be separated by subsets $V_1,\ldots,V_k$ if, for every pair of distinct elements of $V$, there is a set $V_i$ that contains exactly one of them. Imposing structural constraints on the separating subsets is often necessary for practical purposes and leads to a number of fascinating (and, in some cases, already classical) graph-theoretic problems. In this work, we are interested in separating the vertices of a random graph by path-connected vertex sets $V_1,\ldots,V_k$, jointly forming a separating system. First, we determine the size of the smallest separating system of $G(n,p)$ when $np\to \infty$ up to lower order terms, and exhibit a threshold phenomenon around the sharp threshold for connectivity. Second, we show that random regular graphs of sufficiently high degree can typically be optimally separated by $\lceil \log_2 n\rceil$ sets. Moreover, we provide bounds for the minimum degree threshold for optimal separation of general graphs. |
| title | Vertex-separating path systems in random graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.01816 |