The chromatic number of the plane is at least 5

Anything goes, but keep it seemly...

The chromatic number of the plane is at least 5

Postby dobrichev » Wed Apr 11, 2018 1:38 pm

The chromatic number of the plane is at least 5, by Aubrey D.N.J. de Grey
We present a family of finite unit-distance graphs in the plane that are not 4-colourable, thereby improving the lower bound of the Hadwiger-Nelson problem. The smallest such graph that we have so far discovered has 1567 vertices.
dobrichev
2016 Supporter
 
Posts: 1625
Joined: 24 May 2010

The chromatic number of the plane is at least 5

Postby Mathimagics » Thu Dec 27, 2018 3:35 am

.
Hmm, this had me worried a little. Someone has found a planar graph that can't be 4-coloured? :shock:

But all is well, these unit-distance graphs are in the plane, but not necessarily planar!

The 4-colour theorem is safe ...

(PS: Sorry it took me 8 months to stumble across this post!)
User avatar
Mathimagics
2017 Supporter
 
Posts: 967
Joined: 27 May 2015

Re: The chromatic number of the plane is at least 5

Postby qiuyanzhe » Thu Dec 27, 2018 4:26 am

[deleted]
*EDIT:
The title is so academic that I misthought what it meant.. Maybe with a explanation could be better.
The problem is about coloring every point of the plane, such that any two points with distance 1, cannot have a same color.
7 is sufficient by dividing the plane into congruent hexagons, and a proof of impossibility of 4 is here, which was really new when posted.
Current best is 5≤(chromatic number of the plane)≤7.
Last edited by qiuyanzhe on Thu Dec 27, 2018 8:36 am, edited 1 time in total.
qiuyanzhe
 
Posts: 71
Joined: 21 August 2017
Location: China

Re: The chromatic number of the plane is at least 5

Postby blue » Thu Dec 27, 2018 8:21 am

This one is true, though ... the CNP is >= 5 (and <= 7).
(It's also true, that (CNP >= 5) doesn't invalidate the 4-color map theorem).
blue
 
Posts: 755
Joined: 11 March 2013

Re: The chromatic number of the plane is at least 5

Postby Mathimagics » Thu Dec 27, 2018 5:34 pm

Back in the summer of '72 (oh, those halcyon days!), the map-colouring issue was called the 4CP (4-colour problem, since no proof had emerged).

I was engrossed in my Combinatorics UG course, so I was for some time living and breathing that 4CP.

One night I woke up in the early hours with the proof! Eureka! I wrote it down, gave it the once-over, and went back to sleep, happily dreaming of fame, impressing the girls, etc.

The morning after? I tell you, it still looked kosher, even in the clear light of day.

So I hopped on a bus to go to Canberra Uni and show my lecturer this elegant handiwork.

About halfway there the flaw in my reasoning suddenly hit me, and it was like I'd been hit by that bus! It was all an illusion ... :?

Years later, when the 4CP officially became the 4CT, I was bitterly disappointed. Not about somebody else doing it (I got over that), but that it was so inelegant. I had hoped for, and looked for, some new Graph Theory insight, some subtle undiscovered property of planar graphs that would provide the missing link to a proof.

What a pity I wasted so much time on that! I might have got heavily into Latin Squares, with the same obsessive zeal! But nobody was interested in Latin Square back then ... and the rest is history. 8-)
Last edited by Mathimagics on Sat Dec 29, 2018 1:45 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 967
Joined: 27 May 2015

Re: The chromatic number of the plane is at least 5

Postby Serg » Sat Dec 29, 2018 1:11 pm

Hi, Mathimagics!
About "4CT" theorem - there are many people who don't like that "computer assisted" proof. But nobody prevents them to make "human style" (elegant) proof. Welcome!

You say you didn't selected "Latin Squares" specialization many years ago, because that theme wasn't interesting for general public. Yes, it is important. I am also sensitive to the attention of other people.

Happy New Year and have a good mood (sounds strange :? ) to you and to all!

Serg
Serg
2018 Supporter
 
Posts: 622
Joined: 01 June 2010
Location: Russia

