Wow! Yaroslav Shitov is my teacher in university. Wasn't expecting to see him there

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.

People would be surprised how many things from everyday life directly reduce to a coloring problem.

So the smallest counter-example is between 5 and 4^10000 vertices

She is fantastic at explaining things

She is very clear, more of her please!

14:28 Graphs are always G or H because G stands for Graph and H stands for Hparg >:-)

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.

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.

Hedetniemi is 80 years old and 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.

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..."

man how stoked would you be getting an answer to your conjecture after 50 years

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 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.

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 loved how clear and conscise she was expressing herself!

I really liked how Erica explained this, I felt like I really understood it despite not doing graph theory before!

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...'

Brilliant introduction to graph theory

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?

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.

The auto subtitles are saying "head-at-knee Amy's conjecture" and it's hilarious.

this woman is such a good explainer

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.

Whoelse but numberphile who will discuss really complicated maths mysteries in laymans terms. Thank you!

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.

To be fair, using colours in a sudoku puzzle might be quite useful for children, especially like 4 by 4s and 6 by 6.

Oooh! I never realized until I saw the quanta magazine picture! I have read so many articles by Erica, she's great!

A really great intuitive explanation of tensor graphs! Thanks Erica!

The recommended Numberphile videos about graph theory are a graph theory problem unto themselves.

I would be really impressed if I saw someone solving a sudoku with that color technique

I love these numberphile videos. They really inspire me and make me want to explore even deeper in maths

Subtle Australian states graph

I really appreciate you making this video with an astonishing explanation. Thank you very much!

There's a flaw in the reasoning: Why watch Netflix when you can watch Numberphile?

That explanation though, great teacher! Wish my uni professors were that great at explaining graph theory...

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.

such clarity! Please continue making more videos, Erica.

Amazing, practical explanations & easy to follow. More of her please!

I remember the „Every graph is 4-colorable“ book, one of the largest in the library at the Mathematical Institute where I studied.

This is a really great video. Interesting concept, explained in depth, but in an understandable and engaging way. Erica was fantastic.

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

Erica Klarreich seems to be a wonderful teacher!

Youre channel is one reason I probably attempt to become a math teacher next year😂

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.

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!

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 😇

She is a professor I would like because she writes so beautiful while most professors’ writing are hard to read as hell.

Wow, you connected the dots very well on this one!

Numberphile's logo is π and currently they have 3.14 Million subscribers.......... Coincidence? I think not!

In Polish there is no ambiguity wirh graph and graph. Graph in graph theory is called graf, graph of function is called wykres.

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 am so charmed by all the examples of jobs the professor gives are things related to the university!!

How intriguing! Never have heard about this type of "graph" before, but it is so interesting, and so well presented/explained by Ms Klarreich.

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.

I absolutely didn’t know about graphes being a mathematical object this way, and this is super interesting

This actually made sense, wish had teacher like this explain everything.

One of my favorite numberphile videos ever!

I like the follow up paper disproving it asymptomatically.

Please, talk about new partial proof by Terence Tao and Collatz Conjecture.

What a great educator you are, Erica! Great video!

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.

Welp I have my final exam about graphs and data structures and algorithms in one hour

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.

This was very interesting and also well explained. You opened up a new universe to me. Thank you ❤️

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.

Congrats on 3.14 million subscribers!

