The Graph Reconstruction Conjecture

[00:01] graph reconstruction conjecture. Nice conjecture of course unsolved and a lot problems really the questions you can ask yourself once you start down that path are really nice. So the idea is you're not given a full information.

[00:14] something and you want to know if you can get back the object you had at the start. If you take a graph let's say let me draw something random. This is a graph with the dots and the lines.

[00:27] >> Exactly. We've got vertices, the dots, and the edges, the lines. This graph, bit. So, it means I'm going to take each vertex and I'm I'm going to remove it. So, if I take this guy and I remove it, it means I'm going to take the edges

[00:40] that are connected to it while I go. So, I remove this guy and I'm going to be going to do that for every single vertex. So, I take this guy out. And so, this one remains on its own. If I take out that guy, this time it's easy. Only

[00:54] with a triangle. And finally, if I remove that one, then well, these two edges come out and I'm left with this three guys. So, I've got things I'm were part of the original graph. And now, my question is, if I gave you these

[01:09] guys, knowing what I did with it to get them, can I get back to the original >> And like like can I take the jigsaw puzzle pieces and put them all back together? Mhm. So I mean the first thing you'd like to do is basically what can I

[01:23] know about the original if the original graph I'm I'm only given this four >> So I have been given the information that in each case just one vertex was >> right. >> You know how these guys came to be. You

[01:37] Maybe I want to know a first thing I can know is like how many vertices in my >> That must be easy to figure out. >> Yeah. How would you do it? Well, I would just count the number of vertices in the subgraph and add one.

[01:53] to figure it out. So, you've got it's the number of vertices in the subgraphs plus one, as you say. Or I mean, if I just, you know, let me I'm going to call these guys cards. So, I'm just going to draw a square around each of them.

[02:07] >> Yeah, we call these that you're calling them cards. of cards is going to be called a deck. This is going to be my deck of cards. I can also simply count the number of cards because I removed each vertex

[02:21] the number of cards in the deck. So okay, I get back this information pretty easily, right? But clearly that's not going to be enough. I only know that my original graph has four vertices. Well, good for me, but not good enough.

[02:34] graph when you're looking at it? What what kind of easy information do you >> I don't know if it's easy, but I'd want to know how many edges it's going to >> Um um I agree with I want to know how many edges I got. So, how could you know

[02:47] about the number of edges? The thing is, every single time you remove a vertex, attached to it. >> And you don't know necessarily how many edges you lost to the the process. >> You don't. But what you know is that an

[03:01] edge in my kind of graph is always attached to two vertices. So, it's going to be disappearing twice. once like this edge this guy E is going to be removed once when I take out this red vertex and once when I take out the black one. So

[03:17] if I count the total number of edges on all of my cards and I just do the sum going to be counted a certain number of times. So I can just do the sum and divide by a certain number and that number is the number of vertices minus

[03:33] two because there are two times where I did not get that edge. So that's an information that's pretty nice. I can just do the number of edges is equal to just do the number of edges is equal to the sum of the edges on each card

[03:48] >> like across all the cards. >> Yeah. Divided by the total number of vertices minus two. So let's just have a look at what it means here. So we have 1 look at what it means here. So we have 1 2 3 4 5 6 7 eight edges in total if I

[04:03] add the number on each card. >> Yeah. And then each edge has been counted a certain number of times. It has been counted four minus two times in each case. So you just divide that total number by two. So 1 2 3 4 5 6 7 8

[04:18] divided by 4 - 2= 2. That means four edges in total. And that is exactly >> So this number of vertices in your equation means the number of vertices in

[04:30] the original not the number of vertices across all cards. Yeah. >> So like two pieces of information I get back. Okay. Is it enough again? So maybe in some cases it will, right? Maybe in

[04:43] that case we're like, okay, if I if I know there are four vertices and there are four edges and I know these guys should appear in my original graph. Maybe it could be enough. But okay, I want a bit more than that. I want to

[04:57] go with. >> Is that enough? By the way, >> it it feels like with more complicated graphs, it wouldn't be, but enough. I don't think there Yeah, because you've got this triangle and you

