Halin’s End Degree Conjecture

Stefan Geschke; Jan Kurkofka; Ruben Melcher; Max Pitz

doi:10.1007/978-3-030-83823-2_13

Halin’s End Degree Conjecture

Stefan Geschke, Jan Kurkofka, Ruben Melcher, Max Pitz

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

An end of a graph G is an equivalence class of rays, where two rays are equivalent if there are infinitely many vertex-disjoint paths between them in G. The degree of an end is the maximum cardinality of a collection of pairwise disjoint rays in this equivalence class.

An old question by Halin asks whether the end degree can be characterised in terms of typical ray configurations. Halin conjectured that it can – in a very strong form which would generalise his famous grid theorem. In particular, every end of regular uncountable degree κ would contain a star of rays, i.e. a configuration consisting of a central ray R and κ neighbouring rays (R_i:i<κ) all disjoint from each other and each R_i sending a family of infinitely many disjoint paths to R so that paths from distinct families only meet in R.

We show that Halin’s conjecture fails for end degree ℵ₁ , holds for end degree ℵ₂,ℵ₃,…,ℵ_ω , fails for ℵ_ω+1, and is undecidable (in ZFC) for the next ℵ_ω+n with n∈ℕ, n⩾2 .

Original language	English
Title of host publication	Extended Abstracts EuroComb 2021
Subtitle of host publication	European Conference on Combinatorics, Graph Theory and Applications
Editors	Jaroslav Nešetřil, Guillem Perarnau, Juanjo Rué, Oriol Serra
Publisher	Birkhauser
Pages	78–83
Number of pages	6
Edition	1
ISBN (Electronic)	9783030838232
ISBN (Print)	9783030838225
DOIs	https://doi.org/10.1007/978-3-030-83823-2_13
Publication status	Published - 24 Aug 2021
Event	European Conference on Combinatorics, Graph Theory and Applications 2021 - Online, Barcelona , Spain Duration: 6 Sept 2021 → 10 Sept 2021

Publication series

Name	Trends in Mathematics
Publisher	Springer
Volume	14
ISSN (Print)	2297-0215
ISSN (Electronic)	2297-024X

Conference

Conference	European Conference on Combinatorics, Graph Theory and Applications 2021
Abbreviated title	EUROCOMB'21
Country/Territory	Spain
City	Barcelona
Period	6/09/21 → 10/09/21

Keywords

Infinite graph
Ends
End degree
Ray graph

Access to Document

10.1007/978-3-030-83823-2_13

Cite this

@inproceedings{2ab75b83bdcd4a11b5b7a0d8368b4f78,

title = "Halin{\textquoteright}s End Degree Conjecture",

abstract = "An end of a graph G is an equivalence class of rays, where two rays are equivalent if there are infinitely many vertex-disjoint paths between them in G. The degree of an end is the maximum cardinality of a collection of pairwise disjoint rays in this equivalence class.An old question by Halin asks whether the end degree can be characterised in terms of typical ray configurations. Halin conjectured that it can – in a very strong form which would generalise his famous grid theorem. In particular, every end of regular uncountable degree κ would contain a star of rays, i.e. a configuration consisting of a central ray R and κ neighbouring rays (Ri:i<κ) all disjoint from each other and each Ri sending a family of infinitely many disjoint paths to R so that paths from distinct families only meet in R.We show that Halin{\textquoteright}s conjecture fails for end degree ℵ1 , holds for end degree ℵ2,ℵ3,…,ℵω , fails for ℵω+1, and is undecidable (in ZFC) for the next ℵω+n with n∈ℕ, n⩾2 .",

keywords = "Infinite graph, Ends, End degree, Ray graph",

author = "Stefan Geschke and Jan Kurkofka and Ruben Melcher and Max Pitz",

year = "2021",

month = aug,

day = "24",

doi = "10.1007/978-3-030-83823-2_13",

language = "English",

isbn = "9783030838225",

series = "Trends in Mathematics",

publisher = "Birkhauser",

pages = "78–83",

editor = "Jaroslav Ne{\v s}et{\v r}il and Guillem Perarnau and Juanjo Ru{\'e} and Oriol Serra",

booktitle = "Extended Abstracts EuroComb 2021",

edition = "1",

note = "European Conference on Combinatorics, Graph Theory and Applications 2021, EUROCOMB'21 ; Conference date: 06-09-2021 Through 10-09-2021",

}

