Ubiquity and the Farey graph

2019/12/04 by Kurkofka, Jan
#05C38 #05C40 #05C55 #05C63 (Primary) 05C10 #05C83 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1912.02147

Abstract

We construct a countable planar graph which, for any two vertices u,v and any integer k≥ 1, contains k edge-disjoint order-compatible u--v paths but not infinitely many. This graph has applications in Ramsey theory, in the study of connectivity and in the characterisation of the Farey graph.

Related

• The Farey graph is uniquely determined by its connectivity
• Every infinitely edge-connected graph contains the Farey graph or T_ℵ0 ∗ t as a minor
• Ubiquity in graphs II: Ubiquity of graphs with nowhere-linear end structure
• Universality in minor-closed graph classes
• Edge-disjoint linkage in infinite graphs