Applications of infinite graph theory - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T20:12:00Z http://mathoverflow.net/feeds/question/39647 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39647/applications-of-infinite-graph-theory Applications of infinite graph theory Richard Dupont 2010-09-22T19:39:37Z 2010-09-26T06:59:47Z <p>Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the necessity.</p> <p>Now I'm wondering about infinite graph theory. Quite a bit of research seems to be done on it as well and of course they are a natural generalization of a useful concept. But I never saw an example where we actually <em>need</em> them.</p> <p>I understand that they come up as infinite Cayley graphs in group theory, that the automorphism groups of infinite but locally finite graphs are topological groups, that they play some role in general topology, etc. But to me it seems they are "just there" and are not essential in the sense that a theorem about them proves something about groups or topology what we couldn't have done easily without using them.</p> <p>Polemically phrased my question is</p> <blockquote> <p>Why should we care about infinite graphs?</p> </blockquote> http://mathoverflow.net/questions/39647/applications-of-infinite-graph-theory/39659#39659 Answer by John Stillwell for Applications of infinite graph theory John Stillwell 2010-09-22T21:06:08Z 2010-09-22T21:06:08Z <p>The first book on graph theory was König's <em>Theorie der endlichen und unendlichen Graphen</em> (Theory of finite and infinite graphs) of 1936. Thus infinite graphs were part of graph theory from the very beginning. König's most important result on infinite graphs was the so-called König infinity lemma, which states that in an infinite, finitely-branching, tree there is an infinite branch. This lemma encapsulates many arguments -- from the Bolzano-Weierstrass theorem, to the completeness theorem of logic, to the proof of various Ramsey theorems -- in graph-theoretic form. König himself used it to prove that the infinite form of van der Waerden's theorem on arithmetic progressions implies the finite version, and Erdos and Szekeres (who were students of König) took up the idea in their pioneering 1935 paper on Ramsey theory.</p> <p>As other commentators have mentioned, infinite graphs are also important as group diagrams in combinatorial group theory and low-dimensional topology. </p> http://mathoverflow.net/questions/39647/applications-of-infinite-graph-theory/39660#39660 Answer by HW for Applications of infinite graph theory HW 2010-09-22T21:28:08Z 2010-09-22T21:28:08Z <p>Bass--Serre theory translates the algebraic notion of a `splitting' of a group $G$ into an action of $G$ on a (usually infinite) tree. See Serre's classic *Arbres, Amalgames, $SL_2$*.</p> http://mathoverflow.net/questions/39647/applications-of-infinite-graph-theory/39662#39662 Answer by Colin Reid for Applications of infinite graph theory Colin Reid 2010-09-22T22:12:09Z 2010-09-22T22:12:09Z <p>The Rado graph (or countable random graph) is graph theory's answer to the normal distribution. It seems almost any sensible definition of drawing edges on a countable graph 'randomly' or even 'pseudo-randomly' will almost surely produce the Rado graph. The study of this specific graph (and similar 'universal' entities) could be justified simply by its ubiquity. That said, I don't know if it's had any clear applications to other areas.</p> http://mathoverflow.net/questions/39647/applications-of-infinite-graph-theory/39663#39663 Answer by Tony Huynh for Applications of infinite graph theory Tony Huynh 2010-09-22T22:26:41Z 2010-09-22T22:26:41Z <p>Here's a nice proof of the Cantor-Bernstein theorem in the language of infinite graphs. </p> <p><strong>Theorem.</strong> Let $G$ be an infinite graph with bipartition $(A,B)$. If $G$ has a matching saturating $A$ and a matching saturating $B$, then $G$ has a perfect matching.</p> <p><strong>Proof.</strong> Let $M_A$ and $M_B$ be matchings saturating $A$ and $B$ respectively. Let $H$ be the graph with vertex set $A \cup B$ and edge set the (disjoint) union of $M_A$ and $M_B$. Hence $H$ may be a multigraph. It is easy to check that every component of $H$ is either an infinite path or an even cycle. Thus, taking every other edge of each component of $H$ yields a perfect matching of $G$. </p> http://mathoverflow.net/questions/39647/applications-of-infinite-graph-theory/39721#39721 Answer by Stefan Geschke for Applications of infinite graph theory Stefan Geschke 2010-09-23T09:26:46Z 2010-09-23T09:26:46Z <p>Recently there has been quite a bit of activity in descriptive set theory concerning definable graphs. Benjamin Miller derived several deep classical results such as Silver's theorem (stating that every sufficiently nice (here coanalytic) equivalence relation on a separable complete metric space either has countably many equivalence classes or there is a Cantor space of pairwise non-equivalent points) from results on uncountable graphs by relatively elementary proofs. The original proof of Silver's theorem used heavy set-theoretic machinery. </p> <p>The result on uncountable graphs that started it all is the $\mathcal G_0$-dichotomy of Kechris, Solecki and Todorcevic:</p> <p>There is a closed graph $\mathcal G_0$ on the Cantor space such that for every analytic graph $G$ on a Polish space either $G$ has a Borel-measurable coloring with countably many colors or there is a graph homomorphism from $\mathcal G_0$ to $G$.</p> <p>So in some sense, $\mathcal G_0$ is the minimal analytic graph whose Borel-chromatic number is uncountable. </p>