We're gonna be talking about a problem in graph theory that was unsolved for more than 50 years and very recently someone solved it so people are very excited about this. It is called Hedetniemi's conjecture - which is a bit of a mouthful - named after the mathematician who first came up with it in 1966, I believe it was part of his doctoral dissertation. He conjectured this result about graph theory and for, like, more than 50 years people tried to prove it they tried to disprove it. And no one seemed to be able to make any headway. But now we know, it is not true. So, so I said this is graph theory, so maybe the first thing I should say is that, when I say graph I don't mean a graph like the kind you make at school, where there's the x axis and the y axis; and you're graphing a function or something. It's very confusing, mathematicians actually use the word graph for two different things. So the kind of graph that we're gonna be talking about is what, in most other areas of science is called a network. So it's a collection of nodes or vertices that are connected by edges. Some of some things are connected, some things might not be connected. So this problem that we're going to be talking about is in an area of graph theory called graph colouring. And the idea is that we want to colour the nodes of our network in such a way that whenever two nodes share an edge, they're different colours. So for example, I'll just draw a really simple graph, and then if I wanted to colour this well, you know maybe I'd start by colouring this one red. Let's see - this one, it's connected to that. So I can't colour that one red, so let's make that one green. So this one down here it's connected to the red one and the green one, so I can't reuse either of those colours. So let's colour that one yellow and now this last one, it's connected to the green vertex so I definitely don't want to use green but I could use red or yellow. And I've used three colours which is the smallest number of colours we could use for this graph, and one of the big questions that mathematicians ask about graphs is what's the smallest number of colours I can use? And this is a question that has a really long history; 150 years ago, or so, people were already thinking about this in terms of colouring maps, and how many colours do you need if you want to colour a map, so that no two adjoining countries or states are the same colour? And this maybe doesn't seem like a question about graph theory because you're like, well, there's no vertices or edges, but it's very easy to convert this into a graph theory question by just - 'cause declaring that you know, each each of these states is a node and if two states border each other then let's connect them. So then this question of colouring the map so that adjoining states are different colours is exactly the same as the graph colouring question. So a long time ago people conjectured that that, for maps, the greatest number of colours You'll ever need is four. And it took forever to prove this, it was proved in the 1970s, with this proof that used massive computations - and I think people still don't totally understand what's going on there. But we do know that, for these - the graphs that come from these kinds of maps four colours is enough. I was gonna give you a couple more examples of where graph colouring can come up - just one kind of fun example if you look at this sudoku puzzle. In case you don't know how these work, you're trying to fill in all these boxes with digits from one to nine so that every row has all the digits, exactly once. Every column has all the digits exactly once and each of these little bold boxes has all the digits exactly once. So you might think well, how is this a graph colouring problem? But you can actually translate this exactly into graph colouring. So the idea here is that we're going to be using nine colours. So we have one colour for each of the digits from 1 to 9. We're going to - if we have a node here - we're going to connect it to all the things that can't be the same digit as that.Okay? So, like, we have a 4 in this box so that means we're not allowed to have fours in the rest of this row, or the rest of this column, or the rest of this box. So we end up with loads of vertices connected by loads of edges and then what you're trying to do is - so maybe if we decided that 4 is going to be coloured red, so all these fours here are red. Each, so we'll colour all the numbers that are forced on us - and then we're trying to colour all the other vertices with our nine colors. And, if we do it successfully, if we do it in a way where connected nodes are different colours, then what we've done is we've ensured that we never use the same digit twice in in one of those little boxes or rows or columns. So colouring with nine colours is identical to solving the sudoku. (Brady: Could you use that to solve a Sudoku then? If I was sitting on the train or something) (could I be drawing a graph and like - would that?)
- You could, although I think if you actually tried to draw this graph there'd be so many edges in it, like, getting in the way of each other that it would be harder to see. But you certainly - if you had like nine coloured pencils you could certainly decide to you know, assign each number a different colour and write colours into the boxes instead of numbers and maybe people who are really attuned to colours and visuals might have an easier time Solving sudokus that way. And I want to just go through one more example quickly with you, because this is going to lead right into Hedetniemi's conjecture. We're gonna imagine that we are hosting, maybe a series of weekend parties at our estate, out in the country - because we're very rich. So we're trying to decide who to invite on which weekend, and we want to collect together good assortment of people - like people who we think are gonna enjoy each other's company. Maybe we know each person's job and we - you know, some of the jobs are kind of conducive to talking with each other, you know like a mathematician and an economist will find some common topics - and other jobs are not. So if we wanted to plan out our weekend party schedule, we could start by basically assigning a different colour to every weekend, and then make a graph of all those different jobs. Like just to do a little toy example that's going to lead into what we care about. So, so maybe maybe the people that we're inviting have just four jobs. Like maybe one of them is a schoolteacher, so let's have an economist, math professor, camp counsellor. What graph would we draw that would help us to have good groupings for our party? Well, so, you know the teacher would probably find things to talk about with the camp counselor, you know like managing groups of kids, and they could probably also talk with the math professor, but maybe they wouldn't have such an easy time striking up a conversation with the economist. So what we're gonna do is we're gonna link things together if they don't get along well. Which which might feel a little backwards because you think oh, you know people get along well, we should link them. But remember that what we're gonna do is we're going to use our colouring to separate those people. So we want to link the ones that don't get along. So, you know, teacher and economist, the economist and the camp counsellor, maybe they're not going to find something. And same thing for the camp counselor and the math professor. But these other things, you know like these two, should get along fine; these two, these two. So this is our graph and now what we can do is we can try to colour the graph and that's gonna tell us which weekend to invite each person. So you know let's start by colouring the economist red and then we have to make sure that these two vertices are not red, because they're connected to the red one, but they're not connected to each other. So, you know if I make the camp counsellor yellow, there's no reason why I couldn't make the teacher yellow. And then the math professor can't be yellow because the math professor is connected to the camp counsellor, but there's nothing stopping the math professor from being red, so we can colour our graph with just two colours.
- (Brady: Erica, were you endeavouring to use the minimum colours?) ('cause I mean you could have done the math professor green there, but were you endeavouring - ?) I could, I I could have coloured green and yes, I was endeavouring to use the smallest number of colours possible because now, no one's coming over on Green weekend, that means that I can just loaf around in my pyjamas the whole weekend and binge-watch Netflix. So, I'm good. So yeah, we're trying to use as few colours as possible. So that's pretty simple. So, let's see. So on red weekend I'm gonna invite the math professor and the economist, and on yellow weekend I'm going to invite the camp counsellor and the teacher. So that's pretty simple but now what if we wanted to be a little more sophisticated as as a host. Because we actually know other things about our friends besides their jobs. And so, let's imagine that maybe we also know some stuff about their hobbies. That means that there are more ways that they could get along with each other. So like maybe the math professor and the camp counsellor, they don't they can't really talk shop with each other, but you know, maybe they each play a musical instrument and so they could talk about that. So let's draw a hobby graph. And, I want to keep these graphs really simple, very basic because when we start combining them things are gonna get a little complicated. So I'm just gonna draw something with three vertices and - so let's imagine that maybe some of our friends collect stamps. well we're filming this in Berkeley, so, you know maybe we should have some people who like to do yoga and some other people who like meditation. And if we wanted to connect up this graph; well the people who do yoga and the people who do meditation they're probably going to get along well; but they might not find anything to talk about with a stamp collector. So we're gonna connect things up like that. And now if we try to colour this graph - again we can actually get away with two colours. So we colour the stamp collector red. Then, we're gonna need to colour the other ones not red. So I could colour them two different colours, but since we're trying to use as few colours as possible, we'll colour them both yellow. So now we have a graph for jobs and we have a graph for hobbies and we're going to imagine that these two things can come in all sorts of different pairings. So like we couldn't have an economist who collect stamps and a camp counsellor who does yoga. And another camp counsellor who does meditation. And, and so on - all the different combinations. So now we have a bigger pool of different kinds of friends and we have two different pieces of information, about how they get along. And the question is how do we combine them? So what we're going to do is we're going to make a sort of a bigger graph that, in a certain sense you can think of as multiplying these two graphs with each other. So that sounds kind of weird you know, like how do you multiply graphs? But if you think about all the different pairings that I just talked about, you know, like economist with stamps, economist with yoga, economist with meditation; well, there's four different jobs and three different hobbies, that the jobs can be paired with, so if we want to capture all the different pairings we're gonna need twelve different pairs. So we already feel - see that there is kind of a multiplication feel to this. So I need to draw a graph that has twelve vertices and there's loads of different ways - you know, I could just plonk the 12 vertices down wherever I want. But I want to try to remember some of the structure of these graphs because that's just gonna make it easier. So I'm gonna have like three vertices that correspond to the economist with the different hobbies and three vertices that correspond to the teacher with the three different hobbies and three that correspond to the camp counsellor with the different hobbies and three for the math professor. So those are my vertices and, you know, and - and having arranged them like this we can kind of see who all these different people are. This person here is an economist who collect stamps, right this person is a teacher who does meditation. Right, this is a teacher who collects stamps and so on. And now we need to think about how we're gonna connect all these vertices up and, so, remember we want to invite people who are going to get along with each other in at least one way. They, they don't need to be able to talk about their jobs and their hobbies, but they need something that's gonna, you know, break the ice for them.
- (Brady: One, one compatible thing?)
- One compatible thing. So we want to connect people, by an edge, if they don't have one compatible thing. If there's nothing they could find to talk about then we're going to draw an edge because that's going to make sure that once we colour, they're going to be on different weekends. So for example, the economist who collect stamps, we're not going to connect that person to the teacher who like stamps because they're good, they can talk about stamps, but we will connect the economist to this teacher who likes meditation because we've decided already that economists and teachers don't get along and stamp collectors and meditation people don't get along. And similarly we're going to connect that economist to the teacher who does yoga because there's nothing compatible there. So we draw these two edges and I'm not going to go through how we do all the different edges, because it's the same idea for all of them, but we end up drawing a bunch of edges into this graph. So we've, we've built this graph that's sort of - that we got by in a certain sense multiplying these two graphs together, and mathematicians actually have a name for this it's called the tensor product. So, you know 'product' like multiplying; and they actually use an X symbol to denote it. So like if one of the graphs was called G and the other one was called H, then the tensor product would be written G times H. For some reason graphs are always G and H. So now we've drawn our graph and we want to start planning out our weekends. So we want to figure out a good way to colour the graph. And one thing that would be an easy solution is just to borrow one of the colourings that I already did. Okay? So like we could just take the colouring that I did here and basically use it to colour this graph, like just colour all the stamp collectors red, like that. You colour all the yoga and meditation people yellow, and that's definitely gonna be a valid colouring of this graph because we already knew that that was a way to guarantee that people who are at the same weekend would find things to talk about. So, you know, basically I just ignored their jobs and focused on their hobbies. Or I could have done it the other way; I could have said I'm just gonna focus on their jobs, so I'm gonna colour all the Economists red, no matter what their hobby is, and let's see, and all the math professors I'm gonna colour them red too. And colour all the teachers yellow, and colour all the camp counsellors yellow. And that's a different way that I could decide who to invite for which weekend - I can just focus on their jobs or I can just focus on their hobbies, and get a colouring either way. Two different colourings of this graph. But the question is is that the best we can do? So in these simple toy examples, it's obvious that this is the best we can do. But if I started drawing more complicated graphs, it's not obvious at all. You know, maybe the job graph needs eight colours and the hobby graph needs 13 colours and then the tensor product; well, we know there's one way to colour it using eight and one way using 13. But maybe there's some way that uses only four colours. So, so that's the question that we want to understand because you know, if we can use fewer weekends, then that would be nice. (Brady: More Netflix days)
- More Netflix days, yes In1966 Hedetniemi conjectured that there is nothing better that you can do. There's no better colouring than the ones you get from these graphs. (Brady: So the minimum colouring on one of your original graphs is the minimum for your mega graph later on, your tensor graph?) Exactly and this conjecture stuck around for more than 50 years. People could not figure out how to prove it or how to disprove it. They did make some progress with trying to come up with a proof, they showed that any time that your, your job and hobby graphs are simple enough that they use four or fewer colours, then it is true that the tensor graph will just need the same number of colours as whichever one of those is simpler. But, but they couldn't get beyond that. (Brady: So it only takes one lucky person to make one and colour it with fewer colours to bring it all down?) Well, exactly and that is what eventually did happen. Now, if you think about this conjecture, I mean I personally found this conjecture surprising. Because if you think about it, you know so these two colourings that we made, by just focusing on one of the graphs, they're forgetting about a lot of things you know about your guests. So, you know, if I use this colouring the one that comes from the jobs to colour my graph, well, you know, maybe there were some people who were compatible that I separated unnecessarily. Like, you know, so a camp counsellor who does yoga could have come the same weekend as a math professor who does meditation, but I split them up because I was only focusing on their jobs. (Brady: It almost feels like your colouring option that you showed me there for the tensor graph was like the lazy option) Yes, they are the lazy options, where we're just kind of throwing away a lot of what we know. And so, so it seems very plausible, if you combine everything, you know, you could get away with fewer weekends. But it turns out that it's really, really hard to concoct an actual example of graphs where that is true. And so, you know decades went by and no one found a counter example until recently; a mathematician named Yaroslav Shitov came up with one.
- (Brady: I'm so excited. I'm dying to see it!) I am not going to draw it for you, and I'll explain why soon. So I'm gonna tell you a bit about how he, like the nature of the graphs that he came up with, and then I'll explain to you why I'm not gonna draw. So what he did is he started with some graph. Let's just call it G, and then he constructed, like for the second graph, you know, if G is our jobs graph and for the hobby graph he constructed what mathematicians call an exponential graph, based on the original graph. We have our graph G, maybe we choose a palette of colours, you know, like however many sharpies I have in different colours. And we think about all the different ways we could colour our graph; and, and and I mean like really any kind of colouring. It's okay if connected edges have the same colour; just any way of slapping colours onto vertices. And the exponential graph is a graph in which every vertex represents a colouring of my original graph. So any possible colouring is going to be a vertex in this exponential graph. So, so there's a lot of different colourings, in fact exponential is - the reason it's called exponential is if I have four colours, then I can colour this vertex four colours, and that one four colours, and that one, you know four different colours. And so the number of different combinations of colourings is going to be like, you know 4 to the however many vertices I have. So that's why these things are exponential. But then he showed that if you choose your original graph in just the right way and choose just the right number of colours for building your exponential graph; then if you take those two graphs and tensor them together in this way, you're gonna end up with a tensor product that needs fewer colours than either of those two graphs. And I don't think that he spent a lot of time, like really trying to optimise these, these numbers. Like he just wanted a counter example. You know often when mathematicians are trying to build a counter example to something, they'll just make all the numbers just like, as big as they need to make all the calculations really easy. So I think he did that and so the graphs that he ended up describing are absolutely humongous. It said like the, the graph G, the like the first graph, had, like 4 to the 100 vertices, and the exponential graph had four to the ten thousand vertices. So I, I typed it into Google's calculator and it told me that the answer was infinity. So, according to Google at least this, this exponential graph has infinitely many vertices. And so I'm here to tell you actually that four the ten thousand is not equal to infinity; but it is a really, really big number. It's um, it's roughly equal to 1 followed by 6000 zeroes. Most estimates of the number of particles in the observable universe are like one followed by 80 zeroes. Then this is 1 followed by 6000 zeroes. (Brady: Okay, I'm not so ask you to draw it then, you're okay) I'm not gonna draw it and um, you know, I don't know if there's anyone out there who has that many friends. Just because his examples, his counter examples are that big, it does not mean that you need to go that big to get to a counter example. So, at present mathematicians don't really know how small the counter examples can be. So it is possible that there are examples out there that are of a size that is you know, sort of totally reasonable and could actually correspond to some, you know, something that you could actually care about and could fathom in the - you know in the in the observable universe. But that is something that we don't know yet. But now we know the conjecture is false, and so, now mathematicians can start chipping away at, you know, like how small can these counter examples be. ...he is still alive.
- (Brady: Now, you're a journalist, did - ) (Brady: and I know you've written about this, did you speak to him?)
- I, I was in touch with him by email and he said that he was delighted. And he, he was not at all invested in his conjecture having to be true. He was just happy to get an answer after 50 years. Whether you're chilling on the sofa or out walking the dog, there can be few simpler pleasures than losing yourself in an audiobook. And when it comes to audiobooks, it's got to be today's episode sponsor Audible. Their selection is huge, there are plenty of math books, of course, or you can go for my favourite audiobook so far; that's endurance by Alfred Lansing. It's a cracking true story, simply told, beautifully narrated; you'll really feel like you're stranded in the Antarctic ice with this band of incredible explorers. It's an amazing audiobook. Really, give it a listen. Now if you're already on board with audible, don't worry, you can also gift it to a friend or family member. Let them share the joy, and for a limited time you can get three months of Audible for just $6.95 a month, that's more than half off the regular price. You go to audible.com/numberphile - or if you're in the US you can text numberphile to 500 500. Again, audible.com/numberphile or text numberphile to 500 500 - that's in the US. Get that great discount. Thanks to Audible for supporting this episode. [Previews of more videos]
Disproof was published on May 6th, 2019 for those of you who were wondering
https://arxiv.org/abs/1905.02167
Was hoping to get a rundown on graph theory. Was not disappointed. Solid video.
How are the edges to the exponential graph decided upon?
So if we know there's a counterexample at least at ( 4100 ) x ( 41000 ), what size of a lower bound do we know where the conjecture works for?
Obvious question:
Has anyone used rote computer search of graphs of size n and m to check Hedetniemi's conjecture?
LOL @ google thinking 410000 = infinity
Did anyone else notice that the example product graph was “disconnected”? Is this because both G and H were connected in a “linear” sense? I’m only familiar with topology and set theory so pardon any incorrect jargon.
This was an awesome video! Thanks!