Ashay Dharwadker's Proof of The Four Color Theorem - A Review


There is a nicely presented proof of the Four Color Theorem by Ashay Dharwadker (without any computer help) at the following Yahoo! Geocities Web site:

http://www.geocities.com/dharwadker


Summary of Dharwadker's Proof
FOUR COLOUR THEOREM.  For any subdivision of the plane into non-overlapping regions, it is always possible to mark each of the regions with one of the numbers  0, 1, 2, 3,  in such a way that no two adjacent regions receive the same number.

STEPS OF THE PROOF:  We shall outline the strategy of the new proof given in this paper.  In section I on MAP COLOURING, we define maps on the sphere and their proper colouring.  For purposes of proper colouring it is equivalent to consider maps on the plane and furthermore, only maps which have exactly three edges meeting at each vertex.  Lemma 1 proves the six colour theorem using Euler’s formula, showing that any map on the plane may be properly coloured by using at most six colours.  We may then make the following basic definitions. 

  • Define N to be the minimal number of colours required to properly colour any map from the class of all maps on the plane.
  • Based on the definition of N, select a specific map m(N) on the plane which requires no fewer than N colours to be properly coloured.
  • Based on the definition of the map m(N), select a proper colouring of the regions of the map m(N) using the N colours 0,1,…,N-1.
The whole proof works with the fixed number N, the fixed map m(N) and the fixed proper colouring of the regions of the map m(N).  In section II we define STEINER SYSTEMS and prove Tits’ inequality and its consequence that if a Steiner system S(N+1,2N,6N) exists, then  N cannot exceed 4.  Now the goal is to demonstrate the existence of such  a  Steiner  system. In section III we define EILENBERG MODULES.  The regions of the map m(N) are partitioned into disjoint, nonempty equivalence classes 0,1,…, N-1 according to the colour they receive.  This set is given the structure of the cyclic group ZN={0,1,…, N-1} under addition modulo N.  We regard ZN as an Eilenberg module for the symmetric group S3 on three letters and consider the split extension ZN]S3 corresponding to the trivial representation of S3.  By section IV on HALL MATCHINGS we are able to choose a common system of coset representatives for the left and right cosets of S3 in the full symmetric group on |ZN]S3| letters.  For each such common representative and for each ordered pair of elements of S3, in section V on RIEMANN SURFACES we establish a certain action of the two-element cyclic group on twelve copies of the partitioned map m(N) by using the twenty-fourth root function of the sheets of the complex plane.  Using this action, section VI gives the details of the MAIN CONSTRUCTION.  The 6N elements of ZN]S3 are regarded as the set of points and lemma 23 builds the blocks of 2N points with every set of N+1 points contained in a unique block.  This constructs a Steiner system S(N+1,2N,6N) which implies by Tits’ inequality that N cannot exceed 4, completing the proof.  The lemmas  1-23  and theorem 24 below are written in logical sequence. 

 

The easy part of the proof is that the existence of the Steiner system S(N+1,2N,6N) is impossible for N > 4 because of Tit's inequality on the parameters of a Steiner system. A Steiner system S(k,v,t) is an organization of k "points" into v "blocks" such that any t points uniquely determine a block. The easy part of the proof is brief enough to repeat here.

Look up Van Lint and Wilson (A Course in Cominatorics, Cambridge Univ. Press, 1992) reference J. Tits (1964), Sur les systemes de Steiner associes aux trois 'grands' groupes de Mathieu, Rend. Math. e Appl. (5) 23, 166- 184, in regard to the following:

Thm. 19.5  In any nontrivial Steiner system S(t,k,v):

v ³ (t + 1)(k - t + 1)


Proof:  A Steiner system S(t,k,v) consists of v "points" organized into "blocks" (sets) of size k such that any t points uniquely determines one block containing them. A Steiner system is "trivial" if k = v (all points in one block) or if k = t (the blocks are simply all the subsets of size t).  Thus a nontrivial Steiner system has more than one block and k > t. In a nontrivial Steiner system, take t points from one block and another point not in that block.  This is a set S of t+1 points not contained in any block (since such a block would share t points with the first block yet be distinct from it by containing the last point). Now there are t+1 subsets T of S of size t, and each determines a unique block B(T) containing T.  How many points are in the union over these B(T)?  Aside from the t+1 points in S which are surely covered by this union, consider the points in some B(T) that do not belong to S.  Since there are t points that do belong to S, there must be exactly k - t points that do not. Further, since distinct blocks B(T),B(T') share t - 1 points in S through their inclusion of T intersect T' they cannot share any other points.  Thus the size of the union over the blocks B(T) is: (t+1) points in S + (t+1)(k-t) points not in S. The desired inequality then follows:

v ³ (t + 1)(k - t + 1)

QED


If we apply this inequality to the Dharwadker's Steiner system S(N+1,2N,6N), it tells us that:

6N ³ (N + 2)N

0 ³ N2 - 4N

This clearly fails for N > 4, so the "easy part" of Dharwadker's proof is easily verified.

The hard part of the idea is to show that a planar map requiring N colors implies the existence of a Steiner system S(N+1,2N,6N). This part of the proof goes far afield in showing the existence of the Steiner system, but it seems well enough written to repay one's study. The lemmas that lead to the conclusion follow logically from the hypotheses. I was able to verify the steps with reference to the group theory texts mentioned in the references. The construction generalizes, what Rotman's book calls, the Witt-Carmichael construction. One important point to note is that all the hypotheses are actually used in the construction. In particular

  • the definition of N depends on the Axiom of Choice.
  • the map M(N) cannot be colored with less than N colors because then some of the elements of the group algebra will represent empty sets of regions and the group actions cannot be defined.
  • the map M(N) cannot be colored with more than N colors because then some of the elements of the group algebra will represent unions of multiple regions (modulo N), violating the topological subdivision of the riemann surface.
A nice geometrical model for visualizing the riemann surface construction can be found in Dharwadker's paper Riemann Surfaces. The Steiner system that results from the main construction in the proof is given explicitly in Dharwadker's paper The Witt Design.

Robert Stewart
July 31, 2005


This website is hosted for free by Freewebs.com - free website. Get your own Free Website now!