I think I've found a universal solution to all such party problems. You invite one graph theory specialist to the party. Since all the guests are part pf a graph colouring problem, they all have something in common with him.
@@TemporalOnline It is not possibele to brute force. It is too big of a range. Not only number of vertices is enormous, but number of possible graphs for each specific number of vertices is huge and grows further as the number of vertices grow. It might not be feasible to check from 5 to 1000 vertices even in this century.
I love these 20 minute videos because it allows the guest to really “sell” the topic. I never knew graphs could be used this way, absolutely fascinating demonstration by Dr. Klarreich!
I remember Steve Hedetniemi from many conferences in the 1980's - he always had the most interesting problems to work on. It's wonderful that he is still teaching.
I think it was Pandora radio? when it was still just a visual website of nodes(album covers) and edges (labeled with adjectives and genres) when I first thought graphs were actually useful. In this case songs were nodes with typological edge types. Following the edges revealed the decision making for the next song. That one simple case changed my understanding of what could be done with graphs in computing for connecting data by proxy to reveal hidden graph structures quickly. The fewest number of colors in this case would also ensure artists and songs, even by a cover band, would not be repeated and get stuck accidentally in a self referential loop in the graph. I later designed an art museum tour creation app based on graphs where people could name the edge type they wanted to traverse, such as color, material, genre, etc. Worked great. 👍 I went to art school, but math truly makes the world usable.
@X E I agree with you. However if you think of a network as being an n-dimensional object, then nodes would be the corners or vertices, and edges the the lines connecting the vertices. Like a (standard) die has 6 faces, 8 vertices, and 12 edges connecting the vertices.
I love that the guy who came up with the conjecture was simply delighted to have an answer to the problem. It shows his love of math and learning isn't about ego, but about finding answers.
It is about ego. HE wants to learn something. HE wants to do math and loves it. For himself. That's as egoistic as it can get and there is nothing wrong with that. Perhaps you meant second-handed appraisal (primarily being valued by others) rather than ego :]
Gotta love how this comes out right before Christmas, when people gather with their families and commonly wonder why it is so hard to get along with each other.
Usually counterexamples and the process of taking numbers "as big (or small) as you need" is really used in analysis. I remember discussing a possible proof and we were talking about approximating some real valued quantities with rational numbers. The thought process went something like "...we can approximate this number with error epsilon, lets just take epsilon divided by a million to be safe..."
@@NoNameAtAll2 squares are hard man :D I remember rounding 4pi/17 to 10pi when proving a function was integrable. If you just have to show an inequality to be true usually you want easy numbers to work with ;)
I also remember the other day I was pretty sure that given a number n and some calculations stuff failed for n+1 but who casres? Slap there 10n and you are done
I like way mathematicians think. They ask a question and when they eventually get answer they ask another question. Like: I think it may be true. Is it true? Sometimes it is true... But not always. When EXACTLY is it true? What's the smallest counter example?
All science is like that - or at least, it _should_ be and _ought to_ be like that. Pure mathematics is more resistant to temptations to skew, falsify, or hide results to get more funding, since the "results" are generally harder to _directly_ profit from. If you're in it, you're in it for the truth, not for the money.
@@HaloInverse a proper scientific hypothesis should always be falsifiable, so if you hear a scientist asking "is it true?" that should be a big red flag that they don't understand the purpose of their own job. aside from that, you're right that they should ask a lot of questions.
Love the subtle jab at Matt Parker: 'Or you could go for my favourite audiobook so far, that's - **scrolls away from Humble Pi audiobook** - Endurance by Alfred Lansing...'
It brought such a smile to my face at the end when Erica mentioned having gotten Hedetniemi's his reaction to finally getting an answer to his conjecture. Any chance we can get you guys back on camera, with him, talking about this together?? :)
My mother was not into sudouks, because it was "about numbers". I said to her, that do not think those as numbers, but as symbols. She is still doing sudokus - about a ten years later.
@@marcoswappner8331 same in Ukrainian (graph in graph theory is "граф" and graph of function is "графік"), but "граф" also means "count" (a person, as in count Dracula or count Dooku)
Graph (in English): the X-Y Cartesian coordinate thing for a function, or a collection of nodes/vertices and edges that connect said nodes. Graphic (in English): depending on context, a digital image or an adjective used to describe art or gory detail. Apparently there's an additional context for these words and that's linguistics, but this isn't Linguaphile (sadly)...
Isn't it the same as solving a sudoku the traditional way with numbers? Numbers and colors represent the same thing, they're just a different type of visualization.
@@aijoo00 Yeah, pretty much the same. I've constructed (converted actually) sudoku using, letters, dingbats (remember them?) and other arbitrary symbols. It never occurred to me to use colors. The biggest problem with not using numerals is, if it's a really difficult example, It's much harder to pencil in candidates.
@@aijoo00 Objectively, yes. But the human mind is subjective, and some people will find it easier one way or another. In my case, I know I would have a harder time solving a color sudoku, as I can visualize numbers better than colors.
I'd absolutely watch a more in depth maths show made by the Numberphile crew to be a Netflix show. Go really in depth with the maths instead of just the surface level stuff, but still produced by the Numberphile guys who are used to explaining things in a more lay way.
What a great introduction to graph theory, and so easy to understand. I can instantly see various situations where it could be applied: seating orders, forming teams, arranging work shifts, traffic control, urban planning... Also, anything that has circles connected by lines looks like a finite-state machine to me. xD
Great explanation. Didn't even have to open a book to see the conjecture. Love the simple language devoid of jargon. Brilliant explanation and analogies 😇
It was probably a bit easier to draw than the map of the USA with 50 states (although 2 of them don't touch the other so you'd only have to worry about the "contiguous 48 states").
It's incorrect, as Victoria and Tasmania do have a land border: it runs across Boundary Islet. This fact was discovered only after the border was fixed.
In my Graph Theory class, we had to prove this statement for the special case chi(G)=3 on the final... i can thankfully say that i got it, but unfortunately almost no one (understandably) did
I found the first few minutes of the video to be wonderful exposition. I scrolled down to see who this new(?) guest on Numberphile was. I wasn't surprised. I have been fan of Erica Klarreich's writing on Quanta for some years now.
Man this was an awesome explanation. I put off watching this all day cause I was like "okay, Graph Theory, I'm gonna need to focus for this one." I think that's the first time there's been a numberphile video using the word "tensor" that I actually followed. Thank you!
i thought i was procrastinating by watching math vids when i'm supposed to be making my project as senior thesis in graphic design but i actually learned something i can apply wow
Very nice lecture indeed. Two small remarks: The graph of a function, as known from school, does fall under the same umbrella as a graph in Graph Theory. Only it is drawn in a different way. And "tensor product" is not the only name for the product in question, nor even the most common name. Just "product" or "Cartesian product" seem more used.
22:27 We can safely assume that one's friend is made of at lest one particle of the observable universe. Therefore, nobody has as much friends. Now, if we speak about imaginary friends, we have to understand how much information the mind can hold. I don't thinks it's that many, but that would be a conjecture.
If you're seeking evidence to support your hypothesis, I can confirm that each of my two friends has more than one elementary particle. Mathematics gets loony.
@18:00 You don't even need to look at the combination of the two graphs to find compatible people who were separated. The Job graph by itself had already forced the compatible Teacher and Professor to be different colors, which at least raises the concern when combining two more complex graphs (requiring many more colors) filled with such indirect separations. (I say many more colors because you need room to simplify.)
I think one fact is important to note: the reason why this conjecture seems _obviously_ false with the presented example is that for most friend groups, we only have a subgraph of the full product. Obviously there are subgraphs, i.e. graphs where certain nodes are deleted, that can be colored with fewer colors. That's not what the conjecture is about, though.
@@unvergebeneid I'm guessing you mean that people don't have a friend for every combination of job and hobby in real life, so their intuition tells them that the problem is easier than it actually is . The conjecture does seem obviously false at first glance because, as Erica points out, you're throwing away information that can only help you if you just default to the starting solutions. I quickly realized how difficult it was to actually create a counterexample, however, since you apparently have to make both G and H require at least 5 colors, which means that even the simplest examples you want to try take quite a while to write down (I gave up already, haha).
@@trogdorstrngbd yes. For the problem in the video you will of course have plenty of real life friend groups that will allow everyone to come on the same weekend, i.e. the graph only needing one color. But as you said, that's not what this conjecture is about, so this example will mislead many people which is also reflected in the comments for this video.
I have gotten into graph theory recently. I like it a lot and It makes neural networks easier to understand. It is pretty complicated if you try to look at the analysis portion of it.
0:40 Just to point out that the confussion for the word graph comes from the shortening of 2 different greek words... Γραφική αναπαρασταση meaning graphical representation is the one used for x, y axis and Γράφος is the one used for the network representation. Englishs words and phrases, as a habbit, have always been shortened for the ease of use but details are lost in the process
"i don't know if there's anyone out there with that many friends..." right after saying the number is orders of magnitude larger than the total number of particles in the universe :O
Discrete math (which includes things like graph theory) is very different from something like calculus. Discrete is like logic puzzles, and challenging but fascinating. Integral calculus/ differential equations is more procedural like algebra, and easier but boring.
Doing things autonomously instead of being forced makes them more fulfilling. I remember reading books in school and hating them, and then rereading those same books after graduation in my free time. Industrial Society and its Future explains the phenomenon well.
Doing math under time pressure and deadlines added unnecessary burden to an otherwise fascinating subject, also the grading system encourages results over learning so there you go.
Brady, thanks to you I had the joy of listening Edward Frenkel's audiobook version of his book Love and Math: The Heart of Hidden Reality, and I've wanted for a while for mathematics to be a bigger part of my life, so thank you for promoting (beyond creating, of course) great popular mathematics content.
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.
Odd. My father is a retired math professor who started in topology, and I have a special gravity towards graph theory but have never heard of Het.. Hetde... Hedetniemi’s conjecture. I’ve always known it as the graph coloring problem , and that 3+x (x>=1) colors is the very minimum needed
Hedetniemi's conjecture (now disproven) is that the graph which is the tensor product of two graphs can not be colored with fewer colors than either of the two graphs individually. So it's not really the same as the graph coloring problem.
Wow! Yaroslav Shitov is my teacher in university. Wasn't expecting to see him there
Whoa
So is he the math professor who collects stamps, does yoga or meditates?
Where do you study at?
That is an uncomfortable family name.
@@aheldar я учусь в М(ФТИ)
I think I've found a universal solution to all such party problems. You invite one graph theory specialist to the party. Since all the guests are part pf a graph colouring problem, they all have something in common with him.
Top 3 comment I've read in this section
Ah but then there's the philosophical question, if you invite a graph theory specialist to the party, will anyone else come?
@@gregergreg just dont tell the other guests that you are inviting a graph theory specialist
Successful Event Managing 101
But then it will be a lecture (one to many). You want every pair of guests to have something in common so whoever one talks to, they could get along.
She is fantastic at explaining things
+100
It was a long explanation. But I was able to follow the explanation. Nice work. 👍
yep, great teacher.
+4^10000
Yeah pal
So the smallest counter-example is between 5 and 4^10000 vertices
so now we just need a sufficiently large computer to find the smallest counterexample
@@paradoxica424 And everybody will moan forever because we brute forced it instead of insighting it.
Very accurate estimate compared to "between 13 and Graham's Number"
@@TemporalOnline 4^10000 is quite large, to pure-brute force it you would need much more atoms than the universe has.
@@TemporalOnline It is not possibele to brute force. It is too big of a range. Not only number of vertices is enormous, but number of possible graphs for each specific number of vertices is huge and grows further as the number of vertices grow. It might not be feasible to check from 5 to 1000 vertices even in this century.
14:28 Graphs are always G or H because G stands for Graph and H stands for Hparg >:-)
She is very clear, more of her please!
Was a bit for idiots this time though... the simplest things explained reaally slowly
@@StefanReich no u
@@StefanReich perfect for a big idiot like me
I love these 20 minute videos because it allows the guest to really “sell” the topic. I never knew graphs could be used this way, absolutely fascinating demonstration by Dr. Klarreich!
I remember Steve Hedetniemi from many conferences in the 1980's - he always had the most interesting problems to work on. It's wonderful that he is still teaching.
I think it was Pandora radio? when it was still just a visual website of nodes(album covers) and edges (labeled with adjectives and genres) when I first thought graphs were actually useful. In this case songs were nodes with typological edge types. Following the edges revealed the decision making for the next song. That one simple case changed my understanding of what could be done with graphs in computing for connecting data by proxy to reveal hidden graph structures quickly. The fewest number of colors in this case would also ensure artists and songs, even by a cover band, would not be repeated and get stuck accidentally in a self referential loop in the graph. I later designed an art museum tour creation app based on graphs where people could name the edge type they wanted to traverse, such as color, material, genre, etc. Worked great. 👍 I went to art school, but math truly makes the world usable.
That was really interesting, the application of maths into other totally unrelated fields.
@X E I agree with you. However if you think of a network as being an n-dimensional object, then nodes would be the corners or vertices, and edges the the lines connecting the vertices. Like a (standard) die has 6 faces, 8 vertices, and 12 edges connecting the vertices.
I love that the guy who came up with the conjecture was simply delighted to have an answer to the problem. It shows his love of math and learning isn't about ego, but about finding answers.
It is about ego. HE wants to learn something. HE wants to do math and loves it. For himself. That's as egoistic as it can get and there is nothing wrong with that. Perhaps you meant second-handed appraisal (primarily being valued by others) rather than ego :]
@Steven Moore the love itself no, but the pursuit of it, is.
I loved how clear and conscise she was expressing herself!
Gotta love how this comes out right before Christmas, when people gather with their families and commonly wonder why it is so hard to get along with each other.
Bengt Lüers ohmy gosh 😂
My family would be a complete graph here
@@Danscottmusic lol
Somehow the answer of "they're the wrong colour" is depressingly true in some families.
Usually counterexamples and the process of taking numbers "as big (or small) as you need" is really used in analysis.
I remember discussing a possible proof and we were talking about approximating some real valued quantities with rational numbers. The thought process went something like "...we can approximate this number with error epsilon, lets just take epsilon divided by a million to be safe..."
Why not epsilon squared?
@@NoNameAtAll2 squares are hard man :D
I remember rounding 4pi/17 to 10pi when proving a function was integrable. If you just have to show an inequality to be true usually you want easy numbers to work with ;)
I also remember the other day I was pretty sure that given a number n and some calculations stuff failed for n+1 but who casres? Slap there 10n and you are done
Graham: „I could maybe prove that C < 10 billion but let‘s be careful and prove C < Graham‘s number instead.“
Hedetniemi is 80 years old and still teaching.
@Steven Moore It is cool and he is a wonderful person if you get to know him.
C L E M S O N
Wow
I really liked how Erica explained this, I felt like I really understood it despite not doing graph theory before!
IKR
This problem is so much simpler when your friend graph is an empty graph.
I can color it with 0 colors and binge watch Netflix every weekend.
man how stoked would you be getting an answer to your conjecture after 50 years
I like way mathematicians think. They ask a question and when they eventually get answer they ask another question.
Like:
I think it may be true.
Is it true?
Sometimes it is true...
But not always.
When EXACTLY is it true?
What's the smallest counter example?
All science is like that - or at least, it _should_ be and _ought to_ be like that. Pure mathematics is more resistant to temptations to skew, falsify, or hide results to get more funding, since the "results" are generally harder to _directly_ profit from. If you're in it, you're in it for the truth, not for the money.
gonna keep it as short and simple problems when u need to deal with these never ending things for a big part of your life i guess😉
@@HaloInverse a proper scientific hypothesis should always be falsifiable, so if you hear a scientist asking "is it true?" that should be a big red flag that they don't understand the purpose of their own job. aside from that, you're right that they should ask a lot of questions.
Yes that is the way of the mathematician. Similarly, they like to generalise things ad infinitum.
That's standard procedure. When you try to get to the bottom of the things, you just ask this questions naturally.
Love the subtle jab at Matt Parker: 'Or you could go for my favourite audiobook so far, that's - **scrolls away from Humble Pi audiobook** - Endurance by Alfred Lansing...'
this woman is such a good explainer
Fake Account she has such a smoothing voice too
true, she's gifted
@@fugreek One trait of very smart people is the ability to explain convoluted concepts in a clear and concise manner
It brought such a smile to my face at the end when Erica mentioned having gotten Hedetniemi's his reaction to finally getting an answer to his conjecture. Any chance we can get you guys back on camera, with him, talking about this together?? :)
"Let's start by coloring the economist red."
Must be a Marxist.
Those damn commies
Or a Republicunt.
That makes as much sense as an anti vax doctor.
I perhaps should have said "Marxian" rather than "Marxist" in reference to the economist.
@@RolandHutchinson Marxist works too, contrary to much public understanding it's still taught in most universities, it's the foundation of sociology.
Brilliant introduction to graph theory
Intro?!
@@liamlouw4643 exactly, that was his point. He meant that there should be an intro
Yes
@@ankitaaarya The first 10 minutes of this video are intro...
@@MrNacknime exactly
Whoelse but numberphile who will discuss really complicated maths mysteries in laymans terms. Thank you!
3 brown 1 blue
@@subschallenge-nh4xp -- It's a great channel, but it's not as accessible as most of Numberphile's content.
My mother was not into sudouks, because it was "about numbers". I said to her, that do not think those as numbers, but as symbols. She is still doing sudokus - about a ten years later.
This professor is so clear and explains so well.
What a blessing it would have been to have her as teacher in my university math lectures.
I love these numberphile videos. They really inspire me and make me want to explore even deeper in maths
To be fair, using colours in a sudoku puzzle might be quite useful for children, especially like 4 by 4s and 6 by 6.
Yes
How would a 6x6 sudoku work? Pretty sure sudoku sizes have to be square numbers.
@@unvergebeneid I've seen 6x6 sudokus divided up into six 2x3 rectangles.
@@unvergebeneid I know it's a thing, there used to be one in my local daily paper... It's split into 6 2 by 3 rectangles.
@@DomenBremecXCVI oooh, okay, if you allow rectangles you can use any number that's not a prime. Clever.
Oooh! I never realized until I saw the quanta magazine picture! I have read so many articles by Erica, she's great!
That's genius, taking a complex subject and presenting it in a manner accessible to non-experts.
Thats exactly why Im into mathematics. If I want to become a rich person with friends and a mansion, I just declare myself as one.
Let me be a rich person.
Since I am rich, I no longer have to write proofs for a living.
END PROOF.
You have two options. Option number one is mathematician. Option number two is lefty.
16 minutes of setup but i really felt that I understood the issue. So nice. She is a really good teacher, even if she may not be. Really good.
A really great intuitive explanation of tensor graphs! Thanks Erica!
The auto subtitles are saying "head-at-knee Amy's conjecture" and it's hilarious.
My brain was hearing it that way even without subtitles.
Amy finds this one just a little harder than Rodin's Thinker found whatever he was thinking about.
And so a few hundred people across the globe just tried hitting their head with their knee, chuckling like morons. Well, at least I did.
Google needs to upgrade their calculator and autosubtitle alghoritms I guess :D
Numberphile's logo is π and currently they have 3.14 Million subscribers..........
Coincidence? I think not!
Is this our "pi million" sub special ?!
The Blue Fox Productions I screenshotted it
7 months later I saw your comment and checked current subscriber count... 3.41 million. Coincidence? Yeah probably
The recommended Numberphile videos about graph theory are a graph theory problem unto themselves.
In Polish there is no ambiguity wirh graph and graph. Graph in graph theory is called graf, graph of function is called wykres.
In portuguese the graph for graph theory is "grafo" and the other is "gráfico"
@@JoaoVictor-gy3bk Same as in Spanish.
@@marcoswappner8331 same in Ukrainian (graph in graph theory is "граф" and graph of function is "графік"), but "граф" also means "count" (a person, as in count Dracula or count Dooku)
Stop flexing your superior languages on us unilingual people! ;-;
Graph (in English): the X-Y Cartesian coordinate thing for a function, or a collection of nodes/vertices and edges that connect said nodes.
Graphic (in English): depending on context, a digital image or an adjective used to describe art or gory detail.
Apparently there's an additional context for these words and that's linguistics, but this isn't Linguaphile (sadly)...
I would be really impressed if I saw someone solving a sudoku with that color technique
Isn't it the same as solving a sudoku the traditional way with numbers? Numbers and colors represent the same thing, they're just a different type of visualization.
kylteri Yeah actually I’d never thought about solving sudokus with coloring problem.
@@aijoo00 Yeah, pretty much the same. I've constructed (converted actually) sudoku using, letters, dingbats (remember them?) and other arbitrary symbols. It never occurred to me to use colors. The biggest problem with not using numerals is, if it's a really difficult example, It's much harder to pencil in candidates.
@@blindleader42 maybe he's just saying he's ALWAYS impressed when seeing someone solve one? XD
@@aijoo00 Objectively, yes. But the human mind is subjective, and some people will find it easier one way or another. In my case, I know I would have a harder time solving a color sudoku, as I can visualize numbers better than colors.
I remember the „Every graph is 4-colorable“ book, one of the largest in the library at the Mathematical Institute where I studied.
This actually made sense, wish had teacher like this explain everything.
Erica Klarreich seems to be a wonderful teacher!
i am so charmed by all the examples of jobs the professor gives are things related to the university!!
Gotta comment on the most important part here:
Stamp collecting is a form of meditation and collectors are a blast at parties.
I like this video.
Exactly
There's a flaw in the reasoning: Why watch Netflix when you can watch Numberphile?
I'd absolutely watch a more in depth maths show made by the Numberphile crew to be a Netflix show. Go really in depth with the maths instead of just the surface level stuff, but still produced by the Numberphile guys who are used to explaining things in a more lay way.
What a great introduction to graph theory, and so easy to understand. I can instantly see various situations where it could be applied: seating orders, forming teams, arranging work shifts, traffic control, urban planning... Also, anything that has circles connected by lines looks like a finite-state machine to me. xD
She is a professor I would like because she writes so beautiful while most professors’ writing are hard to read as hell.
And explains things well.
Great explanation. Didn't even have to open a book to see the conjecture.
Love the simple language devoid of jargon.
Brilliant explanation and analogies 😇
I like the follow up paper disproving it asymptomatically.
I absolutely didn’t know about graphes being a mathematical object this way, and this is super interesting
That explanation though, great teacher! Wish my uni professors were that great at explaining graph theory...
Youre channel is one reason I probably attempt to become a math teacher next year😂
I wish you all the best, but I'm glad your goal isn't to become an English teacher.
Did you?
@@oz_jones thanks for reminding me of this comment, I didnt knew it existet. And yes, I‘m currently writing my bachelor thesis 😂
Erica is a great presenter! Excellent video.
In dutch, there are different words for graph and graph. ;)
grafiek is the one with axi, while graaf is the one that represents a network.
graph
same here in polish
Same in french. English just seems to be running out of words
@@natmath2576 Oh, it's just the worst.
And what's the one that is a count?
Wow, you connected the dots very well on this one!
Dammit
This is a really great video. Interesting concept, explained in depth, but in an understandable and engaging way. Erica was fantastic.
One of my favorite numberphile videos ever!
Subtle Australian states graph
It was probably a bit easier to draw than the map of the USA with 50 states (although 2 of them don't touch the other so you'd only have to worry about the "contiguous 48 states").
And subtly pointing out that Brady's home state of South Australia is the superior state because it has the most borders.
Why so "sa", mate?
(｀・ω・´)
I too have considered mating offspring with either Australians or Britain’s
It's incorrect, as Victoria and Tasmania do have a land border: it runs across Boundary Islet. This fact was discovered only after the border was fixed.
Maybe its G & H because G is for graph and H is the next letter!
Yep, that's exactly it. Unlike physicists, mathematicians are lazy bastards in terms of coming with nomenclatures.
It's because G is for Gobs, and H is for Hobbies.
Like the function f
@@RibusPQR Is this like how people argue how to pronounce gif?
@@zmaj12321 HEY, it's prounounced gif
In my Graph Theory class, we had to prove this statement for the special case chi(G)=3 on the final... i can thankfully say that i got it, but unfortunately almost no one (understandably) did
he showed ... in just the right way ... then you have a counterexample. Great explanation!!!!
Amazing, practical explanations & easy to follow. More of her please!
I found the first few minutes of the video to be wonderful exposition. I scrolled down to see who this new(?) guest on Numberphile was. I wasn't surprised. I have been fan of Erica Klarreich's writing on Quanta for some years now.
According to Python, 4^10000 = 398027684033796659235430720619120245370477278049242593871342686565238635974930057042676009749975595510836461137504912702831400376935319143621753470415827025981215282426893498224826615977707595539466961019588699726772279731941315198182787264034852821200164566127930390710398182979935327718016873784821349516406114982916691867361875370024545872140793827277482562824192439237801588697814168520338650090909697535966525032757049430286459482977357373598020450589927318365663076719136934132593126761906696003770385305284570331119691001526584347722012386381881779425549210851696458253943578557699072154639655630793883941961378971846841113804188730258903839103669626086974468150655710480841592465655211805257863007811676888839555017536731758113448656752514158601444051645154665514388431619042396106716755762338728183461369854648923972904427556158821823778729193111453445844216979095435045778144571378954652122396061615147642540250745857228893999875491625014946013839340891326060933901036249999238637827577774666644809734033861619420363936465178730919233673114244563915058438996625834112132967998495576249320462871747777012165543887156255858358784852335060574881876552025685704823768078710818951860741379429242110855644973977420413810373514584504006896392675854997866870818564207239083874324953871276375716101506575153205747363963740749867514682619756775534507006871485887812402927738227576635284174246988540785975240020481266853076127172228024330561550120182008777598230542033702463408316671120886169260934006805799864598636311179787776738608992346063063099659648279663878174074787179237169752957046404584525301384153358344055908219695854852185210739761460551596658211013159915409566145426809737550417578228465835830890294497535463112081537672664056891624345779311524560019984315456142126282898486728345004767873499752683471409587367450593302392307908004590644754012537113320493601682133709318222647489080531644015321391157387178232154126828007760313716872242209614200967522180475716199973689467714010404673961454146466045855232217196687665143147612199151921277432309700460321430381533385245877431330533479476152339364503436322919665631042328740463612565842560411947020174006507893396276103834436233140915025391014386119201176462659556388343058600326710618903683746516577021214276933289179021059956925949717956040857979165914170970056212869933593589268626151996676594370800885093048230687152803213254735594741799076039453057272319884322341883241036382617598401889439130301876975498681736174215711287053447013711596004574803562701388246822510391522419061320663740921321754344166744899588160649291823535983386025904942040724581017615968429577015808090360968544059204594200069304612417366398776831532265596224715750301792207725607932534543693758772262010387360435567635232718343420679693057360004073679493008945813961012439574397373178636054628207647520675194420244271036343729318858430871461978866964772362057290577326080664463129657590249859748544101333842092713653096656066266827446079145590196644643417403723220085696202719321533233027169599734928971588850348415000070034027025298183104148343980297663148971586607903771717880683175436445585810610546882073571556162324659351310326560804448974229349743425637164834242799991427145050899469511954834774847172360693568437689147399455672090773686782511054291185172381917008889957645311339950993044779783607140593766508017935992581357858306525303783231752425242008347844867988333025417249944092118578113687403158162707075154006053416374075765162668533127078605316562826337193606242535290683224423660462222408680300498714149607265550441220738075941633988435051594487256802874182264814425923111193188280632013127802897889605338783089532740877202304122498193625454768343775535498872821099981620497070810489137457106892573248498734243717184800822956334469415666818858073218653977954309023182851723246522042792401461382001601920501284439325214084210736400630884929942272982943613708123011355260915545831043160243523599372006226150289664982113944898886610710824955096724626895416484521819026132177640598691658035986285376355033719094568083122219345722063613609779158338084375331431276527548482566210071347744541292871876134764249704859840950276227627328897424208932988115108907187647698491814375639614313178092528678007370045871748218421786396197284213209022623762734630836006864192414605237248983289006905268988475197599781524158913583701325199090352274252608342971303907669363045656232183978755853064004010895030834921988601355201181158877254807798058635127708445592064519563115094749276606697559529332807221414021024905241788974917755034700510432039890197393691722911126889174394312127254793141624975830429097997705531781908242083922068769027355129212617244130640289994777413026624013157329948333586377955103195844817163822484232700763859290253400376515701986753596890075818544485475785780031843579065754095099970940504640212850809997051128976563880886392410766321449987529690463262182894272302749154535447233331028841215215533602398281107050696017507827602761547816324743297938177204183765821117818869959795031848201322436053103778993541384779857262311465895754085538371969040922420936915076653500310175006188572019017358300979056992161958286882575984331858170857303361269891312794369244896540323192451678830668180455059289743580640736076233561935888109525845803125912388965524166819855977061399043499229843517930169118036812460794615667808961600389778306540324849286501515292799391304510997298128228258006156017389878086272789993321416349205921635696963703558971391123174877353757536774013315034956942784403824181551741629180658414081905650333672638983416786388095026169496605199749691595798835947189777822765198767949699778106683862989103096006505865271003566346191382406011673958404009194852110016915222433459641787170917872140367871023596464051647947388580570774462304347896201676197195521428782313608583714399238092208362933211302942806480175589402387976531080436906856834377344137698180789562645974374155400497754843905032231188252125802180353577510519869570675234892321663406309376
calculated instantly. It's 6021 digits long.
So "a one with 6000 zeroes" was only off by a factor of about 400,000,000,000,000,000,000.
But express that error as a percentage of 4^10000 and it's less than a percent
You mean 4**10000?
You don't need python or similar to write out that number, though - just write it in hexadecimal for instance..
@@brianlane723 ha ha
Man this was an awesome explanation. I put off watching this all day cause I was like "okay, Graph Theory, I'm gonna need to focus for this one." I think that's the first time there's been a numberphile video using the word "tensor" that I actually followed. Thank you!
I really appreciate you making this video with an astonishing explanation. Thank you very much!
Shes a great communicator. Top notch.
Please, talk about new partial proof by Terence Tao and Collatz Conjecture.
i thought i was procrastinating by watching math vids when i'm supposed to be making my project as senior thesis in graphic design but i actually learned something i can apply wow
Congrats on 3.14 million subscribers!
Very nice lecture indeed. Two small remarks:
The graph of a function, as known from school, does fall under the same umbrella as a graph in Graph Theory. Only it is drawn in a different way.
And "tensor product" is not the only name for the product in question, nor even the most common name. Just "product" or "Cartesian product" seem more used.
What a great presenter! She made the math really clear and well-motivated and interesting and fun! :)
Very well explained, master teacher!
22:27 We can safely assume that one's friend is made of at lest one particle of the observable universe. Therefore, nobody has as much friends.
Now, if we speak about imaginary friends, we have to understand how much information the mind can hold. I don't thinks it's that many, but that would be a conjecture.
If you're seeking evidence to support your hypothesis, I can confirm that each of my two friends has more than one elementary particle. Mathematics gets loony.
Christian Baune There is no such thing as the mind.
I had 2^26 imaginary friends when I was younger... (I’m not even joking)
@18:00 You don't even need to look at the combination of the two graphs to find compatible people who were separated. The Job graph by itself had already forced the compatible Teacher and Professor to be different colors, which at least raises the concern when combining two more complex graphs (requiring many more colors) filled with such indirect separations. (I say many more colors because you need room to simplify.)
21:35 So now the next question is: what is the SMALLEST graph that breaks that conjecture? :J See you in the next couple of decades ;)
What a great educator you are, Erica! Great video!
I think one fact is important to note: the reason why this conjecture seems _obviously_ false with the presented example is that for most friend groups, we only have a subgraph of the full product. Obviously there are subgraphs, i.e. graphs where certain nodes are deleted, that can be colored with fewer colors. That's not what the conjecture is about, though.
Penny Lane what?
@@HL-iw1du You'd help me answer your question if you elaborated a bit ;)
@@unvergebeneid I'm guessing you mean that people don't have a friend for every combination of job and hobby in real life, so their intuition tells them that the problem is easier than it actually is . The conjecture does seem obviously false at first glance because, as Erica points out, you're throwing away information that can only help you if you just default to the starting solutions. I quickly realized how difficult it was to actually create a counterexample, however, since you apparently have to make both G and H require at least 5 colors, which means that even the simplest examples you want to try take quite a while to write down (I gave up already, haha).
@@trogdorstrngbd yes. For the problem in the video you will of course have plenty of real life friend groups that will allow everyone to come on the same weekend, i.e. the graph only needing one color. But as you said, that's not what this conjecture is about, so this example will mislead many people which is also reflected in the comments for this video.
@@IlIlllIllIlIIIll Not sure I understand your question. What graphs don't share any edges?
I have gotten into graph theory recently. I like it a lot and It makes neural networks easier to understand. It is pretty complicated if you try to look at the analysis portion of it.
The best conceivable Christmas present. Thank you.
0:40 Just to point out that the confussion for the word graph comes from the shortening of 2 different greek words... Γραφική αναπαρασταση meaning graphical representation is the one used for x, y axis and Γράφος is the one used for the network representation. Englishs words and phrases, as a habbit, have always been shortened for the ease of use but details are lost in the process
I wonder if this is similar to how our brain's neurons makes connections, and then efficiency would be how well it can avoid necessary separations
I gave this as an example to my students as an unsolved problem and it was proven while the class was still meeting!
Is the breakthrough that they finally managed to spell his name correctly?
Shiny Swalot That’s still an unsolved problem.
She actually pronounces it really well. :D
It's a pretty typical finnish heritage last name though. Nothing difficult to spell.
oldinion This is an aspect of social interaction called a “joke”, which is easy to spell, but difficult for some to understand.
Hedetniemi can be spelled right by just copying and pasting but it's obviously tricky to pronounce. Those dang diphthongs!
Numberphile now has 3.14 million subscribers. That's Beautiful.
She explains graphs better than any of my university teachers
How intriguing! Never have heard about this type of "graph" before, but it is so interesting, and so well presented/explained by Ms Klarreich.
"i don't know if there's anyone out there with that many friends..."
right after saying the number is orders of magnitude larger than the total number of particles in the universe :O
Brilliantly explained. I thoroughly enjoyed this video 🙂
Almost 3.14 milion subs.
6.28 is where it's at. xD
Lol
next stop 42 mil
Naveen Dookia get that tau outta here
IT IS
The digits used in sudoku are just symbols. You can use colors, fruits, whatever.
It is great to see science in action.
But how many colors do exist in the observable universe
(Vsauce theme)..
If it ends up being as low as 100.000 it would allow us to perform A LOT of optimizations in many fields, this is fantastic.
Wanted to stab myself in the eye during college advanced math. Now watching math for entertainment. The hell?
Discrete math (which includes things like graph theory) is very different from something like calculus. Discrete is like logic puzzles, and challenging but fascinating. Integral calculus/ differential equations is more procedural like algebra, and easier but boring.
Doing things autonomously instead of being forced makes them more fulfilling. I remember reading books in school and hating them, and then rereading those same books after graduation in my free time. Industrial Society and its Future explains the phenomenon well.
@@letsmakeit110 Exactly. Like forced charity. Utter oxymoron.
@@zoomskiller Unless you live for physics.
Doing math under time pressure and deadlines added unnecessary burden to an otherwise fascinating subject, also the grading system encourages results over learning so there you go.
Brady, thanks to you I had the joy of listening Edward Frenkel's audiobook version of his book Love and Math: The Heart of Hidden Reality, and I've wanted for a while for mathematics to be a bigger part of my life, so thank you for promoting (beyond creating, of course) great popular mathematics content.
She's so good at communicating, I almost forgot she called sudoku pseudo-coup
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.
These dots on the a paper with text fascinates me
Epic
The most amazing thing is that graph theory, number theory, topology, set theory, and calculus are all interconnected.
Odd. My father is a retired math professor who started in topology, and I have a special gravity towards graph theory but have never heard of Het.. Hetde... Hedetniemi’s conjecture. I’ve always known it as the graph coloring problem , and that 3+x (x>=1) colors is the very minimum needed
Hedetniemi's conjecture (now disproven) is that the graph which is the tensor product of two graphs can not be colored with fewer colors than either of the two graphs individually. So it's not really the same as the graph coloring problem.
@@HeadOnAStick Whew. Thanks for the clarification. I thought I was forgetting or worse, was uninformed.
Thanks to Erica for always placing the caps back on the pens!