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


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?

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


[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.