[05:09] know it has to be part of it. You know, you're only missing one vertex and one you're only missing one vertex and one edge. So, if I take this guy, this is a >> So, I've got my triangle and I know I need to add one more vertex. So, okay,

[05:22] >> Yeah, >> but there I mean, if I connect, what do I connect my vertex to? either this guy or that guy or that guy which is I mean >> So well well I've got my original graph. I'm happy.

[05:35] We could have done it with just that. >> But this is a bit it feels a bit like how do I start? I'm a bit I want to be a bit more systematic. So something I also like to know about a graph is the sequence of degrees. Degree a degree of

[05:49] a vertex is the number of edges it is attached to. So that guy has degree one. attached to. So that guy has degree one. that guy degree three, this one degree get this, I it means I know how many vertices, how many edges in total, and I

[06:04] know how many edges should be attached to each vertex. That's pretty neat. So I yeah, if I can go that far, maybe that's already good. So I can I can go for the sequence of degrees. And that's easy because if I take a card and I'm like,

[06:17] okay, there's one missing vertex. That's my missing vertex. What is its degree? Well, I know that in total there should be four edges in my graph. Here there are only two. This guy has to be of degree two. It has to be to have the two

[06:31] missing edges. Here the missing guy has to be of degree three because there's only one edge here. Here of degree 1 and here of degree two. So I've got what is called the sequence of degrees. But it feels to me here like if we had a really

[06:45] [clears throat] huge deck of cards, you could still do this process that you've would have no idea where they all were in relation to each other cuz when these them are inside, some of them are outside. So, is this enough? Are these

[07:01] >> Well, I haven't really told you the proper question, right? Have I? I've graph back? What I really want to know is are there different graphs that this could be the deck of the conjecture is about uniqueness up to

[07:15] isomorphism. So I want to know like if I give you that deck and I tell you reconstruct the graph please do you get a unique graph? The conjecture is given a deck of cards that belongs to a graph can you reconstruct the original graph

[07:29] uniquely? So it's called the reconstruction conjecture and a graph is said to be reconstructible if this works. you can uniquely reconstruct it from the from the deck. Just to answer the first question that you posed which

[07:42] has become a trivial question now is the answer if I'm given a deck I can that is yes >> um it's still I mean I can reconstruct a graph but we haven't been very clear on what a deck is right I've told you I get

[07:57] a deck doing this vertex removing operation so actually the question it leads to another questions related to this is if I just give you a bunch of subgraphs How do you know it's a deck? Let's do an

[08:11] are going to be my cards. I give you this and this. Let me go up to three cards. Here's my deck. Is it the deck of a graph? Can you know? Like if we try to

[08:23] take these steps in order. We're like, how many vertices are there in my number of cards, it should be three, right? But then we also said it's supposed to be the number of vertices in each subgraph plus one. So it should be

[08:37] that one. >> Yeah, because a deck a deck should doesn't. >> It doesn't. So I'm just I'm just showing that's called an illegitimate deck. This is not a deck of a graph. This is just

[08:52] at this. Can you play with it? >> Well, you you notice easy that you obvious. I mean, I've got some Yeah, I've got some cards here that we we use to um to show to discuss the problem with classes or just as an outreach

[09:06] activity. And that guy, for example, is a fun is a fun one of um it's it's a fun non-deck. Meaning that if I try to do the two first steps, I'm going to get back something pretty clear. Um there are five cards and all the cards have

[09:20] four vertices. So, that works. My original graph should have five vertices. I can do the same with the edges. I can sum the number of edges in edges. I can sum the number of edges in each card. So I've got 3 + 25 + 2 7 + 2

[09:32] each card. So I've got 3 + 25 + 2 7 + 2 9 + 6 15. 15 divided by 5 - 2 is equal to that's three. So 15 divided by 3 means five edges in my original graph.

[09:44] try to do the sequence of degrees and see if I get something. Well, that guy, >> What? Six. >> Yeah, six. My original graph should only have five edges. Yeah, that's not a deck. That's an illegitimate deck.