According to Python, 4^10000 = 398027684033796659235430720619120245370477278049242593871342686565238635974930057042676009749975595510836461137504912702831400376935319143621753470415827025981215282426893498224826615977707595539466961019588699726772279731941315198182787264034852821200164566127930390710398182979935327718016873784821349516406114982916691867361875370024545872140793827277482562824192439237801588697814168520338650090909697535966525032757049430286459482977357373598020450589927318365663076719136934132593126761906696003770385305284570331119691001526584347722012386381881779425549210851696458253943578557699072154639655630793883941961378971846841113804188730258903839103669626086974468150655710480841592465655211805257863007811676888839555017536731758113448656752514158601444051645154665514388431619042396106716755762338728183461369854648923972904427556158821823778729193111453445844216979095435045778144571378954652122396061615147642540250745857228893999875491625014946013839340891326060933901036249999238637827577774666644809734033861619420363936465178730919233673114244563915058438996625834112132967998495576249320462871747777012165543887156255858358784852335060574881876552025685704823768078710818951860741379429242110855644973977420413810373514584504006896392675854997866870818564207239083874324953871276375716101506575153205747363963740749867514682619756775534507006871485887812402927738227576635284174246988540785975240020481266853076127172228024330561550120182008777598230542033702463408316671120886169260934006805799864598636311179787776738608992346063063099659648279663878174074787179237169752957046404584525301384153358344055908219695854852185210739761460551596658211013159915409566145426809737550417578228465835830890294497535463112081537672664056891624345779311524560019984315456142126282898486728345004767873499752683471409587367450593302392307908004590644754012537113320493601682133709318222647489080531644015321391157387178232154126828007760313716872242209614200967522180475716199973689467714010404673961454146466045855232217196687665143147612199151921277432309700460321430381533385245877431330533479476152339364503436322919665631042328740463612565842560411947020174006507893396276103834436233140915025391014386119201176462659556388343058600326710618903683746516577021214276933289179021059956925949717956040857979165914170970056212869933593589268626151996676594370800885093048230687152803213254735594741799076039453057272319884322341883241036382617598401889439130301876975498681736174215711287053447013711596004574803562701388246822510391522419061320663740921321754344166744899588160649291823535983386025904942040724581017615968429577015808090360968544059204594200069304612417366398776831532265596224715750301792207725607932534543693758772262010387360435567635232718343420679693057360004073679493008945813961012439574397373178636054628207647520675194420244271036343729318858430871461978866964772362057290577326080664463129657590249859748544101333842092713653096656066266827446079145590196644643417403723220085696202719321533233027169599734928971588850348415000070034027025298183104148343980297663148971586607903771717880683175436445585810610546882073571556162324659351310326560804448974229349743425637164834242799991427145050899469511954834774847172360693568437689147399455672090773686782511054291185172381917008889957645311339950993044779783607140593766508017935992581357858306525303783231752425242008347844867988333025417249944092118578113687403158162707075154006053416374075765162668533127078605316562826337193606242535290683224423660462222408680300498714149607265550441220738075941633988435051594487256802874182264814425923111193188280632013127802897889605338783089532740877202304122498193625454768343775535498872821099981620497070810489137457106892573248498734243717184800822956334469415666818858073218653977954309023182851723246522042792401461382001601920501284439325214084210736400630884929942272982943613708123011355260915545831043160243523599372006226150289664982113944898886610710824955096724626895416484521819026132177640598691658035986285376355033719094568083122219345722063613609779158338084375331431276527548482566210071347744541292871876134764249704859840950276227627328897424208932988115108907187647698491814375639614313178092528678007370045871748218421786396197284213209022623762734630836006864192414605237248983289006905268988475197599781524158913583701325199090352274252608342971303907669363045656232183978755853064004010895030834921988601355201181158877254807798058635127708445592064519563115094749276606697559529332807221414021024905241788974917755034700510432039890197393691722911126889174394312127254793141624975830429097997705531781908242083922068769027355129212617244130640289994777413026624013157329948333586377955103195844817163822484232700763859290253400376515701986753596890075818544485475785780031843579065754095099970940504640212850809997051128976563880886392410766321449987529690463262182894272302749154535447233331028841215215533602398281107050696017507827602761547816324743297938177204183765821117818869959795031848201322436053103778993541384779857262311465895754085538371969040922420936915076653500310175006188572019017358300979056992161958286882575984331858170857303361269891312794369244896540323192451678830668180455059289743580640736076233561935888109525845803125912388965524166819855977061399043499229843517930169118036812460794615667808961600389778306540324849286501515292799391304510997298128228258006156017389878086272789993321416349205921635696963703558971391123174877353757536774013315034956942784403824181551741629180658414081905650333672638983416786388095026169496605199749691595798835947189777822765198767949699778106683862989103096006505865271003566346191382406011673958404009194852110016915222433459641787170917872140367871023596464051647947388580570774462304347896201676197195521428782313608583714399238092208362933211302942806480175589402387976531080436906856834377344137698180789562645974374155400497754843905032231188252125802180353577510519869570675234892321663406309376 calculated instantly. It's 6021 digits long.

Thanks for getting this video out so quickly!

Brilliantly explained. I thoroughly enjoyed this video 🙂

Maybe its G & H because G is for graph and H is the next letter!

Erica is a great presenter! Excellent video.

Great explanation and so easy to follow. Thank You

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.

Almost 3.14 milion subs.

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.

Thank you Erika. Easily understood and well explained.

Ok. So this is kind of breakthrough I've been long waiting for? Starting from tomorrow, I'm gonna use it in my daily work for now on.

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

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 ;)

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

I listened to Humble Pi on Audible. I had quite a nice time with it while driving to work and back home for a few days

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.

*Look at this graph* 🎶

I loved the video. Very captivating. Thanks for that.

Superb introduction to graph theory! Thank you!

What a great presenter! She made the math really clear and well-motivated and interesting and fun! :)

"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

That's genius, taking a complex subject and presenting it in a manner accessible to non-experts.

Studying CS I learnt quite a bit about graphs and it relates to many problems and applications.

and people joke about math having no practical applications. PFFT! This is exactly the kind of thing that people planning seating arrangements at weddings need lol. And now I want to learn more about graph theory [after I teach myself calculus... after I graduate college, cuz I'm pressed for time and energy]

She's so good at communicating, I almost forgot she called sudoku pseudo-coup

Woah! I just did a project on this for my undergraduate graph theory course. Was not expecting to see this here at all. I couldn't get through the whole paper though. I only wound up talking about exponential graphs and a couple things about tensor products.

Thanks to Erica for always placing the caps back on the pens!

Wanted to stab myself in the eye during college advanced math. Now watching math for entertainment. The hell?

Is the breakthrough that they finally managed to spell his name correctly?

@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.)

One of the few things I really like about math terms in Spanish is that we do can easily distinguish between the two concepts: gráficos o gráficas (for XY plots) and grafos (dots and lines)