A Breakthrough in Graph Theory - Numberphile
video description
1. Abstracting the concept, this seems to be a manner of creating mappings
2. I have the feeling this can be related to or has application in encoding and possibly encryption (analogous in concept to increasing key bit size with RSA, but with groups, rings, etc)
3. Can any graph with n-colors be shown to be the tensor product of G and H where the colors for both are less than n? What if the minimum number of colors for G and H are not equal? I suppose the original graph would have to have a minimum color of 3, because if it had 2, it would be the product of two graphs with a color of 1, which would be the trivial case
4. The new questions seems to be identifying where the divergence point is. That is, if all tensor products of graphs less than n-vertices produce a graph that may be colored with less colors than those in the product, what is n?
5. Surely I'm not the only one to wonder, -Has anyone used this to plan the seating chart for a wedding reception? -
Date: 2022-04-09
Related videos
Comments and reviews: 9
Michael
Me thinking there are too many different colors between. To say -between- 2 red or 2 yellow. Humans are liked to say -color- and never tell exact as discribed in (nm) frequency. So we as humans build up some spooky case around the -whole value-. What about to look at this question within just 1 color and use the frequency as to discribe and ask again. Would be more accurate. To know better about color. Even to scale up -color- into 1st 2nd 3rd. to some ratio. Color as we use in art is some -line- from frequency to next. Unit circle related view on colors. And still no explanation for color. So about this question we stuck into -line- as we builded up. Don't deny the truth about frequency also not into color. The logic behind mathematics needs to be used right to use it into mathematics.
reply
Me thinking there are too many different colors between. To say -between- 2 red or 2 yellow. Humans are liked to say -color- and never tell exact as discribed in (nm) frequency. So we as humans build up some spooky case around the -whole value-. What about to look at this question within just 1 color and use the frequency as to discribe and ask again. Would be more accurate. To know better about color. Even to scale up -color- into 1st 2nd 3rd. to some ratio. Color as we use in art is some -line- from frequency to next. Unit circle related view on colors. And still no explanation for color. So about this question we stuck into -line- as we builded up. Don't deny the truth about frequency also not into color. The logic behind mathematics needs to be used right to use it into mathematics.
reply
Yves
Looking at the 'double graph' at 15m it reminded me of a game of untangling I played for a while on the Net. GooglePlay has under the name Untangle and it is available under the same name a few other game oultlet on the Net (like chiark. greenend. org. uk. At first glance I was sure there was 2 sub-graphs in the video, eyes already used to such graphic confusion. When I first looked at the video, my reflex was to untangle the thing until I realized ther was 2 subsets. Certainly a practical relation between the demostration in the video and that game.
reply
Looking at the 'double graph' at 15m it reminded me of a game of untangling I played for a while on the Net. GooglePlay has under the name Untangle and it is available under the same name a few other game oultlet on the Net (like chiark. greenend. org. uk. At first glance I was sure there was 2 sub-graphs in the video, eyes already used to such graphic confusion. When I first looked at the video, my reflex was to untangle the thing until I realized ther was 2 subsets. Certainly a practical relation between the demostration in the video and that game.
reply
Amipotsophspond
mathematician are really bad at naming things they should just use just use UUIDs to name all their stuff and replace all of their symbols.
2 + 2 = 4 could be
2 b0187310-5486-4b22-a85b-3d747e6aecb3 2 b0ff7c42-daf0-4a03-b128-f8d9e34dbc7b 4
a graph as part of graph theory could be fb3d2164-f79e-4164-b4b2-4843f77f2227 a graph as part of a x y plot could be af52bf99-6665-4639-8f9d-de0f172c46fc
it can be made to be display in human readable LaTex that collides the symbols till new symbol are made as to not collide.
reply
mathematician are really bad at naming things they should just use just use UUIDs to name all their stuff and replace all of their symbols.
2 + 2 = 4 could be
2 b0187310-5486-4b22-a85b-3d747e6aecb3 2 b0ff7c42-daf0-4a03-b128-f8d9e34dbc7b 4
a graph as part of graph theory could be fb3d2164-f79e-4164-b4b2-4843f77f2227 a graph as part of a x y plot could be af52bf99-6665-4639-8f9d-de0f172c46fc
it can be made to be display in human readable LaTex that collides the symbols till new symbol are made as to not collide.
reply
Birkl
Didn't see it in the comments so I want to throw it out there:
Showing that a Sudoku can be converted into a graph coloring problem (9-COL in this case) shows that it is either NP-Complete or NP-Hard (not entirely sure which one. One way it shows the one the other way it shows the other. 9-COL then can be converted into a SAT problem.
And. I don't know where I'm doing with this but it's just great I found something that touches on my knowledge of theoretical informatics.
reply
Didn't see it in the comments so I want to throw it out there:
Showing that a Sudoku can be converted into a graph coloring problem (9-COL in this case) shows that it is either NP-Complete or NP-Hard (not entirely sure which one. One way it shows the one the other way it shows the other. 9-COL then can be converted into a SAT problem.
And. I don't know where I'm doing with this but it's just great I found something that touches on my knowledge of theoretical informatics.
reply
Nathaniel
What if you have 5 items that all border each other. Are we saying that shape is not possible? Cause if it is, then you would obviously need more than 4 colors. And given I just build a stand-out of triangles that has 12 points coming together in one spot (Made an inverted bowl essentially) I am 100% sure we can make a shape with more than 4 things touching. I guess individual points don't count it has to be a plane, but what does that do for 4 corners on the US map?
reply
What if you have 5 items that all border each other. Are we saying that shape is not possible? Cause if it is, then you would obviously need more than 4 colors. And given I just build a stand-out of triangles that has 12 points coming together in one spot (Made an inverted bowl essentially) I am 100% sure we can make a shape with more than 4 things touching. I guess individual points don't count it has to be a plane, but what does that do for 4 corners on the US map?
reply
Martin
The two kinds of graphs are really the same thing in a certain sense. If G is a set then the two kinds of graphs are two different ways of representing a set of ordered pairs of elements of G. For instance, let G = -1, 2, 3-. To represent the ordered pair (1, 2) on a graph with axes you can plot the point with coordinates (1, 2. To represent (1, 2) in a directed graph you draw an arrow from node 1 to node 2.
reply
The two kinds of graphs are really the same thing in a certain sense. If G is a set then the two kinds of graphs are two different ways of representing a set of ordered pairs of elements of G. For instance, let G = -1, 2, 3-. To represent the ordered pair (1, 2) on a graph with axes you can plot the point with coordinates (1, 2. To represent (1, 2) in a directed graph you draw an arrow from node 1 to node 2.
reply
Ike
TIL that mathematicians really like coloring things: 3
Btw. there's another real-world application for coloring graphs that has to do with cell phone towers. If two towers are within range they should not use the same frequencies because of interference, so the problem can be expressed as a colored graph where the colors are the available cellular network frequencies.
reply
TIL that mathematicians really like coloring things: 3
Btw. there's another real-world application for coloring graphs that has to do with cell phone towers. If two towers are within range they should not use the same frequencies because of interference, so the problem can be expressed as a colored graph where the colors are the available cellular network frequencies.
reply
Axel
I struggle to understand the example given in the video as an appropriate application for Graph Theory. The example concluded 2 pairings for an optimised rotation for the weekends, but the Math Prof. never ends up meeting with the Teachers even though they could. So why would we call this optimised or am I missing the point?
reply
I struggle to understand the example given in the video as an appropriate application for Graph Theory. The example concluded 2 pairings for an optimised rotation for the weekends, but the Math Prof. never ends up meeting with the Teachers even though they could. So why would we call this optimised or am I missing the point?
reply
Wafikiri
I remember reading of this graph problem in the '70's in Scientific American. Maybe they called the article 'Hunting the Snark' (the snark being a graph which could not be coloured in only four colours, after Lewis Carrol's bathtub-carrying beast character?
reply
I remember reading of this graph problem in the '70's in Scientific American. Maybe they called the article 'Hunting the Snark' (the snark being a graph which could not be coloured in only four colours, after Lewis Carrol's bathtub-carrying beast character?
reply
Add a review, comment
Other channel videos