[09:58] not really looking for an algorithm, but if you want to try to reconstruct from a it, and you tell them like, well, start from this, it's going to end up saying, well, that doesn't work and why. So, a related question to this conjecture, and

[10:11] I believe it is more studied by computer scientists, is is this is this deck a >> And I'm imagining you can get massive >> course the graph that are of interest in a way are just you know massive but yeah

[10:26] way and I think it's a very fun one because at first you're like yeah well nice cards and you just get back a graph and you're like are these nice cards and you're like are these nice cards well actually oo no so we we went on the

[10:40] because it seems to have so many tangent problems to it >> so my first question then is if I have a debt >> and it's legitimate I I know it's legitimate. Can I always

[10:54] reconstruct at least one graph? Is it can a reconstruction always be performed with a legitimate deck? >> So, I believe it is. And the question is not an expert on the problem and I've never um I've never been interested in

[11:09] the algorithm you actually use to reconstruct the graph. look that up. But but the question that is of interest, the burning question is is of interest, the burning question is is it is each legitimate deck unique to

[11:23] one graph out there? >> Mhm. And so that Yeah. >> That's unknown. I mean it's known for certain what we call classes of graphs. conjecture, we generally say it's been stated in 57 by Kelly and in 60 by Ulam.

[11:38] So that's when it's been stated and >> hang on twice by. So how does don't they >> so that's the way it's generally stated when you look across the internet what I found is that there's kind of not a

[11:52] foreign where people are like this is this guy who stated it first this is that guy but there's a first result related to the conjecture by Kelly in 57 and then maybe it grew up a bit more at that time again people will be like yeah

[12:07] but I know exactly when this was stated I don't I just know that it's roughly definitely involved. This guy is really good with stating fun conjecture and the on the thing >> and what's happened since have we has

[12:20] any progress been made or >> a bet? So at the beginning a bit quickly graphs and you're like yeah that should be easy for such graphs. Um one type of graph that is really easy is what we call regular graph. This is a legitimate

[12:33] deck and one thing you notice is well it's always the same one right first before but it's a multis set. you can have repeated objects. It's unlabeled. You just know that this subgraph is appearing six times in the deck.

[12:47] >> Um so it's always the same one. And if you do the number of edges, the number of vertices, you're going to notice that the sequence of degree is always the same. All your vertices have the same degree. And that's what we call a

[12:59] regular graph. Um you you very easily deduce that information from the card. So the first thing you know is well that graph must be a regular. When you say regular, what do you mean? >> Always the same degree. Each. So a graph

[13:13] >> Always the same degree. Each. So a graph is regular means each vertex has the original graph, so you want to know how many vertices you have in total. You've got six cards. And therefore you have six vertices. And then you want to know

[13:26] the number of edges. And so you do 1 2 3 4 5 6. 6 * 6 36. And you divide by 6 - 2, which is 4. So 36 / 4 is equal to 9. So the original

[13:41] So 36 / 4 is equal to 9. So the original graph should have nine edges in total. And now it means that since on each of these cards you only have six, the missing vertex should always have three edges attached to it. All of the

[13:54] That's what you get when you try to look at the sequence of degrees. It means that when you want to add a vertex to that guy, I want to add it here. It should have three edges attached to it. These two guys are already of degree

[14:07] booked. You can only touch these three guys. Well, that's a good thing. You just connect it this way and you've got your final graph. So all of these guys from the deck directly. You know it's regular of degree 3. And then when you

[14:21] way. You take your vertex, you attach it this way. And that that's very typical of the proofs that are known for this conjecture for certain classes of graphs. You first identify the class of the graph from the deck. We say we can

[14:36] the class is recognizable and then knowing your graph is of this class you can reconstruct it. So basically all those proofs like most of the known proofs for classes of graphs come in two steps. Step one is recognize the class

[14:54] steps. Step one is recognize the class example like G is regular and two example like G is regular and two reconstruct your original graph knowing its class. So the unique way to reconstruct it is this one. So that's

