Re: a proof for consideration


Matt Zellman a écrit :

I finally got my hands on a copy of Steinberg's paper, and the key line
of reasoning I use to make the proof that P is not equal to NP is not
addressed in the paper. The focus of that paper is on finding local
structures that would determine 3-colorability, while I demonstrate
that such an approach cannot be satisfactory. Furthermore, I show that
reducing the problem to one that is local in scope necessarily requires
exponential time as well.

As far as I can tell, based on the Steinberg paper (which, admittedly,
is 13 years old), the approach I used is novel. I haven't come across
anything more recent that would suggest otherwise, either.


Matt Zellman wrote:
Matt Zellman wrote:
Proginoskes wrote:
Matt Zellman wrote:
Proginoskes wrote:
matt.zellman@xxxxxxxxx wrote:
so a couple of weeks ago, I posted here asking for help with a paper. I
decided to go ahead and put what I have out here so people can look it
over. I'll reiterate some of the concepts I went over in the previous
thread, and then see if my reasoning is sound.

Recently, I got a few free moments, and I looked up Richard Steinberg's
paper "The Three-Color Problem" (to update and fix errors on my page
about Steinberg's Conjecture), and I found that some of Zellman's
concepts showed up there as well.

1. k-chromatic Edge Replacement Subgraphs (^kERSs)

a ^kERS is a k-chromatic graph that contains at least one pair of
nonadjacent vertices for which no valid k-colorings exist when they are
colored the same color.

A couple of Russian mathematicians, V.A. Aksionov and L.S. Mel'nikov,
called ^kERS's "quasi-edges" in a 1978 paper ("Essay on the theme: the
three-color problem", Combinatorics, Colloquia Mathematica Societatis
Janos Bolyai 18, 23-34).


Would it be more appropriate for me to switch to this term, since it
predates mine? I think it is much clearer to include the chromatic
number in the designation, because such subgraphs only really work when
colored with a set number of colors.

Sticking with "quasi-edges" would cause less confusion. However, if
calling them "k-quasi-edges" would be a nice compromise.

Sounds good to me. "k-quasi-edges" it is.


The ^kERS as a whole functions in exactly the
same way as a single edge, and a k-chromatic graph can be transformed
G=>G' by replacing an edge with a ^kERS, a process I have called
"expansion by edge-replacement."

The reverse process, replacing a ^kERS with an edge, I have termed
"reduction by edge-replacement."

2. Boundary Points

Every graph has at least one set of vertices (of a size greater than or
equal to the chromatic number k of the graph) for which no valid
k-colorings exist when the vertices in the set are colored with less
than k colors. Any such set of vertices is a set of "boundary points."

3. Basic k-chromatic Graphs

A primary basic k-chromatic graph is constructed by taking a basic
(k-1)-chromatic graph and adding one vertex, which is then connected to
an entire set of boundary points with edges or ^kERSs. A secondary
basic k-chromatic graph is an expansion of a primary basic k-chromatic
graph by edge-replacement. The basic 1-chromatic graph is a single
vertex.

Every graph with chromatic number k contains at least one basic
k-chromatic graph as a subgraph, and no basic (k+1) chromatic graphs as
subgraphs.

This sounds a lot like a problem that Bjarne Toft raised in 1985:

PROBLEM. Suppose G is a (k+1)-colorable graph which does not contain
K_(k+1). Does it follow that there are two vertices x and y and two
k-colorable subgraphs G1 and G2, each containing x and y, such that:
(1) in any k-coloring of G1, x and y receive different colors, and
(2) in any k-coloring of G2, x and y receive the same color.

The converse is true for any k. This problem is true for k=2 but has
been proven to be false if k >= 6. It is open for k=3, AFAIK.


Basically, the question is, "is there any combination of a ^kERS and an
'anti-^kERS' that would force k+1 colors, and does not contain a basic
k-chromatic graph?"?

right?

Yes. Although here, all "boundary sets" would have size two.

interesting. I think I can prove that the answer to this question is
"no" for k=3.


should I go ahead and attempt this proof? or is it even necessary?


