5 ms·

A Breakthrough in Graph Theory [video]

226 points by kgwxd 7y ago

arbitrage 7y ago
Here's an explanation so we don't have to listen to numberphile try to turn this into long-winded edutainment for youtube: A counterexample to Hedetniemi's conjecture - featuring Erica Klarreich. This is about graph colouring. For a short explanation of the topic at hand that's pretty good, see: https://en.wikipedia.org/wiki/Hedetniemi%27s_conjecture https://en.wikipedia.org/wiki/Hedetniemi%27s_conjecture The point of this video is that a counterexample to Hedetniemi's Conjecture has been found. That is, the assertion that tensor products cannot be colored with an unexpectedly small number of colors, is wrong. You can't say this -- that the least amount of colours needed to colour a graph which is the product of two other graphs is the least number of colours needed to individually colour the original graphs. Apologies if i didn't get this right, but let's have a discussion about it instead of shunting people on a message-board off to youtube with no descriptions provided about what this topic actually is.
- JshWright 7y ago
  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.
  - mokus 7y ago
    They may be a bit on the ranty side but I, for one, greatly appreciate the ability to read an abstract in 15 seconds rather than however long it takes to ingest a video and separate the content from the fluff. This is also how HN works: 99% of the time, there’s enough summary and context in the comments that I always just click through to the comments first to find out whether the article/video/whatever is worth the time.
    - JshWright 7y ago
      Absolutely, but the commentor could have just done that, rather than lamenting that we should be discussing it... in a discussion thread that only exists because someone posted the video here in the first place.
    - Klinky 7y ago
      >This is also how HN works: 99% of the time, there’s enough summary and context in the comments that I always just click through to the comments first to find out whether the article/video/whatever is worth the time. Isn't that also a folly of HN? People not reading the articles and rushing to the comments to make some proclamation or put in their two cents.
      - munk-a 7y ago
        Except you can fully understand this topic in a lot less than thirty minutes - I agree that people making half-reasoned arguments is a problem but at the same time you can comprehend the contents of this conjecture and the disproving of it via a few simple statements about graphs or relational algebra.
- abacadaba 7y ago
  I for one appreciate the summary. Need to make an AI youtube summarizer.
  - JshWright 7y ago
    I have no problem with the summary. I think it would have been a very strong comment if it had just skipped the first and last paragraphs.
  - catalogia 7y ago
    Pull the subtitles with youtube-dl, then either read it (should be much faster than watching it) or throw some typical auto-summary software at it first. Something like: `youtube-dl --skip-download --write-sub --write-auto-sub --sub-lang=en 'https://www.youtube.com/watch?v=Tnu_Ws7Llo4'` https://www.youtube.com/watch?v=Tnu_Ws7Llo4'` You can use ffmpeg to convert subtitle files between different formats. SRT is easy to clean up for reading with a a few editor macros.
    - abacadaba 7y ago
      word, ty.
- marmaduke 7y ago
  Can you remove the complaint about edutainment so we can up vote in earnest your summary?
  - gjs278 7y ago
    oh no! they didn’t phrase it the way I like so I can’t push the button!
- dang 7y ago
  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 https://news.ycombinator.com/newsguidelines.html
egdod 7y ago
Here’s a nice write-up by Gil Kalai: https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-morning-news-yaroslav-shitov-counterexamples-to-hedetniemis-conjecture/ https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-m...
tromp 7y ago
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?
- sesuximo 7y ago
  id bet yes
- rowanG077 7y ago
  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 7y ago
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.
gwf 7y ago
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.
bhl 7y ago
There's an associated Quanta article that goes with the video, along with a previous HN submission for that: [1] https://www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theory-conjecture-20190617/ https://www.quantamagazine.org/mathematician-disproves-hedet... [2] https://news.ycombinator.com/item?id=20203707 https://news.ycombinator.com/item?id=20203707
- deleted 7y ago
  [deleted]
SlowRobotAhead 7y ago
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 7y ago
  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.
  - lonelappde 7y ago
    That's right. That's a general proof technique: to assemble a structure from a bunch of parts or layers, each of which adds to or multiplies the size of the structure, and possibly the various factors may be known only by upper bounds. So there is room to improve slightly by brute force or more careful accounting, or a lot by finding an alternate construction.
krick 7y ago
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 7y ago
  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.
bubblesocks 7y ago
I love the way in which this lady broke down the complexity of graph theory into something that anybody can understand. I mean, I understood it.
- lonelappde 7y ago
  > this lady Erica Klarriech, PhD https://en.m.wikipedia.org/wiki/Erica_Klarreich https://en.m.wikipedia.org/wiki/Erica_Klarreich