[15:07] what we did on the on the blue deck. >> Do all regular graphs produce decks that are just full of duplicates? >> Um not necessarily. You could have I mean no but if you take one good example is complete graphs which like each

[15:21] vertex is connected to every single other vertex and so when you take one thing but you can really like doing the first steps we discussed you can really easily get that and then you get the second part. So it's it's nice and easy

[15:34] to have these two steps but it also means that for some certain certain class of grass of graphs we don't know one of the two steps or we can only recognize the class but we we can't reconstruct the graph.

[15:47] So like the general results we have the conjecture there it's it's almost nothing. We've got one one lema called Kelly's lema which states more general original graphs and then you've got specific classes like so regular graphs

[16:01] is a very easy proof the trees so these are the graphs that have no cycles inside them so for example that guy is a tree but if I add this this is not a tree anymore there's a cycle trees are um reconstructible and that's a proof

[16:16] from uniquely yeah uniquely yeah it it fits like the conjecture is okay for the for the trees it's okay for the regular graphs. But for many other types, we don't know. And these include classes of graphs that are very well known, such as

[16:28] planer graphs, the graphs when you can draw them without crossing over the >> And for these we only know one of the two steps, for example. So it seems like it seems absurdly difficult. We've got there is no general results for all

[16:43] graphs and you've got so many classes of graphs. So what do you do when you have really I found really fun with this problem. It's a friend of mine who just it's not his area of research either. It was just like I just learned about this

[16:56] conjecture. Isn't this fun? And I was like this is extremely fun. Let me rabbit hole for the next two weeks and I'll be very happy. And you're like okay well why did we take vertices in the first place? Why don't we take edges?

[17:11] slightly different problem and see if it brings something to it. So the fundamental question here is when we run this one vertex algorithm that you showed me at the start is there some fundamental information that is lost

[17:25] graph. >> It seems like there's not like you can >> well I' I've haven't stated the conjecture properly have I because I I should well I don't even need to do it here but if I just take these two cards

[17:39] how many vertices should my original graph have? >> Two. >> Yeah. How many edges? >> We don't know because Yeah, it could either be this guy or it could be that

[17:53] We'll never know. >> Yeah. So, the conjecture is actually valid for graph with at least three vertices because two vertices can have information is lost. >> So, so two is a trivial example.

[18:07] that doesn't work. >> Yeah. But yeah, I mean, have we found graphs that disprove the thing? Like graphs in general, what I consider to be a graph today where was these um this kind of object where there are no

[18:19] multiple edges. I didn't let you try to have this kind of stuff. I also refused to have loops. So I considered some specific graphs, but still very very very large class of graphs. And then people went on well side quests again

[18:31] and said uh but what could we what what could we do that could be different? conjecture if we go a bit further? Just one counter example, just one deck that it forever. >> Oh yeah, for the conjecture would I mean

[18:44] one counter example the conjecture? No, that's been found so far. But people slightly different graphs? Do you know oriented graphs? another piece of paper? >> Yes, please.

[19:00] triangle for example and I put orientation on my edges. All right. >> This is an oriented graph. Um, and for that type of graph, what they call diraphs, uh, there's been infinite

[19:13] conjecture that has been found. If you take what they call a tournament, which is a complete oriented graph on five vertices and you put orientation of the edges, you can actually find two different oriented graphs. Um, there

[19:28] exist another graph oriented in a slightly different way that has the same deck as this one. And so they found counter examples. you can produce easy like lowderee counter examples to the conjecture using slightly different type

[19:40] of objects. So okay that's one one quest that was solved in a way. Um but then so many other questions that should maybe help you and in fact just create other new questions. You know you remember that

[19:54] deck where that has all the same images like these are all the same cards. Do I really need all the cards? How many of them do I need to reconstruct? And that's another question you can ask. Is there a minimal number of cards?

[20:08] >> An inco can you reconstruct from an incomplete deck? my mind buzzing. [laughter] >> Well, there there are different type of questions you can ask. First one was like, you know, um a deck is a multis

