About 20 years ago I went to a talk by Jim Propp on the fractional chromatic number of a graph. (Here is a link to a free legal copy of the book on fractional graph theory by Ed Scheinerman and Dan Ullman.)
Let c be a natural number. A graph G=(V,E) is c-colorable if there is a mapping of the vertices of G to the vertices of Kc such that (x,y) ∈ E --> (x,y) is an edge in Kc
Let Kt:k be the Knesser graph: the vertices are all k-element subsets of {1,...,t}, (A,B) is an edge if A∩B=∅. A graph is t/k-colorable if there is a mapping of the vertices of G to the vertices of Kt:k such that (x,y) ∈ E --> (x,y) is an edge in Kt:k. (That is not quite right as that might depend on if you use, say, 15/10 or 3/2 but is close. See page 40-42 in the book linked to above for the formal definition.)
One can also show that this is equivalent to other definitions of fractional chromatic number (one involves a relaxation of an LP problem).
The big open problem in the field and perhaps the motivation for it was this:
Known and the proof is human-readable: Every Planar Graph is 5-colorable.
Known and the current proof is NOT human-readable: Every Planar Graph is 4-colorable.
OPEN: Is there some number 4<c<5 such that every planar graph is c-colorable and the proof is human-readable?
I had not thought about this problem for a long time when I was invited by Dan Cranston to give a talk at a Discrete Math Seminar in Virginia Commonwealth University. Looking over the prior talks in the seminar I noticed a talk on Fractional Chromatic Number of the Plane by Dan Cranston. I inquired:
BILL: Fractional colorings! Has there been progress on finding a number less than 5 so that the proof that every planar graph is c colorable is reasonable?
DAN: Yes. By myself and Landon Rabern. We have shown that every planar graph is 4.5-colorable in this paper! I've given talks on it, here are my slides.
BILL: This is big news! I am surprised I haven't heard about it.
DAN: The paper is on arXiv but not published yet. Also, while you and me think its a great result, since its already known that all planar graphs are 4-colorable, some people are not interested.
BILL: Too bad you didn't prove it in 1975 (the four-color theorem was proven in 1976).
DAN: I was in kindergarten.
BILL: Were you good at math?
DAN: My finger paintings were fractional colorings of the plane and I never used more than 4.5 colors.
DAN: By the way, the paper I spoke about in seminar was about fractional colorings of the plane. The graph is: all points in the plane are vertices, and two points have an edge if they are an inch apart. The ordinary chromatic number is known to be between 4 and 7. Tighter bounds are known for the fractional chromatic number, see the paper linked to above when you first mention that paper.
Some thoughts:
1) I would have thought that they would first get something like 4.997 and then whittle it down. No, it went from 5 right to 4.5. Reducing it any further looks hard and they proved that it cannot be a tweak of their proof.
2) The paper is readable. Its very clever and doesn't really use anything not known in 1975. But the problem wasn't known then and of course the right combination of ideas would have been hard to find back the. In particular, the method of discharging is better understood now.
3) When I told this to Clyde Kruskal he wanted to know if there was a rigorous definition of ``human-readable'' since the open question asked for a human-readable proof. I doubt there is or that there can be, but this paper clearly qualifies. Perhaps a paper is human-readable if 2 humans have actually read it and understood it. Or perhaps you can parameterize is and have n-human-readable for n humans.
4) Why does my spell checker thing colorable and colorings and parameterize are not words?
5) The serendipity: I'm very happy to know the result. I came upon it by complete accident. I'm bothered that there may be other results I want to know about but don't. How does one keep up? One way is to check arXiv's once-a-week or on some regular basis. But is that a good use of your time? I ask non-rhetorical.
Very interesting.
ReplyDeleteA few weeks ago, there was a question on Quora (https://www.quora.com/What-are-the-papers-every-programmer-should-read) on the papers every programmer should read. My thoughts were immediately towards Cook's definition of NP Complete, Karp's 21 Problems, and Google's PageRank - the later two being more readable than the first but all being papers that I enjoyed reading a lot.
This post makes me wonder about papers that CS Theory or Mathematicians should (and can) read, say in one sitting, or without having to already be an expert or reference a bunch of other outside texts to understand them. Maybe not the details of the proofs, but at least the concepts of the paper.
Have you ever done anything like this?
Ryan Williams asked such a question on cstheory.stackexchange
DeleteSee: http://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read
Instead of saying 4.5-colorable (which makes no sense to me since you can't have half a color) is if fair to call it 9/2-colorable?
ReplyDeleteYes.
DeleteI typically call it a 9/2 color theorem. It implies that the fractional chromatic number of every planar graph is at most 4.5, but it is slightly stronger than that.
In graduate school I subscribed to the ArXiv's combinatorics section for a few months and skimmed the abstracts, occasionally reading the papers that looked interesting. I think it was a good way to stay current, but decided it was a bad use of my time. Maybe it's not a coincidence that I'm no longer working in academics :-)
ReplyDelete4) Why does my spell checker thing colorable and colorings and parameterize are not words?
ReplyDeleteBritish English? coloUrable and coloUrings and arametriSe?
Interestingly formulated problem!
ReplyDeleteAs for thought 5, I use feedly.com and subscribe to the relevant arXiv feeds. I subscribe to blogs I read to and such and so it keeps all of these feeds in one place. Just reading titles or abstracts seems to have been good for me
Is there a lower bound on the fractional chromatic number of planar graphs? Anything strictly larger than 4?
ReplyDeleteThe 4 Color Theorem proves an upper bound of 4 on the fractional chromatic number of planar graphs. Any graph that contains a copy of K_4 gives a lower bound of 4. So, to summarize:
DeleteEvery planar graph has fractional chromatic number at most 4, and this bound cannot be improved.
How about a planar graph consist of serially connected three diamond sub-graphs and an edge joining the two degree two vertices of the diamonds. This graph has no K_4 and its chromatic number is 4.
DeleteA few days ago I have proposed a solution (draft) to the unsettled case of Scheinerman's conjecture which was a case in the post
ReplyDeletehttps://rjlipton.wordpress.com/2015/10/29/guessing-conjectures/
Recent version is here
https://www.academia.edu/17504492/Scheinermans_conjecture_is_true_with_only_four_directions
Non-computer proof of 4.5 colorability of planar graphs which is quite new for me but I have made proposition that computer-free proof based on spiral chain coloring (2004) together with the efficient algorithmic solution of three color problem (ICM2014 Seoul) may lead to the resolution P versus NP problem in the affirmative. See
https://www.academia.edu/10213412/From_the_Proof_of_the_Four_Color_Theorem_to_P_NP
and
https://www.academia.edu/7108130/The_Big_Bang_Theory_of_Planar_Graph_Coloring_Solution_of_the_Three_Color_Problem
Hi Cahit,
Deletei attempted to understand your spiral chains proof technique for the four color theorem, but after reading the paper i am not clear on how it works. Would you be willing to give an outline of the proof technique in plain language?
Thanks,
landon
Algorithm 1.[Description] Let S1, S2, ..., Sk be the set of spiral chains of G. Color the vertices from an inner spiral chain towards an outer spiral chain. Color spiral chain from inner towards outer spiral segments. Color the core spiral segment with the color class CC1 = {G, R, Y }. For the other spiral segments use Sk,i =⇒ CC1 = {G, R, Y } , i = 1, 3, 5, ... and Sk,i =⇒CC2 = {R, Y, B} , i = 2, 4, 6, .... An vertex in the core-spiral receive an unique color form CC1 based on the adjacent previously colored triangle. In all spiral segments other than the core-spiral assign non-safe color to a vertex whenever is possible. If non-safe color cannot be assigned use respective safe color of the three color classes. In a spiral segment coloring if an vertex is in the sailing boat sub-graph and cannot be colored properly then switch safe color with non-safe color between the parallel spiral segments. This operation assures three colorability of the current outer spiral segment at any step. Furthermore three colorability of the outer-spiral segment assures always to find an safe color to assign to the last vertex of the spiral chain.
Delete1 Exchange of a safe color of the upper spiral chain with a proper non-safe color of lower spiral chain can be viewed as preparation the rest of spiral chain segment vertices for 3-coloring. Think of hiding the unwanted colored spots on the surface of an cake by pushing them with your finger!
extract from (page 9):
http://arxiv.org/pdf/0710.2066.pdf
The most exciting thing about the proof for me is that it completely eschews Kempe chains. Does this lead to a faster than O(n^2) algorithm for 4.5 coloring planar graphs? Does the 4CT admit a proof without Kempe chains? Does this lead to a faster than O(n^2) algorithm for 4-coloring?
ReplyDeleteHi Landon,
DeleteHave a look to the following to papers:
https://www.academia.edu/541633/On_the_Algorithmic_Proofs_of_the_Four_Color_Theorem
https://www.academia.edu/440527/VISUALIZATION_OF_THE_FOUR_COLOR_THEOREM
Complexity of the spiral chain coloring algorithm is O(n).
No Kempe chains used in the proof. Only switch of a "safe" color of a vertex of the spiral segment S_i with a safe color of a vertex of the spiral segment S_(i-1). This is the only case of color switching when an induced sailing boat sub-graph occur between S_i and S_(i-1). Note that, in this way maintaining 3-colorability of (current) outer-spiral segment.
ReplyDeleteattn to : Landon Rabern
ReplyDeleteand this one also
http://arxiv.org/abs/0710.2066
or
https://www.academia.edu/1577705/A_Unified_Spiral_Chain_Coloring_Algorithm_for_Planar_Graphs