it's really fascinating how similar this feels to the 4-color theorem: you have a planar graph that can be categorized into parts that can behave in two different ways depending on the number of parts (either you need x parts or you need fewer than/more than x parts to fully categorize it) and proving the case for x=3 and x=5 was relatively straightforward but it took a lot of extra time to prove x=4
I wonder how similar these problems are, they're obviously not the same problem, otherwise they'd have a solution to this book problem way earlier, but that 4-color theorem can be reduced to a graph where all the nodes are the areas and the edges are the borders with other areas.
II totally agree with that. Also, there is more suspiscious evidence that hints at some kind of connection between these two problems. For example Toshiki Endo was able to show that any toroidal graph can be embedded in at most 7 pages. Interesting side note, any toroidal graph can be colored with 7 colors. furthermore Toshiki endo points that the upper bounds on the book thickness of a graph and the chromatic number are asymptotically equivalent. They point this out in this paper if you wan to read more about it: Endo Toshiki. The pagenumber of toroidal graphs is at most seven. Discrete Mathematics, 175:87-96, 1997.
I was thinking the same thing. Especially when James introduced the restriction that the edges could not cross and that there were no phantom loops (i.e. maximum number of crossings) it reminded me of the reduction of the 4-color map theorem into the building blocks of map graphs, and how it was impossible to have a 2-d map graph with only points with 6 connections or higher. My instinct tells me there's a connection there, but I have no idea where to even begin with proving that
It's not every day that an explicit solution to a graph problem is found that can be printed on less than all the paper in the universe, one vertex per proton.
I just find it how mind blowing life seems come full circle(-ish). I started watching this channel back in early middle school and Dr Grime was one of the first people on this channel that really stuck with me, and now i'm only a couple semesters away from graduating with my undergrad in Math. I loved growing up with this channel
@@numberphile I'll add my own story. I started watching in middle school too--I specifically remember recreating the argument that 100% of all integers contain the digit 3 for my mom. This fall I'll start a PhD in mathematics!
Dr Grime absolutely my favourite regular on this channel. He knows how to explain things so well that a kid can understand it, and he knows how to scale explanations from the basics up until the higher level stuff. Also, his awkward and enthusiastic demeanour reassures me that he is a real mathematician and a nerd.
I did a project in college specifically about looking at books of knots, every knot can be done with 3 pages (and apart from the unknot they all need 3 pages) so they're a little boring with that respect, but the proof of this is rather simple, and then from there you can give each arc it's own page and that's the arc representation of a knot, and then there's a pretty simple proof of Alexander's theorem using that representation. Just fun stuff.
I’m Canadian, but my parents are from northern England. One particular room in my childhood home had two cupboards, one that contained boots, winter jackets, and mittens. That was the “boot cupboard”. The other cupboard in this room was where we kept our books. That was the “book cupboard”. It was a source of constant confusion.
They're called shelves (made of boards) and enclosed they're called cabinets. A "cupboard" is a series of shelves that hold cups. Also, maybe it was confusing to you all because English people bastardize pronunciation between boots and books? They already bastardize the meaning of cupboards.
@@CharFred-vr1ti Imagine the words 'boots' and 'books' pronounced in a Northern English accent - like Manc or Lanc in general. All will then be clear.
Brady's graphics are the genius of numberphile videos! His interviews are amazing and the knowledge he shares needs to go further. singingbanana needs more sunshine.
I love this! Reminds me of the early Numberphile videos. I'm far from a mathematician, but in this instance, simplicity with everyday understanding makes for a great video that really appeals to a dummie like me. And, James is the best at this stuff. What a great teacher. Thanks for this video, Brady!
Fun fact: a tree can always be done in only one page. Pick a root, and place it on the leftmost point. Afterwards, place all the points of the graph in a depth-first listing, and connect all points. Every subtree will be all together, recursively listed without intersections in the single page.
Instantly thinking about the infamous problem where the points define electricity, water, and gas, and each of the homes need to be connected to each one, without crossing (on a regular sheet of paper).
Yeah, K5 (the complete pentagram - the complete graph on 5 vertices) and K3,3 (the utilities graph, or the complete bipartite graph on two sets of three vertices) are famously the two fundamental non-planar graphs - every non-planar graph has one or both of those two as a "minor" - a minor of a graph is any graph that can be formed by taking a subgraph (some of the vertices and edges, including all the ends of the edges) and then contracting edges (so the two vertices at the ends of an edge merge, with any vertex connected by an edge to either of the old vertices having an edge to the new vertex).
Freeze the video at 7:46 and check out those eye popping numbers on the screen on the wall! 4000+ videos and 1.3 billion views. Way to go Brady and team!
@7:55 If you consider the points B & A to be the north and south poles, then the points t0-t7 will be on the equator. The tighter "blocks" of points can be stretched out along the north-south direction independently. Not sure if that helps you form a mental image or not, different brains visualize in different ways.
Idea for a possible way the two could be related: (actually this doesn’t work. Posting anyway.) Take a planar graph , embedded in the plane in some way. Thicken the edges of the graph, making these edges the nodes of a new graph, and have them be connected if they are neighboring (as in, if they share a vertex, *and* are adjacent in the order they make around the vertex) The result should still be planar. 4-color these new vertices (which, recall, are the original edges). Assign ones with different colors to different pages. ... this construction doesn’t work because it doesn’t have the pages/leaves meet on one line. So yeah nvm.
That's the sort of thing mathematicians must be asking ..... What if you started with a 3-colour map, and did some sort of transformation to end up with a graph that needed a 3-page book?
This reminds me a lot of PCB designing... how many layers of copper do you need for manifacturing the connections you need... don't know if it is exactly the same problem but they definetly seem similar...
With PCBs, you have some additional physical constraints; a via (through connection) connecting any two layers requires a hole that must go through all the layers, and this adds a space requirement which in turn imposes a restriction on the total number of layer changes available.
It’s a version on a theme, it probably has that issue in each of those sub components that you can’t add loops by using the same kind of prevention techniques the GH graph uses.
Looking at the original paper, they talk about the sub structures as “gadgets” which cannot be embedded in three pages under specific circumstances. if you wanna look at the paper it’s in the description of the video.
We got numbers at 10^404 and 10^2135 that are just like 5040, but more firm (if you are stunned at the amount). Infinity is sickening and others have no regard for actual variations in just one number with 404 digits in base 10. Fun. Sine wave is connector of circle and triangle in 2D. I am ahead of the quantum computer!
Great video!! I have an idea for a numberphile espisode that super cool. How the design of a tachymeter dial works regardless of unit, all from a mathematical point of view.
I would like to ask this question: Why is 3 not connected to 1? Should there not be a phantom loop connecting 3 and 1 on a second page? Or is that to distinguish crossed paths?
The idea is that if you can create a "phantom loop" that passes through every vertex, you can use the method of generating a book graph for a planar graph that has a loop and just remove the extra edges afterwards. So all you need to do is add enough edges (without crossing any existing edges) to make a continuous path that goes through every vertex exactly once and comes back to the start, use that method, and remove the edges you added. The tricky part then comes up with planar graphs where it's impossible to do that.
Curiously, the graph in the linked article (see description) shows the same kind of graph with one less cluster (t0-t6 rather than t0-t7), but that graph is also missing 1 line from a symmetry perspective. So it actually may be required.
Let's say you represent a graph as a table with 0 for no connection and 1 for a connection between vertices, then read out the entire table as one single number. Do the resulting numbers have an interesting relationship to structure, type and properties of the graphs they were derived from?
The table you are talking about is called the adjacency matrix. I don't know what you mean by reading out the table as a single value. Summing them would simply give you twice the number of edges. However, how the eigen values and eigen vectors relate to the graph is a whole field called spectral graph theory
@@hampusnyberg6583 Yes. Quote Wikipedia: "For a simple graph with vertex set U = {u1, …, un}, the adjacency matrix is a square n × n matrix A such that its element Aij is one when there is an edge from vertex ui to vertex uj, and zero when there is no edge." With "read out the entire table as one single number" I meat forming a binary number by concatenating zeros and ones contained in A in a certain order. For example: r = A11 || A12 || A13 || .... || Ann Then the question, if r is "interesting" in a very broad sense. Example: if r is prime, does this property relate to properties of the corresponding graph?
there's no guarantee there are any applications yet in pure mathematics, the research comes first, and application comes later (if ever) number theory was for ages thought to be useful only as an intellectual fascination (and was even jokingly lauded by at least one pure mathematician for that) until people started studying methods of cryptography and realized it was perfect for that
I’m assuming the Goldner-Harary graph was partially named after Frank Harary, who I had the pleasure of meeting in his latter days. The special graphs you mentioned near the end each had nearly 3 times as many adages as vertices, so must have an average vertex degree of nearly 6. Was a bit confused at the start around what is allowed on a book page. I’m assuming that we cannot have edges both inside and outside a Hamiltonian cycle, hence why we need 3 pages for a K5 graph.
Once again the proof involved a SAT solver, which just keeps happening again and again with these breakthroughs (the recent 1-tile thing too), and yet SAT solvers still seem to be underused and not widely known about
The first time I saw this type of graph was when someone showed me all the cross-references between the 66 books of the Bible. It was amazing how full that was. Now I can’t help but wonder, how many pages would it take to untangle that one? 📖
I must be missing something, because I can't confirm rhe complete graph formula. Let's start with just one node. According to the formula, you'd need 1 page. But the node sits on the spine, by definition, and there are no edges which would need any pages. So I'd say it' neds zero pages. Similarly for n=2, there the complete path consists of two nodes connected by an edge. The nodes sit on the spine, by definition, and the edge also can be drawn along the spine, so again, zero pages. But then, maybe books are defined to always have at least one page. Well, then let's look at n=3, which according to the formula should need 2 pages. But the complete graph in this case is just a cycle, exactly like the one in the first one-page example, just with one node less. So for n=3 you should actually only need 1 page. For 4 and 5 nodes, the formula does give the correct number of pages, and beyond I didn't check. But for n up to 3, I don't think the formula is right.
No. Imagine a sphere made of rubber. You can poke a single hole and stretch that to become the entire perimeter of a flat sheet of paper (think of stretching the edge of an uninflated balloon until it is a flat rubber sheet.) If you were on a torus, things would be different though. Edit: I forgot to mention the important part, that the hole you poke in the surface can always be placed between lines/points. So no lines will cross the resulting edge of the flattened map.
You didn't know my personal life. I was just trying to handle things and try to help my mom. I never told anyone. I been stressing losing my mom before I knew it. I haven't done anything Or asked anyone for help. I am noting sueing. This was my stress relieving from doing all the responsibility in my house. I never asked anyone's help
Depends. It's called an ambient isotopy in which, if you consider the graph to be embedded in into 3D space (or other sufficient spaces), then you can continually deform not just the two edges in the first picture but the space surrounding them so that the image of the transformation is the second picture. However, if you are considering planar isotopy then you must work with a projection of your graph on the plane and you can only stretch the plane without pulling edges out of it. In this isotopy, pulling the two edges in the first picture through the other edges in the way is not legal since you're tearing the plane around them when you do that. In short, it's only a topology preserving operation, or topological stretching as you put it, if imagine the graph as being embedded in 3D space or something similar. I worked on a paper that was concerned with such things. Here's a fun theorem that didn't make it into the paper: Consider a complete graph with 5 vertices in the shape of a pentagon, such as the graph we were discussing earlier. Furthermore, let us only consider the edges to be straight lines (this is called a linear embedding) and for it to be occupying the plane. Suppose you are told this graph was actually embedded in 3D space in some way that you don't know, leaving you to make guesses about how it looks in 3D based on this "shadow" of the graph. At each crossing you must mark one of the edges as being "on the top" from the perspective of the shadow (a graph with such markings is called a crossing diagram of said graph). Each choice makes a different prediction for what the embedding might look like, with some choices being impossible. Amazingly, there's exactly one crossing diagram up to planar isotopy! That is, just by stretching the plane, you can always make your prediction look like the "correct" one, or into any other legal crossing diagram of any 5 vertex graph with pentagonal shape (pulling a vertex into the quadrilateral formed by the other four vertices is not a planar isotopy, so that distinction must be made).
Could pages be used to give a scale to the non-planarness on a graph? Im trying to cast my mind back to my Uni days and think how this could be used in knot theory 🤔
Certainly one of the stats of a graph is its book number. But we need to understand that a graph's book number can be as large as 4 (as we now know) and still be planar. As for a measure of how non-planar a non-planar graph is, there are numerous variants of crossing-number. Marcus Schaefer wrote a paper which was a survey of some of them --- he listed dozens!
I hope I am phrasing this right. How many different numbers yield a maximum of 4 pages for the book embedding of graphs? is it just one so far? Also, would doubling the number yield 4 pages as well?
I'm very curious about that too. So far I can only think up a use case that involves an electric circuit being implemented on several prototyping boards that are hinged on one side just like a book for maintenance access, but that would only make sense if no jumping wires are allowed, which doesn't seem like a realistic constraint. The concept of a book graph seems very obvious, but abstracting the rules that define a book graph and then matching them to an equivalent problem is hard. In principle, the binding of the book being straight and the pages being planar seems irrelevant to the underlying logic. It's a two-dimensional problem which kind of leaks into the third dimension with every page connecting to all other pages through a single line representing the back of the book.
A network is a graph with named nodes. It would have been nice to defined this in the 1st 20 seconds instead of calling a graph a network. Not all graphs have named nodes so not all graphs are networks.
Здравствуйте! Очень давно подписан на ваш канал, но смотрю ваши ролики с других каналов, переводящих их на русский. Английский я конечно знаю, но понимать терминологию очень сложно. У меня тут вопрос назрел, надеюсь вы его прочитаете: полый шар гомеоморфен шару или тору?
I think you refer to the graph @6:35 in the video. What you are really suggesting is adding a new point to the graph on the line between vertex 4 and vertex 10 (let's call the new vertex 12.) Placing vertex 12 between vertices 6 and 8, you can then draw a line from 4 to 12 bowing down under 6, and one from 12 to 10 bowing up above 8. This is a different graph with a different number of vertices, and illustrates why the problem is so difficult. Adding vertices can actually lower the number of pages required. (Note: each line in a bok can only arc upwards or downwards, not zig-zag through the chart.)
@@rosiefay7283 that's the question at the end but in the middle of the video, he talks about reordering the points so you get _more_ pages. But I agree, the video was much more confused than Brad's videos usually are.
@@unvergebeneid The bit in the middle is just to highlight that you can pick a bad order and increase the apparent book number that way, which means that finding the actual book number of a graph requires more than just finding the best arrangement of arcs for some particular ordering.
@@unvergebeneid He reorders the points to show that you get a different result. But the entire time, he was aiming to minimize the number of pages. If he was trying to maximize it, then you would just have a single edge for every page.
Unfortunate terminology conflict with the paper book analogy here... books have paper leafs that have text printed on their both sides, the two sides are numbered and are called pages. Here in this graph case a "page" is that what is called a "leaf" in the paper book.
Well that's a printing decision, you could print this with one 'page' on each page, but it'd be rather unreadable with transparency involved and with opaque leafs it'd be impossible to see the whole graph at once. Still, there are four 'layers of information' so to speak, which corresponds better to a page than to a leaf.
0:52 I don't know what I find more surprising --- that you wanted to say it again in a "Southern accent", or that when you tried, it was more Scouse than anything else.
it's really fascinating how similar this feels to the 4-color theorem: you have a planar graph that can be categorized into parts that can behave in two different ways depending on the number of parts (either you need x parts or you need fewer than/more than x parts to fully categorize it) and proving the case for x=3 and x=5 was relatively straightforward but it took a lot of extra time to prove x=4
I wonder how similar these problems are, they're obviously not the same problem, otherwise they'd have a solution to this book problem way earlier, but that 4-color theorem can be reduced to a graph where all the nodes are the areas and the edges are the borders with other areas.
II totally agree with that. Also, there is more suspiscious evidence that hints at some kind of connection between these two problems. For example Toshiki Endo was able to show that any toroidal graph can be embedded in at most 7 pages. Interesting side note, any toroidal graph can be colored with 7 colors. furthermore Toshiki endo points that the upper bounds on the book thickness of a graph and the chromatic number are asymptotically equivalent. They point this out in this paper if you wan to read more about it:
Endo Toshiki. The pagenumber of toroidal graphs is at most seven. Discrete Mathematics, 175:87-96,
1997.
I was thinking the same thing. Especially when James introduced the restriction that the edges could not cross and that there were no phantom loops (i.e. maximum number of crossings) it reminded me of the reduction of the 4-color map theorem into the building blocks of map graphs, and how it was impossible to have a 2-d map graph with only points with 6 connections or higher.
My instinct tells me there's a connection there, but I have no idea where to even begin with proving that
No, with 4ct the question was "5 necessary?" (no) and with this it's "4 necessary?" (yes).
Yep, I was gonna mention it myself but first comment I see is this one
It's not every day that an explicit solution to a graph problem is found that can be printed on less than all the paper in the universe, one vertex per proton.
That's because the focus of the work was on keeping page count down- they must have applied it to the proof as well as the pudding!
Honestly it is refreshing to not have 24 books on a book of a graph
I just find it how mind blowing life seems come full circle(-ish). I started watching this channel back in early middle school and Dr Grime was one of the first people on this channel that really stuck with me, and now i'm only a couple semesters away from graduating with my undergrad in Math. I loved growing up with this channel
You’re welcome. What a great message.
@@numberphile I'll add my own story. I started watching in middle school too--I specifically remember recreating the argument that 100% of all integers contain the digit 3 for my mom. This fall I'll start a PhD in mathematics!
Dr Grime absolutely my favourite regular on this channel.
He knows how to explain things so well that a kid can understand it, and he knows how to scale explanations from the basics up until the higher level stuff.
Also, his awkward and enthusiastic demeanour reassures me that he is a real mathematician and a nerd.
I agree. His face on a preview makes me click much faster.
I mean, but then you have people like Tom Crawford who is not awkward at all, and looks nothing like a stereotypical nerd... yet absolutely is 😂
Yeah old Grimey is pretty cool 😅
I did a project in college specifically about looking at books of knots, every knot can be done with 3 pages (and apart from the unknot they all need 3 pages) so they're a little boring with that respect, but the proof of this is rather simple, and then from there you can give each arc it's own page and that's the arc representation of a knot, and then there's a pretty simple proof of Alexander's theorem using that representation. Just fun stuff.
I thought that Alexander's theorem of knots was chopping them with a sword?
I thought that books of knots were manuals for Boy Scouts.
@@adamcetinkent hah, I see what you did there
I’m Canadian, but my parents are from northern England. One particular room in my childhood home had two cupboards, one that contained boots, winter jackets, and mittens. That was the “boot cupboard”. The other cupboard in this room was where we kept our books. That was the “book cupboard”. It was a source of constant confusion.
Great story, it sounds like a perfect firtst page for a book for children.
For children wearing boots and reading books.
They're called shelves (made of boards) and enclosed they're called cabinets. A "cupboard" is a series of shelves that hold cups. Also, maybe it was confusing to you all because English people bastardize pronunciation between boots and books? They already bastardize the meaning of cupboards.
@@CharFred-vr1ti Imagine the words 'boots' and 'books' pronounced in a Northern English accent - like Manc or Lanc in general. All will then be clear.
Brady's graphics are the genius of numberphile videos! His interviews are amazing and the knowledge he shares needs to go further. singingbanana needs more sunshine.
I love this! Reminds me of the early Numberphile videos. I'm far from a mathematician, but in this instance, simplicity with everyday understanding makes for a great video that really appeals to a dummie like me. And, James is the best at this stuff. What a great teacher. Thanks for this video, Brady!
Fun fact: a tree can always be done in only one page. Pick a root, and place it on the leftmost point. Afterwards, place all the points of the graph in a depth-first listing, and connect all points. Every subtree will be all together, recursively listed without intersections in the single page.
That was the most beautiful graph I’ve ever seen. What a reveal!
Great graphics Mr Grime! This channel has only gotten better.
In this video I learned something about graph theory, and unlearned how I said the word book. Balanced, as all things should be.
yo i've actually drawn a similar number line by hand before! glad to know i wasn't the only one that had the idea of doing that lol
Instantly thinking about the infamous problem where the points define electricity, water, and gas, and each of the homes need to be connected to each one, without crossing (on a regular sheet of paper).
Yeah, K5 (the complete pentagram - the complete graph on 5 vertices) and K3,3 (the utilities graph, or the complete bipartite graph on two sets of three vertices) are famously the two fundamental non-planar graphs - every non-planar graph has one or both of those two as a "minor" - a minor of a graph is any graph that can be formed by taking a subgraph (some of the vertices and edges, including all the ends of the edges) and then contracting edges (so the two vertices at the ends of an edge merge, with any vertex connected by an edge to either of the old vertices having an edge to the new vertex).
I am a simple girl. I see James, I click.
Hi Dr. Grime! Hi Brady!
This was really nicely explained. What an interesting problem! It's great to see someone found a solution once and for all.
Freeze the video at 7:46 and check out those eye popping numbers on the screen on the wall! 4000+ videos and 1.3 billion views. Way to go Brady and team!
haven't watched this channel in many years and i am relieved to see that james grimes is still very handsome
Canteieve ive been watching this guy for 10 years
I love to see the planar graph expressed on a sphere
@7:55 If you consider the points B & A to be the north and south poles, then the points t0-t7 will be on the equator. The tighter "blocks" of points can be stretched out along the north-south direction independently. Not sure if that helps you form a mental image or not, different brains visualize in different ways.
why does no planar graph need 5 pages? has anything to do with the 4 color map theorem?
Idea for a possible way the two could be related: (actually this doesn’t work. Posting anyway.)
Take a planar graph , embedded in the plane in some way. Thicken the edges of the graph, making these edges the nodes of a new graph, and have them be connected if they are neighboring (as in, if they share a vertex, *and* are adjacent in the order they make around the vertex)
The result should still be planar.
4-color these new vertices (which, recall, are the original edges).
Assign ones with different colors to different pages.
... this construction doesn’t work because it doesn’t have the pages/leaves meet on one line.
So yeah nvm.
That's the sort of thing mathematicians must be asking .....
What if you started with a 3-colour map, and did some sort of transformation to end up with a graph that needed a 3-page book?
So the image at 7:47 is one of the things we would send to alien civilizations to prove our intelligence and worthiness to avoid getting destroyed.
This reminds me a lot of PCB designing... how many layers of copper do you need for manifacturing the connections you need... don't know if it is exactly the same problem but they definetly seem similar...
With PCBs, you have some additional physical constraints; a via (through connection) connecting any two layers requires a hole that must go through all the layers, and this adds a space requirement which in turn imposes a restriction on the total number of layer changes available.
It's a good day when James is on numberphile 😁
Am I seeing right, the Goldner-Hararay Graph (6:22) looks embedded multiple times in the new 4-page graph (8:08) ?
It’s a version on a theme, it probably has that issue in each of those sub components that you can’t add loops by using the same kind of prevention techniques the GH graph uses.
Looking at the original paper, they talk about the sub structures as “gadgets” which cannot be embedded in three pages under specific circumstances. if you wanna look at the paper it’s in the description of the video.
Thanks for the new video, math will remain in our hearts ❤
7:58 Someone NEEDS to make a tee shirt with this on it!
Can we get that final heart graph on some merch?
James at it again
That graph was sooooooo nice!!! ❤
I want prints of these. They are so beautiful.
Very interesting!
I'm sure I recently saw a video about inter-referencing in the bible and the graph looked exactly like this...!
0:59 "...Southern [UK] accent..." On the radio, the BBC Book Club used to sound like 'BBC Bik Kleb', which I found entertaining.
Is this a minimal planar graph requiring 4 pages, w.r.t. some sensible measure (average degree seems fitting), or just _a_ counterexample?
We got numbers at 10^404 and 10^2135 that are just like 5040, but more firm (if you are stunned at the amount). Infinity is sickening and others have no regard for actual variations in just one number with 404 digits in base 10. Fun. Sine wave is connector of circle and triangle in 2D. I am ahead of the quantum computer!
Does anyone know where a proof can be found for the complete graph/page theorem? I.e. that any complete graph needs ceiling(n/2) pages?
I would go so far as to say it isn't actually true: the complete graph with 3 nodes surely fits on one page?
@@TheRocreex I looked at the wiki article for book embeddings and it clarified that the result holds for n >= 4
Great video!! I have an idea for a numberphile espisode that super cool. How the design of a tachymeter dial works regardless of unit, all from a mathematical point of view.
Thank you ❤
It looks like a map of the Tralfamadorian Underground, where you travel from station to station through hyper-space.
I wonder if something like this is also being researched but with 3-dimensional graphs and 4-dimensional books.
I would like to ask this question: Why is 3 not connected to 1? Should there not be a phantom loop connecting 3 and 1 on a second page? Or is that to distinguish crossed paths?
The idea is that if you can create a "phantom loop" that passes through every vertex, you can use the method of generating a book graph for a planar graph that has a loop and just remove the extra edges afterwards. So all you need to do is add enough edges (without crossing any existing edges) to make a continuous path that goes through every vertex exactly once and comes back to the start, use that method, and remove the edges you added.
The tricky part then comes up with planar graphs where it's impossible to do that.
@@Idran Thanks
I may be wrong, but for symmetry reasons I presume there is one line missing in the graph at 8:00, i.e. from point t2 to about 10 o'clock
Perhaps, but maybe it wasn't even needed.
Curiously, the graph in the linked article (see description) shows the same kind of graph with one less cluster (t0-t6 rather than t0-t7), but that graph is also missing 1 line from a symmetry perspective. So it actually may be required.
Let's say you represent a graph as a table with 0 for no connection and 1 for a connection between vertices, then read out the entire table as one single number. Do the resulting numbers have an interesting relationship to structure, type and properties of the graphs they were derived from?
The table you are talking about is called the adjacency matrix. I don't know what you mean by reading out the table as a single value. Summing them would simply give you twice the number of edges. However, how the eigen values and eigen vectors relate to the graph is a whole field called spectral graph theory
@@hampusnyberg6583 Yes. Quote Wikipedia: "For a simple graph with vertex set U = {u1, …, un}, the adjacency matrix is a square n × n matrix A such that its element Aij is one when there is an edge from vertex ui to vertex uj, and zero when there is no edge."
With "read out the entire table as one single number" I meat forming a binary number by concatenating zeros and ones contained in A in a certain order. For example: r = A11 || A12 || A13 || .... || Ann
Then the question, if r is "interesting" in a very broad sense. Example: if r is prime, does this property relate to properties of the corresponding graph?
If your doing an Extra videos on this, maybe you could give a couple of examples where books are useful.
there's no guarantee there are any applications yet
in pure mathematics, the research comes first, and application comes later (if ever)
number theory was for ages thought to be useful only as an intellectual fascination (and was even jokingly lauded by at least one pure mathematician for that) until people started studying methods of cryptography and realized it was perfect for that
Loved it by heart❤
this untangling...is it related to knot theory?
I’m assuming the Goldner-Harary graph was partially named after Frank Harary, who I had the pleasure of meeting in his latter days.
The special graphs you mentioned near the end each had nearly 3 times as many adages as vertices, so must have an average vertex degree of nearly 6.
Was a bit confused at the start around what is allowed on a book page. I’m assuming that we cannot have edges both inside and outside a Hamiltonian cycle, hence why we need 3 pages for a K5 graph.
On a more flippant note, I don’t think the Spirograph was invented or so called with graph theoretical graphs in mind!
Each page is a planar graph (i.e., no edges crossing) with all the edges in the half-plane whose boundary is the row of vertices.
You guys are still at it after all these years. Cheers 🥹🍻
I adore this.
Once again the proof involved a SAT solver, which just keeps happening again and again with these breakthroughs (the recent 1-tile thing too), and yet SAT solvers still seem to be underused and not widely known about
Does anybody know why is there a ladder in a wall? It is there since forever, is it someone of decoration?
Dude's always with the deep stuff
Jim Grime
I imagine how much info. Fast Fouriers would dig up
How can the one publish the prime number Formula at a science magazine ?
7:53 I miss one line from B to the point between t0 and t1. Is it really missing or is the graph really like this?
I think it’s a mistake in the video. The original paper has that line shown in the drawing.
That graph needs to be on a t-shirt.
Why is it that no graph needs a 5 page book? how do u prove that?
No edge-maximal planar graph. Full graphs can require any number n of pages, and you only need 2n vertices - this is said in the video.
That pronunciation of "book" that Grime does reminds me of the character of Paul's grandfather in A Hard Day's Night. 😝
(Also, the way Paul McCartney sings the "little white book" line in "Lovely Rita")
The first time I saw this type of graph was when someone showed me all the cross-references between the 66 books of the Bible. It was amazing how full that was. Now I can’t help but wonder, how many pages would it take to untangle that one? 📖
First task is to untangle all the inconsistencies of the bible.
Why can there be no one with 5 pages?
Good video 👍
I must be missing something, because I can't confirm rhe complete graph formula.
Let's start with just one node. According to the formula, you'd need 1 page. But the node sits on the spine, by definition, and there are no edges which would need any pages. So I'd say it' neds zero pages. Similarly for n=2, there the complete path consists of two nodes connected by an edge. The nodes sit on the spine, by definition, and the edge also can be drawn along the spine, so again, zero pages.
But then, maybe books are defined to always have at least one page. Well, then let's look at n=3, which according to the formula should need 2 pages. But the complete graph in this case is just a cycle, exactly like the one in the first one-page example, just with one node less. So for n=3 you should actually only need 1 page.
For 4 and 5 nodes, the formula does give the correct number of pages, and beyond I didn't check. But for n up to 3, I don't think the formula is right.
These remind me of Simon Tatham's Untangle puzzle game you can play online.
Could this be related to the four color theorem?
I'd have expected the 4th page to contain just one edge, like the straw that broke the camel's back.
What about graphing the points in the surface of a sphere? Would it change things?
No. Imagine a sphere made of rubber. You can poke a single hole and stretch that to become the entire perimeter of a flat sheet of paper (think of stretching the edge of an uninflated balloon until it is a flat rubber sheet.) If you were on a torus, things would be different though.
Edit: I forgot to mention the important part, that the hole you poke in the surface can always be placed between lines/points. So no lines will cross the resulting edge of the flattened map.
Is it the smallest 4-page planar graph? Or can there exist ones with fewer vertices?
You didn't know my personal life. I was just trying to handle things and try to help my mom. I never told anyone. I been stressing losing my mom before I knew it. I haven't done anything
Or asked anyone for help. I am noting sueing. This was my stress relieving from doing all the responsibility in my house. I never asked anyone's help
When stretching the two crossing lines outside the pentagram, can that be considered a form of topological stretching?
Depends. It's called an ambient isotopy in which, if you consider the graph to be embedded in into 3D space (or other sufficient spaces), then you can continually deform not just the two edges in the first picture but the space surrounding them so that the image of the transformation is the second picture. However, if you are considering planar isotopy then you must work with a projection of your graph on the plane and you can only stretch the plane without pulling edges out of it. In this isotopy, pulling the two edges in the first picture through the other edges in the way is not legal since you're tearing the plane around them when you do that. In short, it's only a topology preserving operation, or topological stretching as you put it, if imagine the graph as being embedded in 3D space or something similar.
I worked on a paper that was concerned with such things. Here's a fun theorem that didn't make it into the paper: Consider a complete graph with 5 vertices in the shape of a pentagon, such as the graph we were discussing earlier. Furthermore, let us only consider the edges to be straight lines (this is called a linear embedding) and for it to be occupying the plane. Suppose you are told this graph was actually embedded in 3D space in some way that you don't know, leaving you to make guesses about how it looks in 3D based on this "shadow" of the graph. At each crossing you must mark one of the edges as being "on the top" from the perspective of the shadow (a graph with such markings is called a crossing diagram of said graph). Each choice makes a different prediction for what the embedding might look like, with some choices being impossible. Amazingly, there's exactly one crossing diagram up to planar isotopy! That is, just by stretching the plane, you can always make your prediction look like the "correct" one, or into any other legal crossing diagram of any 5 vertex graph with pentagonal shape (pulling a vertex into the quadrilateral formed by the other four vertices is not a planar isotopy, so that distinction must be made).
Could pages be used to give a scale to the non-planarness on a graph? Im trying to cast my mind back to my Uni days and think how this could be used in knot theory 🤔
Certainly one of the stats of a graph is its book number. But we need to understand that a graph's book number can be as large as 4 (as we now know) and still be planar.
As for a measure of how non-planar a non-planar graph is, there are numerous variants of crossing-number. Marcus Schaefer wrote a paper which was a survey of some of them --- he listed dozens!
this seems like an interesting way to conceptualize manipulating dimensions.
2:29 “I created a 2 page book”.
Don’t get why that requires two “pages” ?
to prevent crossings
I hope I am phrasing this right. How many different numbers yield a maximum of 4 pages for the book embedding of graphs? is it just one so far? Also, would doubling the number yield 4 pages as well?
Take the graph from the video and add as many independent vertices as you want. That graph will also require 4 pages.
Why can't the Goldner-Harary planar graph go from page 2 to page 1 through the gap between 6 & 8? Or is that what the third page is?
A line can only be on one page.
why arent there any books with 5 pages ? surely more complex graphs will require more pages 🤔?
These are specifically for planar graphs. Or graphs that can be drawn on a plane without any crossings (without the line restriction like a page)
I'm not a super math guy but, is this similar to the number of holes in a t-shirt or that bottle?
we love 301
Homework until next week - is it the smallest graph that needs four pages to create a book.
So any planar graph can be represented as a book of at most 4 pages? Is that the theorem effectively?
yup
I'm sure there is an application for this somewhere.. But where
Why is the spine not considered a page? It also contains information. Doesn't that mean it's actually 5 dimensions needed to embed the info?
Just curious, are there any known practical implications for the book size of a graph?
I'm very curious about that too.
So far I can only think up a use case that involves an electric circuit being implemented on several prototyping boards that are hinged on one side just like a book for maintenance access, but that would only make sense if no jumping wires are allowed, which doesn't seem like a realistic constraint.
The concept of a book graph seems very obvious, but abstracting the rules that define a book graph and then matching them to an equivalent problem is hard. In principle, the binding of the book being straight and the pages being planar seems irrelevant to the underlying logic. It's a two-dimensional problem which kind of leaks into the third dimension with every page connecting to all other pages through a single line representing the back of the book.
The crisscrosses could be avoided /eliminated in higher dimensions.
You can avoid the crossings even on a 2D surface that's more interesting than just a plane - for instance, you can get up to K7 on a torus
A network is a graph with named nodes. It would have been nice to defined this in the 1st 20 seconds instead of calling a graph a network. Not all graphs have named nodes so not all graphs are networks.
Здравствуйте! Очень давно подписан на ваш канал, но смотрю ваши ролики с других каналов, переводящих их на русский. Английский я конечно знаю, но понимать терминологию очень сложно. У меня тут вопрос назрел, надеюсь вы его прочитаете: полый шар гомеоморфен шару или тору?
I notice the last 3 page book could be done in 2 pages if the green line can cross pages.
I think you refer to the graph @6:35 in the video. What you are really suggesting is adding a new point to the graph on the line between vertex 4 and vertex 10 (let's call the new vertex 12.) Placing vertex 12 between vertices 6 and 8, you can then draw a line from 4 to 12 bowing down under 6, and one from 12 to 10 bowing up above 8. This is a different graph with a different number of vertices, and illustrates why the problem is so difficult. Adding vertices can actually lower the number of pages required.
(Note: each line in a bok can only arc upwards or downwards, not zig-zag through the chart.)
It's beautiful
The brown paper has almost completely disappeared from these videos.
It took me a while to understand that the goal was to have the _most_ number of pages for a given graph, not the fewest.
No, for any one graph, it's to have the fewest pages. The question is: what's the smallest number of pages which is enough for every planar graph.
@@rosiefay7283 that's the question at the end but in the middle of the video, he talks about reordering the points so you get _more_ pages. But I agree, the video was much more confused than Brad's videos usually are.
@@unvergebeneid The bit in the middle is just to highlight that you can pick a bad order and increase the apparent book number that way, which means that finding the actual book number of a graph requires more than just finding the best arrangement of arcs for some particular ordering.
@@unvergebeneid He reorders the points to show that you get a different result. But the entire time, he was aiming to minimize the number of pages. If he was trying to maximize it, then you would just have a single edge for every page.
If you're an Australian in the UK it's traditional to mock their accents
Unfortunate terminology conflict with the paper book analogy here... books have paper leafs that have text printed on their both sides, the two sides are numbered and are called pages.
Here in this graph case a "page" is that what is called a "leaf" in the paper book.
Well that's a printing decision, you could print this with one 'page' on each page, but it'd be rather unreadable with transparency involved and with opaque leafs it'd be impossible to see the whole graph at once. Still, there are four 'layers of information' so to speak, which corresponds better to a page than to a leaf.
The Coca-Cola bottle contraption next to the religious corner 🌞👍🏻
0:52 I don't know what I find more surprising --- that you wanted to say it again in a "Southern accent", or that when you tried, it was more Scouse than anything else.
I would read a book about this.
wow.
my new wallpaper
Is James from Lancashire?
2:50 For this to be possible you need to sacrifice a goat.
Book embedding of graphs? More like “Bro, Numberphile is where it’s at!” 👍
I think the natural question is "is there an infinite amount of them?"
You can just add a chain of length n to the graph and it will keep the property, so yes, there is an infinite amount of them.
4432 videos, hey? Impressive!