Discovery about Book Embedding of Graphs - Numberphile
Вставка
- Опубліковано 29 кві 2023
- Featuring James Grime. Check opportunities with Jane Street at www.janestreet.com/join-jane-... (episode sponsor)
More links & stuff in full description below ↓↓↓
James Grime: www.singingbanana.com
His UA-cam channel: / singingbanana
More James on Numberphile: bit.ly/grimevideos
Four Pages Are Indeed Necessary for Planar Graphs (paper): arxiv.org/abs/2004.07630
Play with the four page graph: be.cs.arizona.edu/map/1442/
Read more on book embedding: en.wikipedia.org/wiki/Book_em...
Numberphile is supported by the Simons Laufer Mathematical Sciences Institute (formerly MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from The Akamai Foundation - dedicated to encouraging the next generation of technology innovators and equitable access to STEM education - www.akamai.com/company/corpor...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Animation and Editing by Pete McPartlan
Special error correction credits to Numberphile Society members Michael Colognori & Debbie Chakour
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9 - Наука та технологія
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
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
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 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!
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 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.
That was the most beautiful graph I’ve ever seen. What a reveal!
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!
Great graphics Mr Grime! This channel has only gotten better.
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.
Thanks for the new video, math will remain in our hearts ❤
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.
I am a simple girl. I see James, I click.
That graph was sooooooo nice!!! ❤
Definitely food for thought.
Assuming graphs with a cycle through all nodes… the line and pages idea is very interesting… I want to put a peripheral cycle in each page…
Food for thought
It's a good day when James is on numberphile 😁
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).
Loved it by heart❤
Very interesting!
James at it again
In this video I learned something about graph theory, and unlearned how I said the word book. Balanced, as all things should be.
I adore this.
Canteieve ive been watching this guy for 10 years
Thank you ❤
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
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.
haven't watched this channel in many years and i am relieved to see that james grimes is still very handsome
7:58 Someone NEEDS to make a tee shirt with this on it!
I want prints of these. They are so beautiful.
Good video 👍
It's beautiful
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.
I'm sure I recently saw a video about inter-referencing in the bible and the graph looked exactly like this...!
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!
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?
Can we get that final heart graph on some merch?
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.
Is this a minimal planar graph requiring 4 pages, w.r.t. some sensible measure (average degree seems fitting), or just _a_ counterexample?
this untangling...is it related to knot theory?
Is it the smallest 4-page planar graph? Or can there exist ones with fewer vertices?
It looks like a map of the Tralfamadorian Underground, where you travel from station to station through hyper-space.
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
You guys are still at it after all these years. Cheers 🥹🍻
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.
Dude's always with the deep stuff
Jim Grime
I imagine how much info. Fast Fouriers would dig up
Could this be related to the four color theorem?
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.
I would read a book about this.
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.
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
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
Здравствуйте! Очень давно подписан на ваш канал, но смотрю ваши ролики с других каналов, переводящих их на русский. Английский я конечно знаю, но понимать терминологию очень сложно. У меня тут вопрос назрел, надеюсь вы его прочитаете: полый шар гомеоморфен шару или тору?
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.
These remind me of Simon Tatham's Untangle puzzle game you can play online.
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).
0:59 "...Southern [UK] accent..." On the radio, the BBC Book Club used to sound like 'BBC Bik Kleb', which I found entertaining.
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!
Why can there be no one with 5 pages?
I wonder if something like this is also being researched but with 3-dimensional graphs and 4-dimensional books.
That graph needs to be on a t-shirt.
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")
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.
I'm sure there is an application for this somewhere.. But where
Is James from Lancashire?
this seems like an interesting way to conceptualize manipulating dimensions.
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.
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!
wow.
my new wallpaper
I'm not a super math guy but, is this similar to the number of holes in a t-shirt or that bottle?
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.
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.
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?
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.
How can the one publish the prime number Formula at a science magazine ?
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
thank you
i have a new idea about my new tattoo 😂
That tattoo artist is going to need a really steady hand.
So any planar graph can be represented as a book of at most 4 pages? Is that the theorem effectively?
yup
Does anybody know why is there a ladder in a wall? It is there since forever, is it someone of decoration?
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.
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.
I'd have expected the 4th page to contain just one edge, like the straw that broke the camel's back.
4432 videos, hey? Impressive!
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
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.)
Homework until next week - is it the smallest graph that needs four pages to create a book.
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?
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
The Coca-Cola bottle contraption next to the religious corner 🌞👍🏻
2:50 For this to be possible you need to sacrifice a goat.
Surely the four page theorem is related to the four color theorem, but there's no mention of that in this video?
we love 301
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)
So does that mean with V-E+F = 2 for it's euler characteristic it would have 2- 275 +890 = 617 Faces? Or is this not topologically a 2-characteristic graph?
It's a planar graph, so its euler characteristic should indeed be 2
@@chriss1331 Thanks!
If you're an Australian in the UK it's traditional to mock their accents
The brown paper has almost completely disappeared from these videos.
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.
I miss singing banana
Book embedding of graphs? More like “Bro, Numberphile is where it’s at!” 👍
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.