A Breakthrough in Graph Theory - Numberphile

A counterexample to Hedetniemi's conjecture - featuring Erica Klarreich.
More links & stuff in full description below ↓↓↓

Thanks to Stephen Hedetniemi for providing us with photos and pages from his original dissertation.

Some more graph theory on Numberphile...




NUMBERPHILE

Videos by Brady Haran

[uyytkuw]

Wow! Yaroslav Shitov is my teacher in university. Wasn't expecting to see him there

[gcewing]

I think I've found a universal solution to all such party problems. You invite one graph theory specialist to the party. Since all the guests are part pf a graph colouring problem, they all have something in common with him.

[davethepants]

People would be surprised how many things from everyday life directly reduce to a coloring problem.

[guinea_horn]

So the smallest counter-example is between 5 and 4^10000 vertices

[Bengt.Lueers]

Gotta love how this comes out right before Christmas, when people gather with their families and commonly wonder why it is so hard to get along with each other.

[kanewilliams]

She is very clear, more of her please!

[Demki]

14:28 Graphs are always G or H because G stands for Graph and H stands for Hparg >:-)

[douro]

Hedetniemi is 80 years old and still teaching.

[mueezadam]

I love these 20 minute videos because it allows the guest to really “sell” the topic. I never knew graphs could be used this way, absolutely fascinating demonstration by Dr. Klarreich!

[zerid]

This problem is so much simpler when your friend graph is an empty graph.
I can color it with 0 colors and binge watch Netflix every weekend.

[robindawes]

I remember Steve Hedetniemi from many conferences in the 1980's - he always had the most interesting problems to work on. It's wonderful that he is still teaching.

[amradio]

I think it was Pandora radio? when it was still just a visual website of nodes(album covers) and edges (labeled with adjectives and genres) when I first thought graphs were actually useful. In this case songs were nodes with typological edge types. Following the edges revealed the decision making for the next song. That one simple case changed my understanding of what could be done with graphs in computing for connecting data by proxy to reveal hidden graph structures quickly. The fewest number of colors in this case would also ensure artists and songs, even by a cover band, would not be repeated and get stuck accidentally in a self referential loop in the graph. I later designed an art museum tour creation app based on graphs where people could name the edge type they wanted to traverse, such as color, material, genre, etc. Worked great. 👍 I went to art school, but math truly makes the world usable.

[pepe]

man how stoked would you be getting an answer to your conjecture after 50 years

[JamesFluker]

I love that the guy who came up with the conjecture was simply delighted to have an answer to the problem. It shows his love of math and learning isn't about ego, but about finding answers.

[Wanon]

Love the subtle jab at Matt Parker: 'Or you could go for my favourite audiobook so far, that's - **scrolls away from Humble Pi audiobook** - Endurance by Alfred Lansing...'

[MK-]

Usually counterexamples and the process of taking numbers "as big (or small) as you need" is really used in analysis.

I remember discussing a possible proof and we were talking about approximating some real valued quantities with rational numbers. The thought process went something like "...we can approximate this number with error epsilon, lets just take epsilon divided by a million to be safe..."

[JimsMaher]

Brilliant introduction to graph theory

[GusTheWolfgang]

I loved how clear and conscise she was expressing herself!

[auntiesueinashoe]

I really liked how Erica explained this, I felt like I really understood it despite not doing graph theory before!

[mikapeltokorpi]

My mother was not into sudouks, because it was "about numbers". I said to her, that do not think those as numbers, but as symbols. She is still doing sudokus - about a ten years later.