The New Sudoku Players' Forum

[dobrichev]

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.

[Mathimagics]

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

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!)

[qiuyanzhe]

[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.

[blue]

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).

[Mathimagics]

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.

[Serg]

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

[Mathimagics]

.
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!

Cheers!

PS: And eleven, and qiuyanzhe etc etc ...

[999_Springs]

wow thanks for making me feel young again 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

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?

[tarek]

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?

I thought that China borders 14 other sovereign states

Happy new year everybody

Tarek

[Mathimagics]

.
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.

[coltonz]

Until recently it was known that the answer can be 4,5,6 or 7. The Moser spindle is a simple example of a unit-distance graph with chromatic number 4, and there is a simple coloring of the plane, found by Isbell, based on the hexagonal packing with 7 colors so that no color contains a pair of points of distance 1.