I'm reading a CS paper right now and I'm also feeling this so bad... I understand the paper, but somewhere in the middle it says "We use the following notation to simplify the presentation" and what follows is this dense gibberish that slowed me down for hours. Eventually I understood that the notation indeed represents the thing I already understood, but in a complicated way.
@@GijsvanDam Which raises the question: what notation would you have preferred, which is even simpler? You compare a thing and a notation, but the thing got a head start because you already understood it before you read the notation.
@@rosiefay7283 Funny you'd ask, because I was thinking about this as well. In this particular case (since it was CS) just code (or pseudocode) would have been much clearer. And sometimes a diagram can explain a concept way simpler than any notation you can come up with.
@@GijsvanDam What the author unconsciously intended was to demonstrate the power of their own understanding and not actually enhance the understanding of the reader. The author has to go into more detail, and explain his "simplified" notation, than actually explaining the concept in a manner where the student can apply the concept properly, and understand where the concept can be applied.
Great video! The paper proving the result is a lengthy one but a fantastic read. It builds upon its own ideas and constructions at a good pace and explains the motivations very intuitively. Graph theory really is one of those special fields of mathematics that builds upon elementary ideas in a very accessible way, and this makes so many of the proofs so satisfying!
I love it when we can tread ground across how discrete math problems may be solved in a semi-numerical fashion, which leads back through logical symbols in theorems, to join up again in purely numerical form (or at least straight back into set theory, and the form of sets and super- and sub- sets, which arguable all cardinal and ordinal numbers actually are.)
For the definition of a perfect graph, my brain wanted to call it the rate-determining reaction, analogous to chemistry. A chemical reaction can only be as fast as its slowest step, like an assembly line. If the biggest clique size wasn’t the “slowest,” then there’s something else slowing down the coloring number. And a perfect graph is the fastest among those with the same omega, i.e., those that also have that same step as part of their reaction. A clique is just another word for a complete subgraph, right? I’m not missing something, right? For my thesis, I had a graph where the vertices of the graph represented almost all of the (n+1)-cliques in a complete graph of an n-cube (so, almost 2^n choose n+1 vertices). [They had to be n-simplices (like a triangle or tetrahedron or pentachoron) of the right size, which would be the smallest size. So if I labeled the vertices of the cube with vectors of zeros and ones, then pick one of the n+1 vectors and subtract it from the others (like making that one the origin), then line up those new n vectors, then you want the determinant to be exactly one.] In my graph of almost all (2^n choose n+1) vertices, there would be an edge if the corresponding n-simplices did not intersect (touching at a face is fine) and no edge if they did intersect. Then I needed to find all the n!-cliques in that giant graph. Keeping in mind that each one could have up to 2^n * n! copies because of the symmetry of the cube. Basically, since there were so many redundancies that I was not smart enough to simplify down for the computer, it just crashed every time I did anything more than n=3.
From my understanding, a clique is specifically a subdivision of a graph G where all vertices in the clique are pairwise adjacent, whereas a subgraph is just a subset of verticies from graph G.
rate determining reaction is an oddly specific analogy. This concept appears everywhere. It is often called the bottleneck, the weakest link, etc. Notably, in chemistry, you also see this in chemical equations with the idea of "limiting reactant".
Excellent observation. I think it is also interesting that cell phones and cell towers exist in 3d space, but the problem you just described can be represented in 2d space. if a cell phone tower knew just one more bit of information about a cell phone, it's height, or angle relative to the tower, or distance. 2 cellphones could use the same frequency as long as they where not, say, at the same angle relative to true north from the tower.
Fantastic lectures. Thanks a lot. What books do you recommend for learning: graph theory and its application in science and engineering. This will help a lot of people. Thank you in advance
Perfect graphs are interesting because if we can find them easily then, you have a kind of heuristic to compute the chromatic number xhi(G) ; browse the graph finding maximal cliques...or try to compute w(G) instead of xhi(G). If you want to do the same for a random graph by a computer sortware..you will met the NP obstacle ...not enough computation time, when the size of graph (number of vertices) increase. One application of graph coloring is to make network (electronic, social,..) with parallel tasks and some independance between them.
As given in this relatively new (pre)paper on arxiv (arxiv.org/pdf/1903.00208.pdf) the theorem was proven by others in 2005...and Maria and others improved the algorithm and computation complexity a few years ago.
Vertex Transitive graphs seem perfect, but they're not in this colouring sense. They include archamedian solids, infinite regular trees, hypercubes, complete bipartite, cycles, splays, infinite grids, a grid on torus etc… They're graphs where the nodes are indistinguishable. :) For example, think of a corner of a cube, now try to describe that corner to another person. :) They are symmetric everywhere, like a sphere.
Hang on, doesn't every complement of an odd cyclic graph already contain a cyclic graph, making that condition redundant? C(7)^C, for instance, contains C(7) going 1-3-5-7-2-4-6. Is there really an odd cyclic-complement graph where that is not the case?
In fact, what's wrong with this proof? Theorem: Every complement of a cyclic graph of odd order k >= 7 contains the cyclic graph of order 3, and is therefore not perfect. Proof: Number the vertices along the cycle 1, 2, ..., k. 1 is connected to 3 (since 1 and 3 are nonconsecutive), 3 is connected to 5 (since 3 and 5 are nonconsecutive), 5 is connected to 1 (not-adjacent since k >= 7). So I guess my question is why bother with the "complement of a cyclic graph" part of the argument? A graph is perfect iff it contains an odd cycle. Done.
It is not just about containing a cycle, but also having no more edges. For example you want 7 vertices with edges 1-2-3-4-5-6-7-1, but no more edges (no edges 1-3, etc.) Similarly for "containing" a complement of a cycle you want exactly the edges you would expect (no more no less).
You could define something that was to polyhedra what graphs are to polygons (i.e., a graph, plus each edge can be part of some faces, maybe with some rules). I haven't heard of this being studied or having interesting results, outside of results about polyhedra.
Numberphile! I love the strong representation you give to women in mathematics. I notice on almost all your videos featuring female mathematicians, a multitude of the commenters feel a need to comment on their physical appearances, which I hope you understand is condescending and objectifying for women in a field where they are already marginalized. However, perhaps your viewers don't all recognize the problems with this behavior. Maybe you could make a video addressing the inequity women face in the STEM field and address the appropriateness of these comments. Thanks!
Agreed on all points. It's great to see both male and female mathematicians get a chance to shine on these channels, but very disappointing to see how much more often people comment on the women's appearances than the men's.
@Puppet the only cringe here is all of the constant stream of men who are so lonely they feel the need to comment on these mathematicians' appearances, even going far enough to claim they have a "crush" as if they would EVER even have a chance with one of these women.. THAT is cringe dude... if you don't see it then you might just be cringey yourself 😌
@Puppet can you explain how I am misinformed? Women are marginalized in STEM- that is a research proven fact, and there are studies ranging all the way from preschool to K-12 to college to the professional field that show the nature of the inequity women face in STEM. I have a bachelor's degree in Mathematics and I'm working on a Master's degree in Math Education that requires that I specifically study research in this area. I am very informed. What data do you use to inform your opinions?
Moreover, beyond my education in math research, it doesn't take any sort of science to know that these kinds of comments are awkward and belittling- it just takes a shard of empathy, and a glance over at any numberphile video featuring a male mathematician, to see how this is not fair
@@invaderpopz Women dominate *all levels* of education. Yes, that includes graduate studies. The fact that in math, engineering, physics and perhaps a few other fields like philosophy men dominate doesn't mean that women are marginalized. Men and women have different interests, and that's okay. That said, it is weird that so many people comment on their looks, and I agree that it is "cringe". Then again, the viewership is almost certainly predominantly male, and males generally are attracted to females.
Is anyone working on what happens when a planer graph is translated to a volume? I am interested in what happens to graph theory when you use a higher dimension to solve problems in a lower dimension, or vice versa. For example drawing a planar graph in 3 dimensions, ddges may no longer intersect in this higher dimension, seems like cheating, but might have very useful applications in the real world. I understand that each higher spatial dimension introduces a new connection method, and new constraints, but is this true and provable? Do dimensions introduce new connection methods, and connection constrains? 3D introduces a Plane, 4D introduces a, what, Volume? My understanding is that with Planar graphs we are trying to avoid intersecting edges, re-drawing a planar graph in 3 dimensions can allow edges to not intersect, but the 3rd dimension introduces the concepts where the closed area created by a subset of vertices and edges create a plane, in 2D planes have no way of intersecting, but in 3D, a graph can be drawn where edges do not intersect, but the planes created by edges and vertices do intersect. In 3D we want to avoid intersecting planes. Is this a valuable concept? Do you know anyone working on this type of thing, meaning proving or working on operations to create theorems equivalent to planar theory in higher dimensions? Or are there theorems that describe how map problems can be solved by changing dimensionality? Basically what I am getting at, is there a theorem that proves that any graph with intersecting edges in 2D can be drawn in 3D and not have intersecting edges? Can it be proven that any graph with intersecting planes drawn in 3D can be drawn in 4D and not have intersecting planes? Can it be proven that any graph with intersecting edges in 2D can be drawn in 4D and not have intersecting edges? I _assume_ this would be valuable to scientists working on 3D graphics, and may have already been done in that field? If you made it this far reading this comment, I thank you Maria Chudnovsky for your efforts and work, and I thank everybody at Numberphile for their superb productions.
You asked a lot of different questions, and I can't answer all, but let me try to add my two cents. A graph can be defined as the list of it's edges. An edge is just a pair (ordered or not depending on whether the graph is directed of not) of vertices. Now, you can think of a 3D graph as a set of vertices, but an "edge" (or plane, though those are infinite most of the time) will consist of 3 vertices. This idea have been generalized by the concept of hypergraphs. Regarding your "is there a theorem that proves that any graph with intersecting edges in 2D can be drawn in 3D and not have intersecting edges" question. In 2D, the edges partition the plane, but in 3D the same edges don'T partition the whole space. Therefore you will always be able to connect vertices in 3D without any two edge intersecting.
Part 1 is at th-cam.com/video/xBkTIp6ajAg/w-d-xo.html
"In maths, we color with numbers"
I'll never look at a paint-by-number the same ever again.
HAPOY BIRTHDAY NEBULA
"A complicated way to say something simple we just observed" I am writing a math paper now, and I feel this so bad...
I'm reading a CS paper right now and I'm also feeling this so bad... I understand the paper, but somewhere in the middle it says "We use the following notation to simplify the presentation" and what follows is this dense gibberish that slowed me down for hours. Eventually I understood that the notation indeed represents the thing I already understood, but in a complicated way.
@@GijsvanDam Which raises the question: what notation would you have preferred, which is even simpler? You compare a thing and a notation, but the thing got a head start because you already understood it before you read the notation.
@@rosiefay7283 Funny you'd ask, because I was thinking about this as well. In this particular case (since it was CS) just code (or pseudocode) would have been much clearer. And sometimes a diagram can explain a concept way simpler than any notation you can come up with.
@@GijsvanDam What the author unconsciously intended was to demonstrate the power of their own understanding and not actually enhance the understanding of the reader. The author has to go into more detail, and explain his "simplified" notation, than actually explaining the concept in a manner where the student can apply the concept properly, and understand where the concept can be applied.
Java programmers are weeping in a corner
Great video! The paper proving the result is a lengthy one but a fantastic read. It builds upon its own ideas and constructions at a good pace and explains the motivations very intuitively.
Graph theory really is one of those special fields of mathematics that builds upon elementary ideas in a very accessible way, and this makes so many of the proofs so satisfying!
Very nicely explained! Thank you, Maria!
(8:29) Aaaah damn!
A lost opportunity to say "...the moment when it finally CLIQUE'd... " 😊
I love it when we can tread ground across how discrete math problems may be solved in a semi-numerical fashion, which leads back through logical symbols in theorems, to join up again in purely numerical form (or at least straight back into set theory, and the form of sets and super- and sub- sets, which arguable all cardinal and ordinal numbers actually are.)
I liked both of these videos but i would have loved to see some examples.. of a perfect graph, of a graph that reduced to k5 or k3,3 etc.
That's homework
I really loved this. Thank you!
Nice explanation! It helps build a bit of intuition.
im here to start an official fanclub
For the definition of a perfect graph, my brain wanted to call it the rate-determining reaction, analogous to chemistry. A chemical reaction can only be as fast as its slowest step, like an assembly line.
If the biggest clique size wasn’t the “slowest,” then there’s something else slowing down the coloring number. And a perfect graph is the fastest among those with the same omega, i.e., those that also have that same step as part of their reaction.
A clique is just another word for a complete subgraph, right? I’m not missing something, right?
For my thesis, I had a graph where the vertices of the graph represented almost all of the (n+1)-cliques in a complete graph of an n-cube (so, almost 2^n choose n+1 vertices).
[They had to be n-simplices (like a triangle or tetrahedron or pentachoron) of the right size, which would be the smallest size. So if I labeled the vertices of the cube with vectors of zeros and ones, then pick one of the n+1 vectors and subtract it from the others (like making that one the origin), then line up those new n vectors, then you want the determinant to be exactly one.]
In my graph of almost all (2^n choose n+1) vertices, there would be an edge if the corresponding n-simplices did not intersect (touching at a face is fine) and no edge if they did intersect. Then I needed to find all the n!-cliques in that giant graph. Keeping in mind that each one could have up to 2^n * n! copies because of the symmetry of the cube.
Basically, since there were so many redundancies that I was not smart enough to simplify down for the computer, it just crashed every time I did anything more than n=3.
From my understanding, a clique is specifically a subdivision of a graph G where all vertices in the clique are pairwise adjacent, whereas a subgraph is just a subset of verticies from graph G.
Jo Wick , I said *complete* subgraph. I think that restricts it to have the same definition as a clique.
rate determining reaction is an oddly specific analogy. This concept appears everywhere. It is often called the bottleneck, the weakest link, etc. Notably, in chemistry, you also see this in chemical equations with the idea of "limiting reactant".
8:46 There are two "page.4" 🧐
Really good 🧐 !
Also two page 9's. 🧐🧐
Omg she worked on the proof?!
This is like in cell phones, where two neighboring cells can't use the same radio frequency, because it would lead to interference.
Excellent observation. I think it is also interesting that cell phones and cell towers exist in 3d space, but the problem you just described can be represented in 2d space. if a cell phone tower knew just one more bit of information about a cell phone, it's height, or angle relative to the tower, or distance. 2 cellphones could use the same frequency as long as they where not, say, at the same angle relative to true north from the tower.
Mam, can you please post the continuation of this... Perfect graph. Theorems and lemmas.
is she the first to put the brown paper on the wall?
Dear, can you please make a video on perfect graph theorem statements are equivalent
Great video. I love graph theory!
those two pages at 8:46 are the same.
Fantastic lectures. Thanks a lot. What books do you recommend for learning: graph theory and its application in science and engineering. This will help a lot of people. Thank you in advance
Very nice
Perfect graphs are interesting because if we can find them easily then, you have a kind of heuristic to compute the chromatic number xhi(G) ; browse the graph finding maximal cliques...or try to compute w(G) instead of xhi(G). If you want to do the same for a random graph by a computer sortware..you will met the NP obstacle ...not enough computation time, when the size of graph (number of vertices) increase. One application of graph coloring is to make network (electronic, social,..) with parallel tasks and some independance between them.
Maria also proved a theorem that you CAN determine if a graph is perfect in polynomial time.
As given in this relatively new (pre)paper on arxiv (arxiv.org/pdf/1903.00208.pdf) the theorem was proven by others in 2005...and Maria and others improved the algorithm and computation complexity a few years ago.
Vertex Transitive graphs seem perfect, but they're not in this colouring sense. They include archamedian solids, infinite regular trees, hypercubes, complete bipartite, cycles, splays, infinite grids, a grid on torus etc… They're graphs where the nodes are indistinguishable. :) For example, think of a corner of a cube, now try to describe that corner to another person. :) They are symmetric everywhere, like a sphere.
Maybe HyperCubes 🚀 are an example of completely_perfect graphs. :-)
What is the particular significance of deleting vertices over edges?
Hang on, doesn't every complement of an odd cyclic graph already contain a cyclic graph, making that condition redundant? C(7)^C, for instance, contains C(7) going 1-3-5-7-2-4-6. Is there really an odd cyclic-complement graph where that is not the case?
In fact, what's wrong with this proof?
Theorem: Every complement of a cyclic graph of odd order k >= 7 contains the cyclic graph of order 3, and is therefore not perfect.
Proof: Number the vertices along the cycle 1, 2, ..., k. 1 is connected to 3 (since 1 and 3 are nonconsecutive), 3 is connected to 5 (since 3 and 5 are nonconsecutive), 5 is connected to 1 (not-adjacent since k >= 7).
So I guess my question is why bother with the "complement of a cyclic graph" part of the argument? A graph is perfect iff it contains an odd cycle. Done.
It is not just about containing a cycle, but also having no more edges.
For example you want 7 vertices with edges 1-2-3-4-5-6-7-1, but no more edges (no edges 1-3, etc.)
Similarly for "containing" a complement of a cycle you want exactly the edges you would expect (no more no less).
@@pifdemestre7066 Ooooh I see. And my 3-cycle counterexample doesn't work because a 3-cycle is a clique (unlike bigger cycles).
im a fan
(from previous vid): "If you'd like to watch more of this interview, where we g--"
*tap!*
nice
Do these rules still apply in three dimensions?
You could define something that was to polyhedra what graphs are to polygons (i.e., a graph, plus each edge can be part of some faces, maybe with some rules). I haven't heard of this being studied or having interesting results, outside of results about polyhedra.
@@iabervon How you're essentially describing simplicial sets. They are the foundation for practically all of homotopy theory
Has anyone else noticed that there are two page fours in that cartoon flipbook at the end?
Yes, same thing with ninth page.
I like her accent
Is she related to the other famous mathematician Chudnovsky?
Combinatorics!
Brains and beauty ♥️
At least Berge lived long enough to know that his theorem was proved true.
Not sure if he really did know that.
Numberphile! I love the strong representation you give to women in mathematics. I notice on almost all your videos featuring female mathematicians, a multitude of the commenters feel a need to comment on their physical appearances, which I hope you understand is condescending and objectifying for women in a field where they are already marginalized. However, perhaps your viewers don't all recognize the problems with this behavior. Maybe you could make a video addressing the inequity women face in the STEM field and address the appropriateness of these comments. Thanks!
Agreed on all points. It's great to see both male and female mathematicians get a chance to shine on these channels, but very disappointing to see how much more often people comment on the women's appearances than the men's.
@Puppet the only cringe here is all of the constant stream of men who are so lonely they feel the need to comment on these mathematicians' appearances, even going far enough to claim they have a "crush" as if they would EVER even have a chance with one of these women.. THAT is cringe dude... if you don't see it then you might just be cringey yourself 😌
@Puppet can you explain how I am misinformed? Women are marginalized in STEM- that is a research proven fact, and there are studies ranging all the way from preschool to K-12 to college to the professional field that show the nature of the inequity women face in STEM. I have a bachelor's degree in Mathematics and I'm working on a Master's degree in Math Education that requires that I specifically study research in this area. I am very informed. What data do you use to inform your opinions?
Moreover, beyond my education in math research, it doesn't take any sort of science to know that these kinds of comments are awkward and belittling- it just takes a shard of empathy, and a glance over at any numberphile video featuring a male mathematician, to see how this is not fair
@@invaderpopz Women dominate *all levels* of education. Yes, that includes graduate studies. The fact that in math, engineering, physics and perhaps a few other fields like philosophy men dominate doesn't mean that women are marginalized. Men and women have different interests, and that's okay.
That said, it is weird that so many people comment on their looks, and I agree that it is "cringe". Then again, the viewership is almost certainly predominantly male, and males generally are attracted to females.
Is anyone working on what happens when a planer graph is translated to a volume? I am interested in what happens to graph theory when you use a higher dimension to solve problems in a lower dimension, or vice versa.
For example drawing a planar graph in 3 dimensions, ddges may no longer intersect in this higher dimension, seems like cheating, but might have very useful applications in the real world. I understand that each higher spatial dimension introduces a new connection method, and new constraints, but is this true and provable? Do dimensions introduce new connection methods, and connection constrains? 3D introduces a Plane, 4D introduces a, what, Volume?
My understanding is that with Planar graphs we are trying to avoid intersecting edges, re-drawing a planar graph in 3 dimensions can allow edges to not intersect, but the 3rd dimension introduces the concepts where the closed area created by a subset of vertices and edges create a plane, in 2D planes have no way of intersecting, but in 3D, a graph can be drawn where edges do not intersect, but the planes created by edges and vertices do intersect. In 3D we want to avoid intersecting planes. Is this a valuable concept? Do you know anyone working on this type of thing, meaning proving or working on operations to create theorems equivalent to planar theory in higher dimensions? Or are there theorems that describe how map problems can be solved by changing dimensionality? Basically what I am getting at, is there a theorem that proves that any graph with intersecting edges in 2D can be drawn in 3D and not have intersecting edges? Can it be proven that any graph with intersecting planes drawn in 3D can be drawn in 4D and not have intersecting planes? Can it be proven that any graph with intersecting edges in 2D can be drawn in 4D and not have intersecting edges?
I _assume_ this would be valuable to scientists working on 3D graphics, and may have already been done in that field?
If you made it this far reading this comment, I thank you Maria Chudnovsky for your efforts and work, and I thank everybody at Numberphile for their superb productions.
You asked a lot of different questions, and I can't answer all, but let me try to add my two cents.
A graph can be defined as the list of it's edges. An edge is just a pair (ordered or not depending on whether the graph is directed of not) of vertices. Now, you can think of a 3D graph as a set of vertices, but an "edge" (or plane, though those are infinite most of the time) will consist of 3 vertices. This idea have been generalized by the concept of hypergraphs.
Regarding your "is there a theorem that proves that any graph with intersecting edges in 2D can be drawn in 3D and not have intersecting edges" question. In 2D, the edges partition the plane, but in 3D the same edges don'T partition the whole space. Therefore you will always be able to connect vertices in 3D without any two edge intersecting.
I'm lost...
mostly...
I think...
Maybe not...
I think I have a new crush
the ideal graph includes the criteria of having no binary vertices
Witchcraft!!!!!!
Maria I love you, you're so intelligent and charming
yikes
@@busimagen yikes
Have to say, as well as being seriously intelligent and well qualified...we have a cutie on our hands here....!
the pen on the brown paper is really cringy...