The scope of the three-color problem is bounded only by the size of the
graph. That is, consider the graph below (Figure A):

O---O---O---O---O
/|\ / \ / \ / \ /|
O-O O O O O |
\|/ \ / \ / \ / \|
O---O---O---O---O

This graph is 4-chromatic, as are all the graphs with the same end
regions and different lengths of the same pattern in the middle. I
could change something anywhere on the graph to make the chromatic
number 3. For example, I could delete the leftmost vertex, I could add
a vertex in the middle of the edge at the right end, or I could change
any of the middle vertices to other configurations.

To put it succinctly, in order to determine the colorability of the
graph, I am required to make an exhaustive analysis. No local analysis
would guarantee that I find all the structures that determine the
colorability of the graph.



Suppose, however, that using edge-replacement, we could reduce the
graph to some configuration that could be analyzed locally. If we
replace all the ^3ERSs with edges until there are no ^3ERSs left, we
will be left with a graph that can be analyzed locally, in
deterministic polynomial time. We simply have to go through the graph,
and for each vertex, we look for all the edges connected to that
vertex, and take note of which vertex is on the other end of each edge.
Then we look for all the edges between those vertices, and build a
subgraph from them. We can try to color this subgraph with two colors.
If we can, then the graph may still be 3-colorable. If we can't, then
the graph is not 3-colorable.

It certainly seems like a reasonable course of action, but it turns out
that even identifying ^3ERSs in a graph is necessarily exponential over
the inputs. Go back to the example graph shown above. If we take it
back to the basic 3-chromatic graph it is constructed from, we are left
with the graph below (Figure B):

O---O---O---O---O
/ \ / \ / \ / \ /|
O O O O O |
\ / \ / \ / \ / \|
O---O---O---O---O

It is an example of a graph in which a single ^3ERS has been iterated 4
times from a simple triangle. The ^3ERS by itself looks like this
(Figure C):

1@---O2
\ /|
3O |
/ \|
4@---O5

(where the @s signify the endpoints of the edge that is being replaced,
and the vertices are numbered from 1-5 to help us out later)

Aksionov and Mel'nikov call the smaller graph a "building block".
Richard Steinberg's paper goes into more detail.

Where would be the best place to get ahold of these papers? What
exactly am I looking for?

The Steinberg paper is in a book called _Quo Vadis, Graph Theory?_,
which should be in your local university library (call number QA166 .Q6
1993). (This book is about 400 pages long, but Steinberg's article only
consists of pages 211-248.) I would think it's too old to be available
electronically. Steinberg _might_ still have preprints or reprints, but
I doubt it. (His webpage is
http://www.jbs.cam.ac.uk/people/faculty/steinbergr.html ).


I will check this out the next chance I get.


I finally located a copy and am waiting for it to come in. There isn't
a library in the area that has it.

In each even iteration of this ^3ERS, an edge can be constructed
between the initial vertex 1, and vertex 5 of the
second/fourth/sixth... iteration, without changing the colorability of
the graph. Alternatively, an edge can be constructed between the
initial vertex 4 and vertex 2 of that iteration. For odd iterations,
they switch: initial vertex 1 can be connected to vertex 2 of the
third/fifth/seventh... iteration, or initial vertex 4 can be connected
to vertex 5 of that iteration.

Suppose that for each iteration, we construct one of these two edges.
Such a construction across iterations creates a ^3ERS that cannot be
reduced to another ^3ERS, but only straight to an edge. Each iteration
adds 3 vertices and 7 edges to the graph. The extra edge we add makes
it 3 and 8. We can represent which edge we have constructed at each
iteration by simply making an ordered list: 14411144444... This
particular example is equivalent to the graph represented by
41144411111, but not to the graph represented by 11411144444 or any
other graph in the set. There are therefore at least 2^(i-2) unique
possible ^3ERSs for each iteration i (i>1). Relating this to the size
of the input (suppose our input is just the list of edges), the number
of necessary tests for unique ^3ERSs for a graph with E edges must
necessarily exceed (since our starting set of ^3ERSs is severely
limited, as are the rules for construction):

2^(E/8-2) for E>16


Since without edge-replacement, the scope of the problem is unbounded,
and therefore requires an exhaustive search, and with edge replacement,
it requires a number of tests that is at least exponential over the
size of the input, we are forced to conclude that the 3-coloring
problem cannot be solved deterministically in polynomial time.

And, as a direct result, P is not equal to NP.


Is there anything I've missed?

Is this part of the proof new? or is it also covered in Steinberg or
Askionov and Mel'nikov?

This last part isn't, but Steinberg usually only summarizes results.
The reference list has 128 papers on it.

--- Christopher Heckman

Oh, fun, a scavenger hunt! ;-)

