Typical graphs
The following is a summary of The immersion-minimal infinitely edge-connected graph [KK2024] which is joint work with Jan Kurkofka. In 2024 it is published in Journal of Combinatorial Theory, Series B. 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.
Main results
1.) The halved Farey graph, depicted in Figure 1 below, is the unique strong-immersion-minimal infinitely edge-connected graph [KK2024, Theorem 1] .
2.) 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 [KK2024, Theorem 2]. 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
Summary
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 clique is the only typical infinitely edge-connected graph.
For minors, Kurkofka [Kur22, Theorem 1] 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.
Some remark
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
References
[Kur22] J. Kurkofka, Every infinitely edge-connected graph contains the Farey graph or T_{ℵ₀} ∗ t as a minor, Mathematische Annalen 382 (2022): 1881–1900. Available on arXiv:2004.06710.