✦ LIBER ✦

A Simpler Proof of the Excluded Minor Theorem for Higher Surfaces

✍ Scribed by Carsten Thomassen

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 223 KB
Volume: 70
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1761

No coin nor oath required. For personal study only.

✦ Synopsis

We give a simple proof of the fact (which follows from the Robertson Seymour theory) that a graph which is minimal of genus g cannot contain a subdivision of a large grid. Combining this with the tree-width theorem and the quasi-wellordering of graphs of bounded tree-width in the Robertson Seymour theory, we obtain a simpler proof of the generalized Kuratowski theorem for each fixed surface. The proof requires no previous knowledge of graph embeddings.

1997 Academic Press We define the grid J k as a finite subgraph of the hexagonal tiling of the Euclidean plane. We let J 1 be a cycle of length 6. For each k 2, we define J k as the union of J k&1 and all those 6-cycles in the hexagonal grid which intersect J k&1 . Clearly, J k is a subdivision of a 3-connected graph when k>1. With this notation [8,9] imply article no. TB971761 306 0095-8956Â97 25.00

📜 SIMILAR VOLUMES

A Proof of the Characterization Theorem

A Proof of the Characterization Theorem for Consequence Relations

✍ Zvonimir Šikić 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

The Use of Proof Planning for Co-operati

The Use of Proof Planning for Co-operative Theorem Proving

✍ H. Lowe; A. Bundy; D. McLean 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 491 KB

We describe barnacle: a co-operative interface to the clam inductive theorem proving system. For the foreseeable future, there will be theorems which cannot be proved completely automatically, so the ability to allow human intervention is desirable; for this intervention to be productive the problem

Bifurcations under Nondegenerated Condit

Bifurcations under Nondegenerated Conditions of Higher Degree and a New Simple Proof of the Hopf–Neimark–Sacker Bifurcation Theorem

✍ F. Balibrea Gallego; J.C. Valverde Fajardo 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 91 KB

A Compactness Theorem for Approximating

A Compactness Theorem for Approximating the Invariant Densities of Higher Dimensional Transformations

✍ A. Boyarsky; Y.S. Lou 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 383 KB

Combinatorial Proofs of the Conley-Zehnd

Combinatorial Proofs of the Conley-Zehnder-Franks Theorem on a Fixed Point for Torus Homeomorphisms

✍ S. Alpern; V.S. Prasad 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 428 KB

We give two combinatorial proofs of Franks' Theorem, that an area preserving torus homeomorphism with mean rotation zero has a fixed point. The first proof uses Lax's version of the Marriage Theorem. The second proof uses Euler's Theorem on circuits in graphs and an explicit method of Alpern for dec

A new proof of de Giorgi's theorem conce

A new proof of de Giorgi's theorem concerning the regularity problem for elliptic differential equations

✍ Jürgen Moser 📂 Article 📅 1960 🏛 John Wiley and Sons 🌐 English ⚖ 469 KB 👁 1 views