2020/05/19 by Matt DeVos, DeVos, Matt, Rikke Langhede +5
Computer Science · Mathematics · #05C21 #05C30 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2005.09767
openalex publication_date 2020/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two well-known results in the world of nowhere-zero flows are Jaeger's 4-flow theorem asserting that every 4-edge-connected graph has a nowhere-zero ℤ2 × ℤ2-flow and Seymour's 6-flow theorem asserting that every 2-edge-connected graph has a nowhere-zero ℤ6-flow. Dvořák and the last two authors of this paper extended these results by proving the existence of exponentially many nowhere-zero flows under the same assumptions. We revisit this setting and provide extensions and simpler proofs of these results. The concept of a nowhere-zero flow was extended in a significant paper of Jaeger, Linial, Payan, and Tarsi to a choosability-type setting. For a fixed abelian group Γ, an oriented graph G = (V,E) is called Γ-connected if for every function f : E → Γ there is a flow ϕ: E → Γ with ϕ(e) ≠ f(e) for every e ∈ E (note that taking f = 0 forces ϕ to be nowhere-zero). Jaeger et al. proved that every oriented 3-edge-connected graph is Γ-connected whenever |Γ| ≥ 6. We prove that there are exponentially many solutions whenever |Γ| ≥ 8. For the group ℤ6 we prove that for every oriented 3-edge-connected G = (V,E) with ℓ = |E| - |V| ≥ 11 and every f: E → ℤ6, there are at least 2 √(ℓ) / log ℓ flows ϕ with ϕ(e) ≠ f(e) for every e ∈ E.