Menger's theorem for infinite graphs

DOI10.1007/S00222-008-0157-3zbMATH Open1216.05092arXivmath/0509397OpenAlexW2076891803WikidataQ55967026 ScholiaQ55967026MaRDI QIDQ1016232FDOQ1016232

Ron Aharoni, Eli Berger

Publication date: 5 May 2009

Published in: Inventiones Mathematicae (Search for Journal in Brave)

Abstract: We prove that Menger's theorem is valid for infinite graphs, in the following strong form: let $A$ and $B$ be two sets of vertices in a possibly infinite digraph. Then there exist a set $cp$ of disjoint $A$-$B$ paths, and a set $S$ of vertices separating $A$ from $B$, such that $S$ consists of a choice of precisely one vertex from each path in $cp$. This settles an old conjecture of ErdH{o}s.

Full work available at URL: https://arxiv.org/abs/math/0509397

Mathematics Subject Classification ID

Connectivity (05C40) Infinite graphs (05C63)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matching theory
• On Representatives of Subsets
• Infinite graphs—A survey
• Menger's theorem for countable graphs
• Injective choice functions for countable families
• Ein Neuer Beweis Eines Mengerschen Satzes
• Über Translationen und den Satz von Menger in unendlichen Graphen
• Menger's theorem for graphs containing no infinite paths
• Greene-Kleitman's theorem for infinite posets
• A General Criterion for the Existence of Transversals
• Matchings in graphs of size \(\aleph_ 1\)
• Matchings in infinite graphs
• Infinite matching theory
• Necessary and sufficient conditions for transversals of countable set systems
• Marriage in denumerable societies
• On Dilworth's decomposition theorem
• A counterexample to Aharoni's strongly maximal matching conjecture
• Another Criterion for Marriage in Denumerable Societies
• Menger's Theorem for a Countable Source Set

Cited In (39)

• Enlarging vertex-flames in countable digraphs
• Graph-like continua, augmenting arcs, and Menger's theorem
• Minimal covers of infinite hypergraphs
• Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\)
• Reducing the dichromatic number via cycle reversions in infinite digraphs
• 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10
• Matroid intersection, base packing and base covering for infinite matroids
• The Lovász-Cherkassky theorem for locally finite graphs with ends
• On the packing/covering conjecture of infinite matroids
• On the mixed connectivity conjecture of Beineke and Harary
• The Menger-like property of the three-width of infinite graphs
• A formal approach to Menger's theorem
• A link between Menger's theorem and infinite Euler graphs
• A proof of Menger's Theorem by contraction
• Proof of Nash-Williams' intersection conjecture for countable matroids
• Countable Menger's theorem with finitary matroid constraints on the ingoing edges
• A Riemann-Roch Theorem on Infinite Graphs
• Strongly maximal antichains in posets
• Title not available (Why is that?)
• Gallai-Milgram properties for infinite graphs
• Topological infinite gammoids, and a new Menger-type theorem for infinite graphs
• A mechanized proof of the max-flow min-cut theorem for countable networks with applications to probability theory
• Locally finite graphs with ends: A topological approach. II: Applications
• Buser's inequality on infinite graphs
• Busemann points of infinite graphs
• Tight infinite matrices
• Disjoint dijoins for classes of dicuts in finite and infinite digraphs
• The Lovász-Cherkassky theorem in infinite graphs
• Infinite gammoids
• A minimax theorem for infinite graphs with ideal points
• Menger's theorem
• On the intersection conjecture for infinite trees of matroids
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• On the infinite Lucchesi–Younger conjecture I
• Greedoids from flames
• The Max-Flow Min-Cut theorem for countable networks
• On the intersection of infinite matroids
• The Lovász-Cherkassky theorem in countable graphs
• Title not available (Why is that?)

This page was built for publication: Menger's theorem for infinite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016232)