Unsolved Problems in Graph Theory

  Рет қаралды 10,003

ThoughtThrill

ThoughtThrill

Күн бұрын

Пікірлер: 22
@lyrimetacurl0
@lyrimetacurl0 7 күн бұрын
"look at this graph"
@natepolidoro4565
@natepolidoro4565 8 күн бұрын
Great quality video. I love this channel.
@marcelob.5300
@marcelob.5300 7 күн бұрын
Absolutely, they deserve 1M subscribers
@Fepo.productions
@Fepo.productions 8 күн бұрын
Me, who is supposed to revise GCSE level maths for my mocks Random video explaining a maths concept I didn't even think could be thought up in fiction Me: hmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
@ThoughtThrill365
@ThoughtThrill365 8 күн бұрын
They are unsolved for a reason 😄
@roy11gg
@roy11gg 5 күн бұрын
5:39 Kittler❤
@Busybody007
@Busybody007 7 күн бұрын
amazing animation soo easy to understand.
@davethesid8960
@davethesid8960 5 күн бұрын
0:18 - That's why in Hungarian we say "gráf" and "grafikon" to distinguish them.
@DeadJDona
@DeadJDona 4 күн бұрын
9:30 what's the ratio of a sizes of triangles, adjacent to point for n-gon?
@patrickgambill9326
@patrickgambill9326 7 күн бұрын
9:58 What about the graph with no edges? Aren't the chromatic and total chromatic number the same?
@nivpearlman6514
@nivpearlman6514 7 күн бұрын
Delta(G)=0 X(G)=X''(G)=1 They are the same but trivially and equal to one
@patrickgambill9326
@patrickgambill9326 7 күн бұрын
Makes sense. I definitely misheard the video. They said maximum degree, not ordinary chromatic number 😅
@isavenewspapers8890
@isavenewspapers8890 6 күн бұрын
This is an interesting edge case (no pun intended). For any edgeless graph, the chromatic number and the total chromatic number are either both 0 or both 1 (and hence the same number). The former arises only in the case of the unique graph with no vertices-the order-zero graph. After all, the graph vacuously starts out with every vertex and edge colored, so we don't need to pick up a single crayon. What about the maximum degree of this graph? Finding a graph's maximum degree amounts to finding the maximum of the set of the degrees of its vertices. But if you take the set of the degrees of the vertices of the order-zero graph, you just get the empty set. You can't take the maximum of the empty set, so the maximum degree of the order-zero graph is undefined. ... At least, I think that's how it works. For a more airtight answer, I'd probably need to be more careful about some of the formal definitions.
@marcelob.5300
@marcelob.5300 7 күн бұрын
Great content!
@patrickgambill9326
@patrickgambill9326 7 күн бұрын
These are great! Do you like the switching reconstruction and vertex reconstruction problems?
@Dravignor
@Dravignor 7 күн бұрын
Where's the graph isomorphism problem?
@poland4m17s
@poland4m17s 2 күн бұрын
What's that
@Dravignor
@Dravignor 2 күн бұрын
@@poland4m17s Say you have two "different" graphs, and you notice that for any two adjacent vertices/edges in the first graph, there is a corresponding pair of adjacent vertices/edges on the second one, such that you don't end up with any extra vertices/edges from one of them that doesn't correspond to anything from the other. You could think of this correspondence as a mapping that "preserves the structure" between the two. This is the idea of graph isomorphism. The Graph isomorphism problem seeks to automate the process of finding an isomorphism between any two graphs, and asks whether you can always determine whether such two graphs are isomorphic or not in a given amount of time (Specifically O(nᵏ) if you know computational time complexity).
@Mooonhead
@Mooonhead Күн бұрын
@@Dravignor The question you are looking for would fit better into a theoretical computer science video. But it is certainly one of the easier algorithmic problems to explain and sits at an incredibly interesting spot in our current complexity landscape. Maybe he will make a video on TCS later on and include this problem? Edit: To be clear, I think you want him to address the problem of figuring out in which complexity class it sits right? Because simply solving the graph isomorphism problem is quite easy for any given instance if you don't care about time constraints.
@Dravignor
@Dravignor Күн бұрын
@Mooonhead Fair enough. Granted, I do not know much about graph theory; my only exposure to the subject was part of a rushed course in Discrete Math, but I was certainly interested in it at the time so I was hoping this video would bring more light into it. I do however appreciate your added clarity about the problem
@oserodal2702
@oserodal2702 6 күн бұрын
A category is just a funny graph with a few rules. Why not do unsolved problems for category theory?
@omfgacceptmyname
@omfgacceptmyname 6 күн бұрын
divine ambitions? really weird way to say that 5:15 this whole section was strange
Introduction to Graph Theory: A Computer Science Perspective
16:26
The Unsolved Problem of Reconstruction
20:33
Wrath of Math
Рет қаралды 15 М.
Леон киллер и Оля Полякова 😹
00:42
Канал Смеха
Рет қаралды 3,3 МЛН
How many people are in the changing room? #devil #lilith #funny #shorts
00:39
Turn Off the Vacum And Sit Back and Laugh 🤣
00:34
SKITSFUL
Рет қаралды 11 МЛН
Mandelbrot's Evil Twin
7:47
2swap
Рет қаралды 413 М.
Why 4d geometry makes me sad
29:42
3Blue1Brown
Рет қаралды 1 МЛН
Every Infinity Paradox Explained
15:57
ThoughtThrill
Рет қаралды 501 М.
How This Autonomous Liquid Metal Finds Its Way Through Mazes
8:41
The Action Lab
Рет қаралды 223 М.
Every Unsolved Geometry Problem that Sounds Easy
11:37
ThoughtThrill
Рет қаралды 494 М.
The Oldest Unsolved Problem in Math
31:33
Veritasium
Рет қаралды 12 МЛН
Math's Map Coloring Problem - The First Proof Solved By A Computer
9:04
Quanta Magazine
Рет қаралды 238 М.
You're Probably Wrong About Rainbows
27:11
Veritasium
Рет қаралды 4,2 МЛН
Unsolved Math Problems Solved After Eons
11:34
ThoughtThrill
Рет қаралды 92 М.
Every Math Paradox Explained - FULL Video
33:01
ThoughtThrill
Рет қаралды 199 М.