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.

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.

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.