[20:22] same card, >> duplicates. >> But what if you don't allow for a multi-et anymore and you only want one copy of each graph? If two graphs are iso two subgraphs are isomorphic, you

[20:35] reconstruct for this? This is the set reconstruction problem. It's a it's a been solved either. >> And do you need to be told one of these is a duplicate? Do you need to be told? >> Good question. What do you impose on the

[20:49] >> But the one I like is really this question of the number of cards. And we kind of turned it into a game. This is going to be a it's a far-fetched game, but imagine I'm playing with you. I'm just uh I've got a deck and you've got a

[21:02] deck. You created one. And the idea was um we all have the same number of cards, but I want you to try to reconstruct the graph in a unique way. Of course, checked for up to a certain number. I know this is going to work because we're

[21:15] not playing with 50,000 cards, but I want you to be as slow as possible. I want to win. So, which cards should I give you? Like each turn, I'm going to a card. I'm like, this provides me with a bit of information, but I don't have

[21:28] have enough. Two cards, I know I don't have enough cuz there between the two missing vertices, there could be an edge or not, so I don't know. And then you give me your third card. I give you your third card. I'm like, now is this

[21:41] >> That is a nerdy game. >> It is a very nerdy game, but I mean, you but I've played it. >> You have played it. works. So I was like how what kind of graph could I draw that would be

[21:54] >> So you and your opponent sitting opposite each other with your decks and you're drawing and Yeah. Yeah. >> Yeah. Completely. And the question I mean um the question is what kind of graph is the hardest to reconstruct in

[22:09] you need? You want to have the maximum of cards needed. And one cool example is this guy. So the graph I'm taking is disconnected meaning it's it is in two components. This is my full graph. This is G. It has two triangles. And now the

[22:24] cards from G, if you remove one vertex, I'm going to be left with this and this, >> But it's always the same. If I remove that guy, I'm going to be left with this and this, this guy, etc. So, I've got this times six. So, I've got all

[22:39] how many will I need to give you so that you're sure this is actually the guy you want? How do you attack the problem? You reverse it. So you're like, if that's a card, what could I get back from it? So let's have a look. I I start from here.

[22:53] You could. Yeah. >> Yeah. I could have tons of things. So I know I have one extra vertex, right? So I could put my extra >> Yeah, it could be on his own. So let's that's that's the first possibility,

[23:05] else could I could I have? It could be this guy, but then it could be Well, it Good news, right? But it could be several other things. Lots of other things. And maybe I won't draw them all, but you can you can just ask yourself

[23:19] like, okay, but so you've got plenty of possibilities. And now once you've done this, for each of the possibility, well, you go back to the original question. You draw their deck and you see how many cards are exactly these ones.

[23:32] Of course, because the conjecture hasn't been I mean there's no counter example. these different graphs is not going to have exactly the same deck or we would negative. That would be great. But no, but one of these guys have has exactly

[23:48] four cards that are exactly the same as this one. So you know that four cards is have this. >> There is a Okay, so there is a graph. produces >> four of these and two other different

[24:03] cards. And so if I only give you the four, you could not distinguish between my original graph and that graph I'm talking about. And so it is like this is an extremal problem like how many what's the maximum number of cards I could give

[24:15] reconstruct it but I could also ask what's the minimal number of cards. So there's what we call an existential number and a universal number of cards and this is another problem. And so all these kind of different problems it's a

[24:27] constellation and you're hoping that it will give give you back some information that can help solve the actual conjecture. But so far it's just to me who's just like been browsing papers that come out. It looks like it's so far

[24:40] problem. It's like more tension stuff. It's pretty cool. I really like it. color the vertices so that adjacent vertices get different colors. So, for

[24:56] example, in this graph, I can color this blue and this green blue and this green >> until we get to term 60 and something. >> until we get to term 60 and something. And at that point, Jake Sulli says to

[25:12] And at that point, Jake Sulli says to the demon, "Fly straight, damn