Geschke, S, Kurkofka, J, Melcher, R & Pitz, M 2021, Halin’s End Degree Conjecture. in J Nešetřil, G Perarnau, J Rué & O Serra (eds), Extended Abstracts EuroComb 2021: European Conference on Combinatorics, Graph Theory and Applications. 1 edn, Trends in Mathematics, vol. 14, Birkhauser, pp. 78–83, European Conference on Combinatorics, Graph Theory and Applications 2021, Barcelona , Spain, 6/09/21. https://doi.org/10.1007/978-3-030-83823-2_13

Halin’s End Degree Conjecture. / Geschke, Stefan; Kurkofka, Jan; Melcher, Ruben et al.
Extended Abstracts EuroComb 2021: European Conference on Combinatorics, Graph Theory and Applications. ed. / Jaroslav Nešetřil; Guillem Perarnau; Juanjo Rué; Oriol Serra. 1. ed. Birkhauser, 2021. p. 78–83 (Trends in Mathematics; Vol. 14).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Halin’s End Degree Conjecture

AU - Geschke, Stefan

AU - Kurkofka, Jan

AU - Melcher, Ruben

AU - Pitz, Max

PY - 2021/8/24

Y1 - 2021/8/24

N2 - An end of a graph G is an equivalence class of rays, where two rays are equivalent if there are infinitely many vertex-disjoint paths between them in G. The degree of an end is the maximum cardinality of a collection of pairwise disjoint rays in this equivalence class.An old question by Halin asks whether the end degree can be characterised in terms of typical ray configurations. Halin conjectured that it can – in a very strong form which would generalise his famous grid theorem. In particular, every end of regular uncountable degree κ would contain a star of rays, i.e. a configuration consisting of a central ray R and κ neighbouring rays (Ri:i<κ) all disjoint from each other and each Ri sending a family of infinitely many disjoint paths to R so that paths from distinct families only meet in R.We show that Halin’s conjecture fails for end degree ℵ1 , holds for end degree ℵ2,ℵ3,…,ℵω , fails for ℵω+1, and is undecidable (in ZFC) for the next ℵω+n with n∈ℕ, n⩾2 .

AB - An end of a graph G is an equivalence class of rays, where two rays are equivalent if there are infinitely many vertex-disjoint paths between them in G. The degree of an end is the maximum cardinality of a collection of pairwise disjoint rays in this equivalence class.An old question by Halin asks whether the end degree can be characterised in terms of typical ray configurations. Halin conjectured that it can – in a very strong form which would generalise his famous grid theorem. In particular, every end of regular uncountable degree κ would contain a star of rays, i.e. a configuration consisting of a central ray R and κ neighbouring rays (Ri:i<κ) all disjoint from each other and each Ri sending a family of infinitely many disjoint paths to R so that paths from distinct families only meet in R.We show that Halin’s conjecture fails for end degree ℵ1 , holds for end degree ℵ2,ℵ3,…,ℵω , fails for ℵω+1, and is undecidable (in ZFC) for the next ℵω+n with n∈ℕ, n⩾2 .

KW - Infinite graph

KW - Ends

KW - End degree

KW - Ray graph

U2 - 10.1007/978-3-030-83823-2_13

DO - 10.1007/978-3-030-83823-2_13

M3 - Conference contribution

SN - 9783030838225

T3 - Trends in Mathematics

SP - 78

EP - 83

BT - Extended Abstracts EuroComb 2021

A2 - Nešetřil, Jaroslav

A2 - Perarnau, Guillem

A2 - Rué, Juanjo

A2 - Serra, Oriol

PB - Birkhauser

T2 - European Conference on Combinatorics, Graph Theory and Applications 2021

Y2 - 6 September 2021 through 10 September 2021

ER -

Halin’s End Degree Conjecture

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this