Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.14151 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910751519670272 |
|---|---|
| author | Aurichi, Leandro Fiorini Real, Lucas |
| author_facet | Aurichi, Leandro Fiorini Real, Lucas |
| contents | The Unfriendly Partition Problem asks whether it is possible to split the vertex set of an infinite graph $G$ into two parts so that every vertex has at least as many neighbors in the other part than on its own. Despite the uncountable counterexamples provided by Milner and Shelah in 1990, this question still has no solution for graphs on countably many vertices. Under this hypothesis, our main result claims that such a bipartition exists if the rays of $G$ do not pass through infinitely many vertices of finite degree and infinitely many vertices of infinite degree simultaneously. In particular, for the class of countable graphs, we generalize previous results due to Aharoni, Milner and Prikry and due to Bruhn, Diestel, Georgakopolous and Sprüssel. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14151 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Remarks on the countable case of the Unfriendly Partition Problem Aurichi, Leandro Fiorini Real, Lucas Combinatorics 05C63 The Unfriendly Partition Problem asks whether it is possible to split the vertex set of an infinite graph $G$ into two parts so that every vertex has at least as many neighbors in the other part than on its own. Despite the uncountable counterexamples provided by Milner and Shelah in 1990, this question still has no solution for graphs on countably many vertices. Under this hypothesis, our main result claims that such a bipartition exists if the rays of $G$ do not pass through infinitely many vertices of finite degree and infinitely many vertices of infinite degree simultaneously. In particular, for the class of countable graphs, we generalize previous results due to Aharoni, Milner and Prikry and due to Bruhn, Diestel, Georgakopolous and Sprüssel. |
| title | Remarks on the countable case of the Unfriendly Partition Problem |
| topic | Combinatorics 05C63 |
| url | https://arxiv.org/abs/2412.14151 |