From: Bill Dubuque Newsgroups: sci.math Subject: Re: Number of Algorithms is Countable (?) Date: 08 May 1998 22:48:57 -0400 Tal Kubo wrote: | | In a sense the above is a dispute between the classical (first post) | and constructive (second post) meanings of existence of a decision | algorithm. ... Excellent examples here are the recently discovered nonconstructive graph-theoretic algorithms that are implied by the work of Robertson and Seymour on graph embeddability (which generalizes to higher genus surfaces Kuratowski's forbidden minor obstructions to planarity, cf. below). Here the nonconstructivity arises from the fact that the work of Robertson and Seymour implies only the _existence_ of a finite list of forbidden minors -- it is not known in general how to _construct_ a list of such obstructions. See my prior post below for further details and especially the cited papers by Fellows and Langston for the interesting ramifications in the foundations of complexity theory. -Bill Dubuque From: Bill Dubuque Newsgroups: sci.math,comp.theory,sci.logic Subject: Kuratowski planarity: generalizations [was: Electric, Water, Gas connection puzzler] Date: 17 Nov 1996 07:59:42 -0500 Keywords: Kuratowski planarity, forbidden subgraphs, Jordan Curve theorem, Robertson-Seymour theorem, Kruskal theorem, well-quasi-order, metamathematics, van-Kampen obstructions, Whitney trick, nonconstructive complexity theory "Bob Johannsen" wrote: | | The problem is to connect each utility to each house, without crossing | wires (pipes) or making connections house to house: | | Electric Water Gas | | House 1 House 2 House 3 | | I don't think this can be done. | But how can one prove this is impossible (if it is!)? This graph is known as the complete bipartite graph K[3,3]. It is a celebrated theorem of Kuratowski (1929) that a graph is planar iff it contains no subgraph homeomorphic to the "forbidden subgraphs" K[3,3] or K[5], the 5-vertex complete graph. This theorem was also proven earlier in 1927-28 by Pontryagin, and later by Frink and Smith in 1930; see the paper by Kennedy and Quintas for the history (a bibliography is below). The fact that K[3,3] is nonplanar is the easy part of Kuratowski's theorem. Thomassen has constructed a proof of the Jordan curve theorem based upon this (see his 1992 Monthly paper), as well as short graph-theoretical proofs of the the Jordan-Schonflies theorem, Hurwitz's theorem, etc., see his 1994 survey paper. A far reaching generalization was obtained by Robertson and Seymour in a long series of papers published during the eighties. They proved that the collection of finite graphs is well-quasi-ordered by minor embeddability, from which it follows that Kuratowski's "forbidden minor" embedding obstruction generalizes to higher genus surfaces: for a fixed integer g >= 0, there is a finite list of graphs L(g) with the property that a graph C embeds on a surface of genus g iff it does not contain, as a minor, any of the graphs on the list L. Such techniques provide nonconstructive existence proofs of poly-time algorithms for related graph-theoretic problems, in stark contrast to the fact that most all earlier problems shown to be poly-time were shown so by explicit constructions. This has interesting ramifications in the foundations of complexity theory -- a topic which has been discussed at length in a series of papers by Fellows and Langston. Friedman has performed a metamathematical analysis of the Robertson-Seymour theorem and has determined that it is independent of some rather strong logical systems. See Simpson's excellent expository survey for an introduction to this circle of ideas (available online, see below). A similar analysis had already been done for the weaker Kruskal theorem about embedding of trees -- which has powerful applications to proving termination of rewrite rule systems and the correctness of the Knuth-Bendix equational completion, see Gallier's survey. There has also been some work on higher-dimensional generalizations of Kuratowski graphs, starting with a 1932 paper of van Kampen which presents an obstruction o(K^n) which measures the nonembeddability of an n-dim complex in R^(2n). This paper anticipated and stimulated later developments in cohomology. It was ultimately shown by Wu and Shapiro that, for n >= 3, K^n embeds in R^(2n) if o(K^n)=0, a result obtained using the Whitney trick. A 1994 paper of Freedman et. al. shows that the criterion is insufficient for n=2 (this paper also summarizes related work since van Kampen). Sarkaria 1991 showed that the Whitney trick may also be applied in the one dimensional case to thus obtain Kuratowski's graph planarity criterion. See also Larmore's paper, and Wu's book on embedding theory. Following are some entry points into the literature. See the Monthly papers for introductory expositions. -Bill Dubuque Even, Shimon Graph algorithms. Computer Software Engineering Series. Computer Science Press, Inc., Woodland Hills, Calif., 1979. ix+249 pp. $17.95. ISBN 0-914894-21-8 MR 82e:68066 68E10 05C99 94C15 Fellows, Michael R. The Robertson-Seymour theorems: a survey of applications. Graphs and algorithms (Boulder, CO, 1987), 1--18, Contemp. Math., 89, Amer. Math. Soc., Providence, RI, 1989. MR 90k:05067 05C10 05A99 68R05 68R10 Fellows, Michael R.; Langston, Michael A. Nonconstructive tools for proving polynomial-time decidability. J. Assoc. Comput. Mach. 35 (1988), no. 3, 727--739. MR 90i:68046 68Q25 03D15 68R10 Fellows, Michael R.; Kaschube, Paul A. Searching for $K\sb {3,3}$ in linear time. Linear and Multilinear Algebra 29 (1991), no. 3-4, 279--290. MR 92i:05084 05C10 05C85 68R10 Freedman, Michael H.; Krushkal, Vyacheslav S.; Teichner, Peter van Kampen's embedding obstruction is incomplete for $2$-complexes in ${\bf R}\sp 4$. Math. Res. Lett. 1 (1994), no. 2, 167--176. MR 95c:57005 57M20 57Q35 Friedman, Harvey; Robertson, Neil; Seymour, Paul The metamathematics of the graph minor theorem. Logic and combinatorics (Arcata, Calif., 1985), 229--261, Contemp. Math., 65, Amer. Math. Soc., Providence, R.I., 1987. MR 88g:03085 03F35 05C10 Gallier, Jean What's so special about Kruskal's theorem and the ordinal Gamma[0]? A survey of some results in proof theory, Ann. Pure and Applied Logic, 53 (1991) 199-260. [HFR] Harrington, L.A. et.al. (editors) Harvey Friedman's Research on the Foundations of Mathematics. Elsevier 1985. Kennedy, John W.; Quintas, Louis V.; Sys\lo, Maciej M. The theorem on planar graphs. (English. French, Polish summary) Historia Math. 12 (1985), no. 4, 356--368. MR 87e:01025 01A60 05C10 Larmore, Lawrence L. The first obstruction to embedding a $1$-complex in $2$-manifold. Illinois J. Math. 14 1970 1--11. MR 40#4955 55.70 (Reviewer: C. W. Patty) Nesetril, Jaroslav; Thomas, Robin Well quasi-orderings, long games and a combinatorial study of undecidability. Logic and combinatorics (Arcata, Calif., 1985), 281--293, Contemp. Math., 65, Amer. Math. Soc., Providence, R.I., 1987. MR 88i:03098 03F35 03D55 03E05 03F30 05C05 90D99 Sarkaria, K. S. A one-dimensional Whitney trick and Kuratowski's graph planarity criterion. Israel J. Math. 73 (1991), no. 1, 79--89. MR 92g:57034 57Q35 55S35 Simpson, Stephen G. Unprovable theorems and fast-growing functions. Contemporary Math. 65 1987, 359-394; contained in full in my post: http://search.dejanews.com/dnquery.xp?QRY=dubuque%2Bsimpson%2Bbudnik&svcclass=dnold Siran, Jozef; Gvozdjak, Pavol Kuratowski-type theorems do not extend to pseudosurfaces. J. Combin. Theory Ser. B 54 (1992), no. 2, 209--212. MR 93a:05056 05C10 Smorynski, Craig (all three papers are reprinted in [HFR]) Some rapidly growing functions. Math. Intell., 2 1980, 149-154. The Varieties of Arboreal Experience. Math. Intell., 4 1982, 182-188. "Big" News from Archimedes to Friedman. Notices AMS, 30 1983, 251-256. Spencer, Joel Large numbers and unprovable theorems. Amer. Math. Monthly, Dec 1983, 669-675. Thomassen, Carsten Embeddings of graphs. Graphs and combinatorics (Qawra, 1990). Discrete Math. 124 (1994), no. 1-3, 217--228. MR 95f:05035 05C10 05C25 20F32 57M15 Thomassen, Carsten The Jordan-Schonflies theorem and the classification of surfaces. Amer. Math. Monthly 99 (1992), no. 2, 116--130. MR 92k:57026 57M99 05C10 57N05 57Q15 Thomassen, Carsten Kuratowski's theorem. J. Graph Theory 5 (1981), no. 3, 225--241. MR 83d:05039 05C10 Thomassen, Carsten A link between the Jordan curve theorem and the Kuratowski planarity criterion. Amer. Math. Monthly 97 (1990), no. 3, 216--218. MR 91g:55005 55M99 05C10 Wilf, Herbert S. Finite lists of obstructions. Amer. Math. Monthly 94 (1987), no. 3, 267--271. MR 88d:05055 05C10 W. J. Wu A theory of imbedding, immersion, and isotopy of polytopes in a Euclidean space, Science Press, Peking, 1965; MR 35 #6146