WingNews logo WingNews GitHub [2]
top | item 21872358

A Breakthrough in Graph Theory [video]

226 points| kgwxd | 6 years ago |youtube.com | reply

25 comments

order
[+] gwf|6 years ago|reply
Humble brag: Stephen Hedetniemi was my first advisor at Clemson, and I took CS101 with him back in 1985. Both faculty and students were in awe of his intellect, kindness, and modesty. What a delight to stumble upon him this morning. Thanks for posting.
[+] tromp|6 years ago|reply
I'd like to know the best known lower bound on graph sizes that disprove the conjecture. Could there be graphs of just a few dozen nodes that disprove it? Has anyone tried to find a counterexample by brute force search?
[+] rowanG077|6 years ago|reply
it's NP-hard to determine the chromatic number of a graph. So I'd wager you wouldn't get far with a brute force approach.
[+] gorgoiler|6 years ago|reply
Congratulations to Numberphile on getting to pi million subscribers.

Back in the 1990s explanations like this would be pretty common on BBC 2’s Horizon. Though not nearly as detailed, Horizon wasn’t scared of tackling complex material in a way that only appealed to niche viewers. That era of television might be over but Numberphile has very much picked up the baton. The filming style of Numberphile, especially with the delivery-to-producer rather than to camera, the natural lighting, hand held filming, and the occasional interjections from behind the camera, always bring great waves of nostalgia for the days of hard BBC science reporting.

[+] SlowRobotAhead|6 years ago|reply
Help me understand... if dude proved it was false with 4^10000 exponential graph, why hasn’t a smaller tensor been tested? If he could derive a solution with a large set, shouldn’t it be easy enough to test a half size set and classic sort out where the smallest solution is?
[+] walleeee|6 years ago|reply
IANA graph theorist, but I don't think it works like that. Sounds like his graph G (with ~4^100 nodes, from which the 4^10000 node exponential graph and the counter-exemplary tensor product itself derive) is a bespoke construction. I don't think it's possible in practice to just drop nodes from it and test whether the condition holds for the new tensor product. There are 4^100 ways to remove r = 1 node from an n = 4^100 node graph. Increase r and the number of combinations you'd need to test shoots through the roof. Without some way to shave off (the vast majority of) candidates, the possible solution space seems way too big for brute force search.

Someone with real expertise, please tell me if I'm wrong.

[+] arbitrage|6 years ago|reply

[deleted]

[+] dang|6 years ago|reply
Please don't be mean about people submitting a video like that. Your comment is a mean sandwich: the filling is great information but the slices at the ends are not in keeping with the spirit of this site. That's actually more important, because it relates to the long-term survival of the community.

https://news.ycombinator.com/newsguidelines.html

[+] JshWright|6 years ago|reply
Do you go off on this same rant on every HN post? That's the way HN works... A title that links off to some other content, and an associated discussion thread.

Personally I (not the OP) found the video interesting, and at a good level for someone without a lot of context.

[+] marmaduke|6 years ago|reply
Can you remove the complaint about edutainment so we can up vote in earnest your summary?
[+] abacadaba|6 years ago|reply
I for one appreciate the summary. Need to make an AI youtube summarizer.
[+] krick|6 years ago|reply
So, a single over-exaggerated counterexample to a conjecture, which doesn't really explain anything about the nature of the class of possible counterexamples? Hardly a breakthrough. Clickbait.
[+] walleeee|6 years ago|reply
No one could prove or disprove the conjecture for 50 years. It was considered a very hard problem by very smart people.

I don't know about you, but I've never solved any problems that have stumped people for decades.