226 points by kgwxd 7y ago

Here's an explanation so we don't have to listen to numberphile try to turn this into long-winded edutainment for youtube: A counterexample to Hedetniemi's conjecture - featuring Erica Klarreich. This is about graph colouring. For a short explanation of the topic at hand that's pretty good, see: https://en.wikipedia.org/wiki/Hedetniemi%27s_conjecture https://en.wikipedia.org/wiki/Hedetniemi%27s_conjecture The point of this video is that a counterexample to Hedetniemi's Conjecture has been found. That is, the assertion that tensor products cannot be colored with an unexpectedly small number of colors, is wrong. You can't say this -- that the least amount of colours needed to colour a graph which is the product of two other graphs is the least number of colours needed to individually colour the original graphs. Apologies if i didn't get this right, but let's have a discussion about it instead of shunting people on a message-board off to youtube with no descriptions provided about what this topic actually is.

JshWright 7y ago
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.
- mokus 7y ago
  They may be a bit on the ranty side but I, for one, greatly appreciate the ability to read an abstract in 15 seconds rather than however long it takes to ingest a video and separate the content from the fluff. This is also how HN works: 99% of the time, there’s enough summary and context in the comments that I always just click through to the comments first to find out whether the article/video/whatever is worth the time.
  - JshWright 7y ago
    Absolutely, but the commentor could have just done that, rather than lamenting that we should be discussing it... in a discussion thread that only exists because someone posted the video here in the first place.
  - Klinky 7y ago
    >This is also how HN works: 99% of the time, there’s enough summary and context in the comments that I always just click through to the comments first to find out whether the article/video/whatever is worth the time. Isn't that also a folly of HN? People not reading the articles and rushing to the comments to make some proclamation or put in their two cents.
    - munk-a 7y ago
      Except you can fully understand this topic in a lot less than thirty minutes - I agree that people making half-reasoned arguments is a problem but at the same time you can comprehend the contents of this conjecture and the disproving of it via a few simple statements about graphs or relational algebra.
abacadaba 7y ago
I for one appreciate the summary. Need to make an AI youtube summarizer.
- JshWright 7y ago
  I have no problem with the summary. I think it would have been a very strong comment if it had just skipped the first and last paragraphs.
- catalogia 7y ago
  Pull the subtitles with youtube-dl, then either read it (should be much faster than watching it) or throw some typical auto-summary software at it first. Something like: `youtube-dl --skip-download --write-sub --write-auto-sub --sub-lang=en 'https://www.youtube.com/watch?v=Tnu_Ws7Llo4'` https://www.youtube.com/watch?v=Tnu_Ws7Llo4'` You can use ffmpeg to convert subtitle files between different formats. SRT is easy to clean up for reading with a a few editor macros.
  - abacadaba 7y ago
    word, ty.
marmaduke 7y ago
Can you remove the complaint about edutainment so we can up vote in earnest your summary?
- gjs278 7y ago
  oh no! they didn’t phrase it the way I like so I can’t push the button!
dang 7y ago
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 https://news.ycombinator.com/newsguidelines.html

egdod 7y ago

Here’s a nice write-up by Gil Kalai: https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-morning-news-yaroslav-shitov-counterexamples-to-hedetniemis-conjecture/ https://gilkalai.wordpress.com/2019/05/10/sansation-in-the-m...

tromp 7y ago

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?

sesuximo 7y ago
id bet yes
rowanG077 7y ago
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 7y ago

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.

gwf 7y ago

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.

bhl 7y ago

There's an associated Quanta article that goes with the video, along with a previous HN submission for that: [1] https://www.quantamagazine.org/mathematician-disproves-hedetniemis-graph-theory-conjecture-20190617/ https://www.quantamagazine.org/mathematician-disproves-hedet... [2] https://news.ycombinator.com/item?id=20203707 https://news.ycombinator.com/item?id=20203707

deleted 7y ago
[deleted]

SlowRobotAhead 7y ago

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 7y ago
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.
- lonelappde 7y ago
  That's right. That's a general proof technique: to assemble a structure from a bunch of parts or layers, each of which adds to or multiplies the size of the structure, and possibly the various factors may be known only by upper bounds. So there is room to improve slightly by brute force or more careful accounting, or a lot by finding an alternate construction.

krick 7y ago

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

bubblesocks 7y ago

I love the way in which this lady broke down the complexity of graph theory into something that anybody can understand. I mean, I understood it.

lonelappde 7y ago
> this lady Erica Klarriech, PhD https://en.m.wikipedia.org/wiki/Erica_Klarreich https://en.m.wikipedia.org/wiki/Erica_Klarreich