A counterexample to the coarse Menger conjecture
<p>Menger’s well-known theorem from 1927 characterizes when it is possible to find k vertex-disjoint paths between two sets of vertices in a graph G. Recently, Georgakopoulos and Papasoglu and, independently, Albrechtsen, Huynh, Jacobs, Knappe and Wollan conjectured a coarse analogue of Menger...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2025
|
| _version_ | 1824459334889766912 |
|---|---|
| author | Nguyen, T Scott, A Seymour, P |
| author_facet | Nguyen, T Scott, A Seymour, P |
| author_sort | Nguyen, T |
| collection | OXFORD |
| description | <p>Menger’s well-known theorem from 1927 characterizes when it is possible to find k vertex-disjoint paths between two sets of vertices in a graph G. Recently, Georgakopoulos and Papasoglu and, independently, Albrechtsen, Huynh, Jacobs, Knappe and Wollan conjectured a coarse analogue of Menger’s theorem, when the k paths are required to be pairwise at some distance at least d. The result is known for k ≤ 2, but we will show that it is false for all k ≥ 3, even if G is constrained to have maximum degree at most three. We also give a simpler proof of the result when k = 2.</p> |
| first_indexed | 2025-02-19T04:40:08Z |
| format | Journal article |
| id | oxford-uuid:cfd9ec47-677f-48a8-8452-a3da57d070e7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-02-19T04:40:08Z |
| publishDate | 2025 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:cfd9ec47-677f-48a8-8452-a3da57d070e72025-02-14T08:53:09ZA counterexample to the coarse Menger conjectureJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:cfd9ec47-677f-48a8-8452-a3da57d070e7EnglishSymplectic ElementsElsevier2025Nguyen, TScott, ASeymour, P<p>Menger’s well-known theorem from 1927 characterizes when it is possible to find k vertex-disjoint paths between two sets of vertices in a graph G. Recently, Georgakopoulos and Papasoglu and, independently, Albrechtsen, Huynh, Jacobs, Knappe and Wollan conjectured a coarse analogue of Menger’s theorem, when the k paths are required to be pairwise at some distance at least d. The result is known for k ≤ 2, but we will show that it is false for all k ≥ 3, even if G is constrained to have maximum degree at most three. We also give a simpler proof of the result when k = 2.</p> |
| spellingShingle | Nguyen, T Scott, A Seymour, P A counterexample to the coarse Menger conjecture |
| title | A counterexample to the coarse Menger conjecture |
| title_full | A counterexample to the coarse Menger conjecture |
| title_fullStr | A counterexample to the coarse Menger conjecture |
| title_full_unstemmed | A counterexample to the coarse Menger conjecture |
| title_short | A counterexample to the coarse Menger conjecture |
| title_sort | counterexample to the coarse menger conjecture |
| work_keys_str_mv | AT nguyent acounterexampletothecoarsemengerconjecture AT scotta acounterexampletothecoarsemengerconjecture AT seymourp acounterexampletothecoarsemengerconjecture AT nguyent counterexampletothecoarsemengerconjecture AT scotta counterexampletothecoarsemengerconjecture AT seymourp counterexampletothecoarsemengerconjecture |