Menger's theorem for infinite graphs

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=Fj_9Jkdjvz4


Duration: 51:48
746 views
3

We prove an old conjecture of Erdos, saying that Menger's theorem is valid also for infinite graphs, in the following strong form: given sets A and B of vertices in a graph (possibly directed, possibly infinite), there exists a family P of disjoint A-B paths, and an A-B separating set S, such that S consists of a choice of precisely one vertex from each path in P. The talk will describe the history of the problem and the main ideas of our proof. This is joint work with Ron Aharoni.



Other Videos By Microsoft Research


2016-09-05A Framework for Unrestricted Whole-Program Optimization
2016-09-05Locality and Phases: Dynamic Structures of Large-Scale Program Behavior
2016-09-05The Physical and Mental States of Users Anytime and in Their Natural Environments
2016-09-05Skoll: Distributed Continuous Quality Assurance
2016-09-05Everything Bad Is Good for You: How Today's Popular Culture Is Actually Making Us Smarter
2016-09-05Service Placement in Stream-Based Overlay Networks
2016-09-05Protocol Composition Logics
2016-09-05THE FUTURE IS NOT FRAMED
2016-09-05Model Checking of Predicate Abstracted Programs without BDDs [1/2]
2016-09-05Social Computing Symposium - Panel - Extracting Signal from Noise in Social Networking
2016-09-05Menger's theorem for infinite graphs
2016-09-052D, 3D and Surface Texture Analysis and Synthesis
2016-09-05Anonymity in Peer-to-peer Systems
2016-09-05Patterns as Signs
2016-09-05Social Computing Symposium - Positive Externalities
2016-09-05Analyzing Mobile ad hoc Network Protocols via Probabilistic Model Checking [1/26]
2016-09-05Are aspects really needed for aspect-oriented programming?
2016-09-05Live Long and Prosper! Exercise, Nutrition and Supplements for Optimal Energy and Productivity
2016-09-05Social Computing Symposium - Visualizing Social Interactions and Collaboration History
2016-09-05Social Computing Symposium - Back Channels: Power and the Active Audience
2016-09-05Social Computing Symposium - Exploring the Social Institutional Dimensions of MoSoSo Design


Tags:
microsoft research