~Matt Zellman



As a footnote, I realize I never actually stated the purpose of the
exhaustive search in the proof, which leaves a rather significant
disconnect for people that don't make the connection automatically.
What we are searching for are the new points that were added in the
construction of a basic 4-chromatic graph. In a sense, we are seeing
whether the vertices directly connected to some particular vertex are a
set of boundary points of a basic 3-chromatic graph (or really, any
3-chromatic graph, which if the conjecture about basic 3-chromatic
graphs being inherent in all graphs of chromatic number 3 is true,
amounts to the same thing). The scope of the search is the number of
vertices removed from the initial vertex that we have to examine.

If it is necessary, I can prove that this is the most efficient
algorithm possible (other than guess-and-check, which may actually be
faster--as is the case for 2-coloring), though I have a hunch that this
statement may be equivalent to--or at least follow quickly from--what
was proved by Razborov and Rudich regarding "natural proofs."

does Razborov and Rudich's proof actually imply this, or is it wishful
thinking on my part?

Hello Sirs,
Here an algorithm for 3 colors:
Either G a planar graph which A 3-cliques as cliques maximum, one notes

each 3-cliques by triangle.

G contains several triangles, to place the one to dimension others, or
to separate by vertex.


1) Zone of obligatory colour application simple:
If one gives to a triangle colors 1,2 and 3, one can find
vertex which will be coloured in an obligatory way, after having
all the zones there is the following result:
A- There has is a zone with 4 colors, that applies that G cannot be
colour with 3 colors.
B- There N are no zones with 4 colors, one cannot nothing say...


2) Zone of made up obligatory colour application:
A zone is known as made up if it contains 2 or more of the simple zones

in such manner that the colour application of zone I obliges the colour
application of
zone J, after having all the zones one has the following result:
A- There has is a zone with 4 colors, that applies that G cannot be
colour with 3 colors.
B- There N are no zones with 4 colors, then G is to colour with 3
colors.


the number of the traingles in this case, compared to the numbers of
the vertex is polynomial: t= (n-3) *2.

Two simple zones cannot thus have the same triangle the number of the
zones is also polynomial.

Suppose that G is coloured by 4 colors, in this case a vertex (4) is
assistant at the three vertex (1, 2 and 3). If 1 is in Z1, 2 in Z2, and
3 in Z3; since the vertex are coloured forcing then there is a relation
enters to, the 3 zones form a zone made up.

Remain the case general, if the graph has 4-cliques then it could not
be coloured by 3 colors.

.

Relevant Pages

  • Re: P is not equal to NP (and this is why)
    ... same way as a single edge, and a k-chromatic graph can be transformed ... In each even iteration of this ^3ERS, ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)
  • Re: a proof for consideration
    ... same way as a single edge, and a k-chromatic graph can be transformed ... initial vertex 4 and vertex 2 of that iteration. ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)
  • a proof for consideration
    ... same way as a single edge, and a k-chromatic graph can be transformed ... In each even iteration of this ^3ERS, ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)
  • P is not equal to NP (and this is why)
    ... same way as a single edge, and a k-chromatic graph can be transformed ... In each even iteration of this ^3ERS, ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)
  • Re: P is not equal to NP (and this is why)
    ... same way as a single edge, and a k-chromatic graph can be transformed ... In each even iteration of this ^3ERS, ... Such a construction across iterations creates a ^3ERS that cannot be ...
    (sci.math)