Re: The chromatic number of the plane is at least 5

Postby Mathimagics » Sat Dec 29, 2018 6:33 pm

.
Hello Serg !!

What I really meant was that, in 1972, I didn't pursue Latin Squares because I wasn't even aware of them as a topic of interest. The "hot topics" in Combinatorics at that time were mostly in the area of Graph Theory.

For my UG final year (1973) project I produced an improved algorithm for producing the Chromatic Polynomial for a given graph (related to 4CP but hardly earth-shattering). Then I graduated and disappeared into the real world of kids and jobs and just getting by …

It wasn't until 1978 that the concept of critical sets in Latin Squares began to appear in published journals, and "Number Place" (Sudoku) puzzles began to appear in the newspapers/magazines, although it would be many years before it really took off. Meanwhile I didn't look at any math journals until about 2001. So I missed these developments.

I see that somebody posted somewhere that interest in Sudoku is waning, that forums like this one are on the way out, that nobody is interested any more. :(

I guess you and me and blue and dobrichev and Leren and coloin and all the others prove this is not so! 8-)

Cheers!

PS: And eleven, and qiuyanzhe etc etc ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 967
Joined: 27 May 2015

Re: The chromatic number of the plane is at least 5

Postby 999_Springs » Sun Dec 30, 2018 1:27 pm

wow thanks for making me feel young again :P i remember when i did my final year of undergrad in 2014 i took a representation theory course, and the lecturer spent a lot of time going through character theory and how character tables work and how to do them. during the course, at least 2 people (not me) independently told the lecturer that this part of the course was fun because it was literally just like doing sudoku. he seemed genuinely upset by that :/ that was a while ago, nowadays i only barely remember enough from my group theory stuff to follow this thread and not easily

Mathimagics wrote:I see that somebody posted somewhere that interest in Sudoku is waning, that forums like this one are on the way out, that nobody is interested any more. :(

pretty sure that was me you're talking about, and while i admire your enthusiasm - and agree with you that a band of keen enthusiasts is a great way to keep a tiny community going - it's an unfortunate sad truth that every "fad", just like sudoku in 2005, has a limited lifetime especially if it can't be/isn't commercialised (like puzzle solving competitions can sometimes be). sudoku has lasted a surprisingly long time because, as we know, it can get really involved - but this level of complexity is not going to attract new members. you're welcome to discuss this on the other thread if you want

on the same topic of unsolved easy-to-state problems in graph theory, here's another one that's interesting: it's the future and now every country on earth owns a corresponding region of land on the moon. what's the minimum number of colours you need to colour both the maps of earth and moon such that corresponding regions belonging to the same country have the same colour and no two neighbouring regions have the same colour? 9, 10, 11 or 12?
Once upon a time I was a teenager who was active on here 2007-2011
ocean and eleven should have paired up to make a sudoku-solving duo called Ocean's Eleven
999_Springs
 
Posts: 459
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: The chromatic number of the plane is at least 5

Postby tarek » Sun Dec 30, 2018 6:10 pm

999_Springs wrote:on the same topic of unsolved easy-to-state problems in graph theory, here's another one that's interesting: it's the future and now every country on earth owns a corresponding region of land on the moon. what's the minimum number of colours you need to colour both the maps of earth and moon such that corresponding regions belonging to the same country have the same colour and no two neighbouring regions have the same colour? 9, 10, 11 or 12?

:D :D :D

I thought that China borders 14 other sovereign states :idea:

Happy new year everybody

Tarek
User avatar
tarek
 
Posts: 2851
Joined: 05 January 2006

Re: The chromatic number of the plane is at least 5

Postby Mathimagics » Mon Dec 31, 2018 7:18 am

.
RE: Earth-Moon problem

It could be as low as 4 colours, could it not? If the moon regions are carefully arranged so that each country on the Moon has exactly the same neigbours as they do on Earth? That is, the Earth adjacency graph is identical to the Moon graph.
User avatar
Mathimagics
2017 Supporter
 
Posts: 967
Joined: 27 May 2015


Return to Coffee bar