Signed permutations and the four color theorem

Let σ₁,σ₂ be two permutations in the symmetric group S_n. Among the many sequences of elementary transpositions τ₁,…,τ_r transforming σ₁ into σ₂=τ_rτ₁σ₁, some of them may be signable, a property introduced in this paper. We show that the four color theorem in graph theory is equivalent to the statement that, for any n≥2 and any σ₁,σ₂S_n, there exists at least one signable sequence of elementary transpositions from σ₁ to σ₂. This algebraic reformulation rests on a former geometric one in terms of signed diagonal flips, together with a codification of the triangulations of a convex polygon on n+2 vertices by permutations in S_n.     

Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

A discrete four vertex theorem

A discrete four vertex theorem is proved for a general plane polygon using a method of proof that also yields a proof, that appears to be new, for the classical four vertex theorem.     

A new proof of the 6 color theorem

In 1965 Ringel raised a 6 color problem for graphs that can be stated in at least three different forms. In particular, is it possible to color the vertices and faces of every plane graph with 6 colors so that any two adjacent or incident elements are colored differently? This 6 color problem was solved in 1984 by the present author; the proof used about 35 reducible configurations. A shorter new proof is given here using only half as many of reducible configurations. © 1995 John Wiley & Sons, Inc.     

A conformally invariant sphere theorem in four dimensions

Publications mathématiques de l'IHÉS -     

A discrete four vertex theorem for hyperbolic polygons

There are many four vertex type theorems appearing in the literature, coming in both smooth and discrete flavors. The most familiar of these is the classical theorem in differential geometry, which states that the curvature function of a simple smooth closed curve in the plane has at least four extreme values. This theorem admits a natural discretization to Euclidean polygons due to O. Musin. In this article we adapt the techniques of Musin and prove a discrete four vertex theorem for convex hyperbolic polygons.     

The converse of the four vertex theorem

We establish the converse to the four vertex theorem without the positivity condition.

     

The combinatorial map color theorem

This paper is written in the spirit of the author's book: Map Color Theorem (1974). We try to develop the Map Color Theorem in a combinatorial way, circumventing the unwieldy embedding theory. Similar (but not identical) generalizations have recently and independently been developed by Alpert (in press) and by Stahl (in press). The first nine theorems are one-dimensional versions of known facts from the theory of two-dimensional compact manifolds. Theorems 10 to 13 are to my knowledge completely new results.     

An addition theorem for the color number

There is a close relation between the color number of a continuous map without fixed points and the topological dimension. If  is an involution, the color number is also related to the co-index. An addition theorem for the color number is established thus underscoring the interrelations between color number, dimension and co-index.

     

An infinite color analogue of Rado's theorem

Let R be a subring of the complex numbers and a be a cardinal. A system L of linear homogeneous equations with coefficients in R is called a-regular over R if, for every a-coloring of the nonzero elements of R, there is a monochromatic solution to L in distinct variables. In 1943, Rado classified those finite systems of linear homogeneous equations that are a-regular over R for all positive integers a. For every infinite cardinal a, we classify those finite systems of linear homogeneous equations that are a-regular over R. As a corollary, for every positive integer s, we have ℵ₀²>ℵs if and only if the equation x₀+sx₁=x₂+?+xs+2 is ℵ₀-regular over R. This generalizes the case s=1 due to Erd?s.     

An intersection theorem for four sets

Fix integers n,r?4 and let F denote a family of r-sets of an n-element set. Suppose that for every four distinct A,B,C,D∈F with |A∪B∪C∪D|?2r, we have A∩B∩C∩D≠∅. We prove that for n sufficiently large, , with equality only if _?F∈FF≠∅. This is closely related to a problem of Katona and a result of Frankl and Füredi [P. Frankl, Z. Füredi, A new generalization of the Erd?s-Ko-Rado theorem, Combinatorica 3 (3-4) (1983) 341-349], who proved a similar statement for three sets. It has been conjectured by the author [D. Mubayi, Erd?s-Ko-Rado for three sets, J. Combin. Theory Ser. A, 113 (3) (2006) 547-550] that the same result holds for d sets (instead of just four), where d?r, and for all n?dr/(d−1). This exact result is obtained by first proving a stability result, namely that if |F| is close to then F is close to satisfying _?F∈FF≠∅. The stability theorem is analogous to, and motivated by the fundamental result of Erd?s and Simonovits for graphs.     

The four color proof suffices

The Mathematical Intelligencer - Since no one else has communicated any other errors in the published unavoidability proof since 1976 we assume that a misunderstanding of the nature of...     

An attempt to understand the four color problem

Is the recently obtained, computer-aided proof of the Four Color Theorem an isolated phenomenon or is its combinatorial complexity typical for a significantly large class of mathematical problems? While it is too early to give a definite answer to this question, an informal discussion is undertaken in this article.