Typical graphs
The following is a summary of the paper The immersion-minimal infinitely edge-connected graph which is joint work with Jan Kurkofka. In 2024 it was published in Journal of Combinatorial Theory, Series B, Volume 164, Pages 492-516. You can find a preprint on arXiv. This paper is an extract from my Master's thesis, which I created under the supervision of Jan during the COVID-19 pandemic. It was a strange and rough time in which Jan supported me a lot. He also helped me to figure out how to structure write-ups in general but especially proofs. This greatly influenced my style of writing.
1st main result: The halved Farey graph, depicted in Figure 1 below, is the unique strong-immersion-minimal infinitely edge-connected graph.
2nd main result: Every list of infinitely edge-connected graphs such that every infinitely edge-connected graph contains a subdivision of some graph from this list has to be uncountable. Moreover, this is witnessed by generalised halved Farey graphs; an example of it is depicted in Figure 2 below.
Figure 1: The halved Farey graph
Figure 2: The generalised halved Farey graph
Context: Given a containment relation ≤, such as the (topological-)minor- or the weak\strong-immersion-relation, these are the ≤-minimal infinitely edge-connected graphs (up to ≤-equivalence). But which ones are they?
For weak immersions, a greedy argument yields that the countably infinite complete graph is the only typical infinitely edge-connected graph.
For minors, Kurkofka (2022) explicitely described the two graphs which are the typical infinitely edge-connected graphs. One of which is the Farey graph, depicted in Figure 3 below.
For strong immersions, our 1st main result is that the halved Farey graph is the only typical infinitely edge-connected graph.
For topological minors, our 2nd main result ensures that there are at least uncountable many typical infinitely edge-connected graphs. The proof heavily relies on generalised halved Farey graphs.
It is noteworthy that the Farey graph has already been present in several mathematical areas ranging from group theory and number theory to geometry and dynamics. Quite interestingly, graph theory has not been among this list until recently. But now the Farey graph and variants of it also play a role in graph theory.
Figure 3: The Farey graph