Re: I have a paper on graph coloring
- From: matt.zellman@xxxxxxxxx
- Date: 7 Aug 2006 18:09:34 -0700
Proginoskes wrote:
matt.zellman@xxxxxxxxx wrote:
Proginoskes wrote:
I don't have a lot to say until right after "as Jaap pointed out" ...
Feel free to scroll down there.
matt.zellman@xxxxxxxxx wrote:
Proginoskes wrote:
matt.zellman@xxxxxxxxx wrote:
Proginoskes wrote:
matt.zellman@xxxxxxxxx wrote:
Dave Rusin wrote:
In article <1154473500.376403.58120@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<matt.zellman@xxxxxxxxx> wrote:
That is, I almost have a paper on graph coloring, because while I have
everything worked out as far as I can tell, I have no idea how to put
it together in order to submit it for publication.
What I need now is probably someone who has actually published
something on graph theory and is willing to coauthor this paper with
me.
If you "have everything worked out", then the paper is written, and it has
one author -- you. It would be inappropriate of anyone else to claim to be
"author" of a paper to which he or she has not contributed scientific ideas.
Indeed it would, which is why I qualified my statement with "as far as
I can tell." It may well be that everything I've come up with stands on
its own, but it could also be the case that I have overlooked something
that people with more experience would easily recognize.
Then you'll have to send a copy to someone, and let them go through it.
That's the safest way to do it.
You should post what your main theorem(s) are, what your necessary and
sufficient conditions for k-colorability are. Then a wider group of
people can see what you've done, and you're likely to get a better
response about whether what you've done is new.
Very well, then. (If anything in this is unclear or confusing, I can
clarify, but I'm going to do my best to get the basics out for now).
This is only going to be a first-view reaction. I might post other
comments later.
Concept 1:
There exist certain graphs that, when colored with k colors, contain at
least one pair of nonadjacent vertices that will never be the same
color. I have dubbed such graphs "Edge-Replacement Subgraphs in k
Colors" or ^kERSs for short. Such a graph can be used in the place of
any edge in any graph with chromatic number k, grafting the
aforementioned pair of vertices onto the endpoints of the edge we mean
to replace. This edge-replacement does not change any of the valid
colorings with respect to the original set of vertices--that is, it
doesn't make any previously valid colorings invalid, or make any
previously invalid colorings valid. The process of edge replacement is
a lot like fractal iteration, and can be carried out indefinitely. I
call this "expansion of a graph by edge-replacement." The reverse of
this concept, reduction of a graph by edge-replacement, will also turn
out to be important.
(1) This is an idea behind Steinberg's Conjecture, that any planar [=
you can draw it in the plane without crossing edges] graph which does
not have any cycles of length 4 or 5 will be 3-colorable. If you look
at the graph at http://math.asu.edu/~checkman/steinberg5cycle.jpg , you
can see why the condition about 5-cycles is necessary; this graph has
no cycles of length 4 or length 5, but is not 3-colorable. The graph
between the vertices u and v is one of your ^3ERSs.
Are there any ^3ERSs which have no cycles of length 4, 5, or 6? If so,
a counterexample to Steinberg's Conjecture would be possible to
construct.
That's a good question. I haven't really looked at that angle yet. The
examples of ^3ERSs that I have found all seem to have cycles of 4 in
them (except the one you just showed me, of course).
(2) A problem would be if you had a ^kERS (let's call it H) as part of
a graph G. If you replace H by a single edge, the chromatic number
might go down by a lot, especially if the chromatic number of H is
high.
The way I have been using ^kERSs, I've been disallowing expansion by
^kERSs with ks different from the graph that is being expanded. It
seems as though this wouldn't really be practical if we are actually
trying to determine what the chromatic number is for the original
graph, but we can definitely say that if you were to replace H by a
single edge, and the resulting graph has a chromatic number less than
k, then the chromatic number of G is k. The concept is not diminished
in usefulness, because it still helps us to establish a lower bound on
the colorability of a graph.
Concept 2:
Every graph of chromatic number k has at least one set of k or more
vertices which in all valid colorings of the graph are never colored
with less than k colors.
This I think is false; consider the pentagon, which has chromatic
number 3. (See http://mathworld.wolfram.com/CycleGraph.html ; a
pentagon is a graph like C_5.) If you call the vertices v1, v2, v3, v4,
v5, in order, then
if S = {v1, v2, v3}, let C be the coloring where
C(v1) = C(v3) = 1, C(v2) = C(v4) = 2 and C(v5) = 3;
if S = {v1, v2, v4}, let C(v1) = C(v4) = 1, C(v2) = C(v5) = 2, C(v3) =
3.
In both cases, you should get a coloring that contradicts Concept 2.
(All other choices for S can be handled by the symmetry of C_5.)
The pentagon is a "edge-minimal" graph that needs 3 colors; if you
delete any of its edges, you get a 2-colorable graph. It is also useful
in other contexts in Graph Theory results, so that's what I tried
first.
as Jaap pointed out, you missed the part where I said *k or more*. This
makes it trivially true, and explains the part below where I say, "A
graph may have only one set of boundary points, which is the entire set
of vertices in the graph..."
Yes, and the pentagon is an example where there is only one set of
boundary points. (I'm glad I include "I think" in that post! 8-))
This might be tied in with the fact that the pentagon is a minimal
3-chromatic graph; that is, if you delete any vertex from it, you get a
graph with chromatic number less than 3. You aren't quite looking at
the minimal k-chromatic subgraphs of G, but something close.
To tie this in to the definition of a "basic graph" I gave further
down, the reason the pentagon has only one (trivial) set of boundary
points is because it can be constructed 5 different ways. That is, you
could expand each 2-colorable graph to a chain of four vertices, and
then add the last vertex, connecting it to the endpoints of that chain.
The problem is that we don't know which vertex was the last one to be
added. So, in a sense, we could say that the pentagon is a
superposition of 5 basic graphs, each with different construction, and
therefore different coloring.
(Not that I intend on rigorizing the concept of superposition in this
sense, but it may be helpful for illustration)
Every minimal k-chromatic subgraph H gives you a set of boundary
points, but not necessarily the other way around, because the subgraph
induced by the set of boundary points might be (k-1)-colorable. (A
(k-1)-coloring of H might not "extend" to a k-coloring of G.)
I'm not sure I understand quite what you mean by this...
If H is a subgraph of G, then a (proper) coloring C of H extends to a
(proper) coloring C' of G if C'(v) = C(v) for all vertices v of H.
If H is a subgraph of G whose chromatic number is k, then V(H) is a set
of boundary points. But if you have a set of boundary points, it's not
immediately clear that the subgraph they induce is k-chromatic.
Yes, that is true. If it were not, there would be an easy solution to
the 3-coloring problem. (Namely, to look at the complete set of
boundary points of G and see if the subgraph they induce--the entire
graph G--has a chromatic number greater than 3)
Actually, this "easy" solution would still require exponential time in
the worst case, but that's kind of the point of the proof... ;-)
I've been calling all such sets of vertices
sets of "boundary points." A graph may have only one set of boundary
points, which is the entire set of vertices in the graph, or it may
have many sets of boundary points ranging in size from k vertices to
the entire graph.
Concept 3:
A basic graph of k colors is a graph constructed by taking a basic
graph of (k-1) colors, adding one vertex, and adding edges between that
vertex and at least one set of boundary points of the basic graph of
(k-1) colors; or a graph that is expanded from a basic graph of k
colors by edge-replacement. The basic graph of 1 color is a single
vertex.
It's a good idea, but since Concept 1 is on shaky ground, and Concept 2
is not true, I wonder whether Concept 3 is useful.
(Don't feel bad; most good ideas fail. If you read books, you only see
the ones that succeed. 8-))
In light of what follows, _this_ is actually a definition. (The
definition of a "basic graph" --- BTW, I am not immediately aware of
any terminology related to what you're talking about. People who focus
their attention on graph coloring might know, though.)
General Definition (necessary and sufficient condition for
k-colorability):
A graph is k-colorable if and only if it contains no subgraphs which
are isomorphic to basic graphs of (k+1) colors.
This would actually be a theorem.
Now, I realize that this really doesn't look like an interesting or
useful definition, but the whole point of that part of the paper is to
show that there is not a more useful definition (Though, this
definition is sufficient to serve as a basis for a proof of the
four-color theorem). For example, while it can be shown that the
special case of 2-colorability can be stated in terms of odd cycles, I
can show that no elemental analysis (by which I mean an analysis of the
elements--vertices, edges, faces, etc.), can possibly be more efficient
at resolving the question than the definition I stated for higher
numbers of colors.
Since there are only two kinds of properties possessed by a graph--the
properties of its elements, and the properties of its structure--this
is sufficient to limit the question to analyses of structure for higher
cases (k>2).
(Shall I go on? or are there objections to resolve first?)
Yes, there are a few things to take care of first.
The thing with k-colorings is that k=1 and k=2 are easy ("trivial"),
whereas k=3 seems to have a much higher level of complexity. (For
instance, the time it takes to find a 1- or 2-coloring is at most a
constant times the number of vertices --- "O(n)" --- but no one thinks
there's a procedure to 3-color a graph that runs in O(n^k) where k is a
constant. This is directly related to P vs. NP, of course.)
And that, I am fairly sure, is what I have proved.
(that there is no procedure to deterministically 3-color a graph in
polynomial time)
If that's one of your results, it will directly establish that P is not
NP. It also makes me (and probably anyone else you show it to) wonder
whether your proof is correct, and that there might be a subtle mistake
in there. This should NOT be taken as an attack against you or your
proof; it's what's called "healthy skepticism", since many people have
tried settling P vs. NP. (Any short proof of the Four Color Theorem,
Goldbach's Conjecture, The Infinitude of Twin Primes, etc., would also
raise skepticism.) But if your proof uses a new idea, it could end up
being correct.
Indeed, I definitely expect a lot of skepticism, which is why I'm
really hesitant to claim P != NP as my primary result. I'd rather get
criticisms back on specific parts and pieces of the argumentation than
an all-in-one "nutjob" dismissal.
I got one of those from one of my profs last fall when I had what I
supposed was a short proof of the four-color theorem--it had errors in
it, but he didn't address them, he just dismissed it out of hand. It
kind of made me want to get back at him by proving it solidly, which
eventually led me here...
Some people will simply refuse to look at a proof of the 4CT that
isn't, say, 30 pages long, because of its history of false proofs.
--- Christopher Heckman
Yes, I know it happens all the time. But in mathematics the practice is
mostly frowned upon and (hence) not all that common. Most common
exceptions probably involve thesis advisors who "practically wrote that
paper themselves", but I'll bet it's at least as oommon for an advisor
(and true coauthor) to insist on NOT taking published credit for the
paper, so as to help out his or her student professionally.
To the OP: find a journal in which comparable papers have appeared.
(You _have_ started reading papers before trying to publish one, right?)
In the front matter or endmatter of the journal you will find instructions
to authors, telling you what to do with your magnum opus. It's common
to take the paper on the road, so to speak, delivering a summary of it
in a seminar talk somewhere; at such an occasion you will get helpful
feedback, and can ask someone for assistance.
This is sort of the root of my problem. I approached the subject of
graph theory from scratch, and picked up concepts as I needed them from
whatever papers, articles, and summaries I could find. As a result, the
language I use to describe both the problem and the solution are rather
different from what is apparently standard. I can almost always
understand what I'm reading (usually with a bit of extra research on
the side), but trying to formulate an argument in what amounts to a
language I haven't quite learned to speak very well is, as you can
imagine, kind of intimidating.
Hopefully you've checked out MathWorld's Graph Theory page? And maybe
Wikipedia? Of course, you chould go to your local university and check
out a textbook on Graph Theory. (They should be around QA164.)
http://mathworld.wolfram.com/GraphTheory.html
http://en.wikipedia.org/wiki/Graph_theory
--- Christopher Heckman
No doubt. I've found both websites excellent places to start, and
picked up as much as I could from them. I looked at a couple of
textbooks last fall, but at that point, the material was more opaque
than I could handle. It would probably be easier now, but I'm no longer
at the university, which tends to complicate things a little.
The big obstacle for Graph Theory is the vocabulary; you get a lot of
terms "thrown at you" at the very beginning. Most will have some sort
of visual counterpart, and once you know the picture that goes with the
concept, life gets easier.
It's very visual.
That is not to suggest that I am not confident in the soundness of my
arguments, only to say that I could really use some help translating
them into something more formally acceptable. I have been leaning
towards considering this a significant enough contribution to both the
actual paper and the ideas themselves to be considered authorship, but
that may not necessarily be the case.
In any case, whether or not I need a coauthor, I definitely need a
translator, or someone to guide me through translating it myself.
You can also "publish" your paper at arXiv.org .
dave
I'm not ruling it out, but I would be much more satisfied with a
conventional publication.
.
- Prev by Date: Re: JSH: Yet another test
- Next by Date: Re: Complex Analysis Iteration Question
- Previous by thread: Re: I have a paper on graph coloring
- Next by thread: I have a paper on graph coloring
- Index(es):
Relevant Pages
|
