Why complete chaos is impossible || Ramsey Theory

Подписаться 411 тыс.

Просмотров 39 тыс.

50% 1

Keep exploring at ► brilliant.org/TreforBazett. Get started for free for 30 days - and the first 200 people get 20% off an annual premium subscription!
Normal tic-tac-toe can always be drawn. But what if it lives in high dimensions? It turns out that no matter how large a tic-tac-toe board you have or how many players want to play, there always is a dimension long enough that guarantees the 1st player will always win. The theorem behind this, Hales-Jewett, is part of a family of theorems in Ramsey theory that show how lower level structures (like straight lines of the same colour) are always going to occur if the dimension is large enough. That is, you can't have a system that is totally without order. In this video we explore these tic-tac-toe generalizations, the Van Der Waerden theorem and sketch it's proof.
Reference: This undergrad level book introducing Ramsey Theory has lots more detail on all the theorems and more: www.sfu.ca/~vjungic/RamseyNot...
0:00 Friends and Strangers Theorem
2:56 What is Ramsey Theory?
3:36 High dimensional Tic-Tac-Toe
7:58 Hales-Jewett Theorem
10:37 Van der Waerden's theorem
14:42 Proof sketch of Van der Waerden's theorem
21:23 Summary
21:57 Brilliant.org/TreforBazett
Check out my MATH MERCH line in collaboration with Beautiful Equations
►beautifulequations.net/pages/...
COURSE PLAYLISTS:
►DISCRETE MATH: • Discrete Math (Full Co...
►LINEAR ALGEBRA: • Linear Algebra (Full C...
►CALCULUS I: • Calculus I (Limits, De...
► CALCULUS II: • Calculus II (Integrati...
►MULTIVARIABLE CALCULUS (Calc III): • Calculus III: Multivar...
►VECTOR CALCULUS (Calc IV) • Calculus IV: Vector Ca...
►DIFFERENTIAL EQUATIONS: • Ordinary Differential ...
►LAPLACE TRANSFORM: • Laplace Transforms and...
►GAME THEORY: • Game Theory
OTHER PLAYLISTS:
► Learning Math Series
• 5 Tips To Make Math Pr...
►Cool Math Series:
• Cool Math Series
BECOME A MEMBER:
►Join: / @drtrefor
MATH BOOKS I LOVE (affilliate link):
► www.amazon.com/shop/treforbazett
SOCIALS:
►Twitter (math based): / treforbazett
►Instagram (photography based): / treforphotography

Наука

Опубликовано:

10 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 121

@VascovanZeller 10 месяцев назад

There's a minor mistake in the 3d tic tac toe cube drawn at 7:58, where one line 32x is displayed as 23x instead. Right? I'm not pointing this out to be petty, rather in case someone was confused like me.

@DrTrefor 10 месяцев назад

Oh quite right, thank for catching that!

@alquinn8576 10 месяцев назад

so while the universe can't be chaotic in theory, humans can induce chaos in practice

@youngxsavage 8 месяцев назад

@@alquinn8576both can b chaotic & kinda are sometimes, even tho living moving things like us can influence the chaos of certain things. But as the universe is also determined by powers, & things seem might evolving rather slow, it’s kinda not as chaotic as it could be without e.g. gravity etc

@allanjmcpherson 10 месяцев назад

The fundamental insight that for a sufficiently large structure, ordered substructures are guaranteed makes me think of the importance of looking at data only once a hypothesis is set. If you just look at a large data set and look for any correlations, you'll almost certainly find some. That doesn't mean they're in any way significant. They're almost certain to exist simply because there's so much data.

@DrTrefor 10 месяцев назад

Ya that's a good metaphor. Reminds me of the 999999 that appears in the first 1000 digits of pi, seems way too "ordered", but it is basically meaningless.

@andrewharrison8436 10 месяцев назад

Absolutely! Look at a small data set, create a hypothesis, throw away that data set and do proper research on a bigger independent data set. You are right, Ramsey theory is a proof that sweating the data will always give significant results that are mostly just coincidence.

@mkj1887 10 месяцев назад

A classic example is the 'face' on Mars.

@afriedrich1452 10 месяцев назад

Well, that explains the humongous structure called string theory.

@wyboo2019 5 месяцев назад

i think its similar to this but also different in a significant way. finding correlations in very large sets of data is because even if some event has a 10^(-6) chance of happening in one instant, you'll still find on average 1 event when looking at 10^6 instances. ramsey theory isn't probabilistic like this. like, the fact that a monochromatic triangle is guaranteed to exist in a complete graph of at least 6 vertices isn't due to to fact that its so unlikely to include a monochromatic triangle in your complete graph that it doesn't show up until you have more vertices, but is rather a fundamental property of complete graphs with more than 6 vertices. it's not a case of the "law of truly large numbers," i mean

@MushookieMan 10 месяцев назад

These videos are far better than Numberphile for getting an introductory understanding of a topic. Those speakers are great, but the videos are in an interview format and unscripted. Plus a picture is worth a thousand words!

@DrTrefor 10 месяцев назад

I actually really appreciate this comment! I definitely sometimes cover topics that have also been covered by numberphile, but my goal is often to use the graphics and editing to make the theorems as accessible as possible to the widest audience. Don't know if I hit that goal, but nevertheless appreciate it!

@DumblyDorr 10 месяцев назад

Franklin Plumpton Ramsey is an under-appreciated giant - in his all-too-short life, he made major contributions to several areas of mathematics and philosophy. What an amazing mind.

@DrTrefor 10 месяцев назад

Such a cool guy!

@madelinewhitney832 8 месяцев назад

With a middle name like "Plumpton," he was bound to do great things . 🤓

@davidaugustyn9234 4 месяца назад

What are the prequistes for functional analysis and quantum physics

@SuperAnatolli 10 месяцев назад

"Why complete chaos is impossible" You haven't seen my apartment.

@Ninja20704 10 месяцев назад

Another famous problem I remember from numberphile is that 7825 is the smallest number N that it is impossible to colour the numbers {1, 2, … , N} in 2 colours such that there is no pythagorean triple in the same colour. However, the general statement about n colours is still only a conjecture and hasn’t been proven. The higher dimension TTT also reminded me about the problem about Graham’s number which is also about colouring lines in higher dimensional cubes. Great video.

@DrTrefor 10 месяцев назад

Ya that’s a really cool one!

@wyboo2019 10 месяцев назад

it's all fun and games until the aliens ask for the 6th Ramsey Number

@DrTrefor 10 месяцев назад

@johnchessant3012 10 месяцев назад

This is really cool! That proof of Van der Waerden's theorem is clever, and so much more enlightening than brute force. Quick correction at 19:33, the gaps in those arithmetic progressions should be 5*(r_2 - r_1) and 5*(r_2 - r_1) + 2. I think we can easily optimize the 325 number a little bit by considering only the row colorings that don't already have an arithmetic progression. I count 14 out of 32 (00100, 00101, 00110, 01001, 01011, 01100, 01101 and their inverses), so our improved bound is 5*(2*14 + 1) = 145.

@DrTrefor 10 месяцев назад

Oh thank you, of course. And yes, often these (highly inefficient) proofs can get a bit more efficient with a number of tricks while still being quite far from their lower bounds

@danielyuan9862 10 месяцев назад

We can also have our rows overlap by at most 2 numbers, and since a number is counted at most twice, any arithmetic progression with the same color can't refer to the same number 3 times. So that would reduce it to 3*(2*14+1)+2=89.

@weishanlei8682 10 месяцев назад

I have some comments. First, the meaning of "chaos" is not clear here. Traditionally, definition of chaos should be that the governing equations are known for the dynamical system but its evolution is sensitive to the initial condition. Second, Dr. Bazett mixes the concept of being "disordered" and "chaotic". in fact, , to a large scale compared to the visualization scale of the system, a chaotic state could be an ordered structure itself. Last, It is a well known fact that a chaotic state in the continuous-time dynamical system could be more easily to achieved when the system has large dimension, not low dimension, unless your dynamical system is discrete in time.

@DrTrefor 10 месяцев назад

I don’t necessarily disagree, but “chaos” here is meant very metaphorically (and I’m hardly alone here, see this section title of this text on Ramsey theory: www.sfu.ca/~vjungic/RamseyNotes/sec_Intro.html). The precise meaning of the theorems is hopefully well explained and not intended to match up with notions of chaos from dynamical systems.

@CubicPostcode Месяц назад

prac.im.pwr.edu.pl/~zak/Ramsey_theory.pdf

@lumi2030 10 месяцев назад

hmm, this video would be complete if you mentioned one of the strangest side products of ramsey theory: graham's number.

@DrTrefor 10 месяцев назад

That's true! I actually did a special video on graham's number once so it didn't make the cut here:D

@lumi2030 10 месяцев назад

@@DrTrefor lots of people complained about the audio quality though

@aarong2374 10 месяцев назад

reminds me how much I missed getting into Ramsey theory in grad work. Really enjoyed your work!

@DrTrefor 10 месяцев назад

Glad you enjoyed it!

@General12th 10 месяцев назад

Hi Dr. Bazett! Very cool!

@Brambrew 10 месяцев назад

3:49 haha caughtcha! Bro messed up his voice line so they re-recorded the word "o's" later lol

@DrTrefor 10 месяцев назад

Lmao: ya I said “exes and odds”. It was weird:D

@Brambrew 10 месяцев назад

@@DrTreforLol, x's and odds, evens and o's, it's all relative right?

@shardator 10 месяцев назад

This has a strong indicaton. If the Universe is large enough, life is inevitable. No creator is needed.

@andrewharrison8436 10 месяцев назад

I have a 4*4*4 noughts and crosses board. Strategically interesting. I think that the first player can force a win. That is very different from a draw being impossible which would need more dimensions than my mind can cope with.

@DrTrefor 10 месяцев назад

Ya in general you need way less dimensions to ensure a winning strategy by force than you do that every game ends up in a win.

@ChalkyWhiteChalkyWhite 9 месяцев назад

So simple yet so easy to overlook.

@GeoffryGifari 10 месяцев назад

This looks like something that could pop up in physics statistical mechanics?

@andrewdickson4753 10 месяцев назад

Found a cute almost-proof that W(3, 2) (i+1, j+1, k+1), you'd have a three in a row if (0, 0, 0), (1, 1, 1) and (2, 2, 2) have the same color. Incrementing the coordinates is the same as adding a constant value to the cell index, so a three in a row implies an arithmetic sequence of length three within the indices. But we were told at the start of the video that a 3x3x3 cube must have a three in a row, so there must be an arithmetic sequence in the 81 indices.

@UliTroyo Месяц назад

I make it halfway through this video and then I noticed the hippotenuse shirt. Now I have to go back about half a minute, when I started chuckling to myself. It's so goofy! Because it's on the slant and stylized without legs, it looks like it's sliding. I think I have to buy it.

@rodbeaudry1660 8 месяцев назад

Brilliant video. I am curious on practical applications for the math.

@ChrisContin 10 месяцев назад

Random is possible, for example conceal the identities of the people from each other. They may or may not know each other; a finite group of all chaos- no certain relationships.

@GeoffryGifari 10 месяцев назад

related to your example of van der waerden's theorem: if complete chaos is impossible in a string of digits, what if we pick something as legendarily "random" as the digits of Pi?

@thesecondderivative8967 10 месяцев назад

Fascinating... Ramsey's theorem reminds me of this statement I heard. It was as follows: A large enough number of monkeys with typewriters would generate create a script with the same literacy as Shakespeare

@xClairy 10 месяцев назад

So basically to put the unbelievable idea more intuitively it's somewhat equivalent to given a infinite number of possibilities you are guaranteed to find some semblance of a thing that's within the scope of the possibilities and this illustrate the min possibilities required of that something to exist within the scope

@AAA-tc1uh 9 месяцев назад

At 8:00 The correct phrasing of the theorem should be "that every colouring of the [...] cube *by c colours*"

@rauljvila 10 месяцев назад

I enjoyed the video, thanks! I just missed the explicit acknowledgement that only examples with integers or discrete values are mentioned. I was left wondering whether this also applies to examples with real numbers and continuous values.

@DrTrefor 10 месяцев назад

Oh true, yes Ramsey theory does tend to live within the world of discrete mathematics. There are notions of, say, fractional dimensions, that are facing tint but not the domain of Ramsey theory as far as I know

@rauljvila 10 месяцев назад

@@DrTrefor I know the question probably doesn't make sense but, given the title of the video, I can't help but wonder: is complete chaos possible with real numbers?

@jrkirby93 10 месяцев назад

I was expecting a connection to chaos theory at some point, and it just never came.

@Person-ef4xj 10 месяцев назад

4:54 there's actually multiple lines of 3 in a row for x. x also has other diagonals and a trigonal line of 3 in a row.

@PatrickDeLaGarza 7 месяцев назад

Where can i find details on the "strategy switching argument" mentioned at 10:16?

@terrym2007 9 месяцев назад

How about the unsolvability of the quintic. It seams that the more roots involved, the less likely it is to have all of the roots to be expressed in a single form. Similar idea?

@SgtSupaman 10 месяцев назад

In your 4D layout of tic-tac-toe, I have to disagree with the three that you choose as being "in a row". In tic-tac-toe, you can only get three in a row via adjacent spaces or one away from adjacent (aka diagonal). Using the space in the bottom left of the screen as the origin and using the format (w,x,y,z) for the coordinates, you have highlighted (0,0,0,0), (1, 1, 0, 1), and (2, 2, 0, 2). For a single move from one space to an adjacent space, only one coordinate could change. For one away from adjacent (aka diagonal), two coordinates would change. But here, three coordinates have changed, meaning that it exceeds the diagonal. It may visually look like a diagonal move, but you are forgetting the extra dimension involved. Even in 3D tic-tac-toe, you can't actually get three in a row from one corner to the opposite corner of the cube through the middle, since those spaces aren't one away from adjacent (aka diagonal) to each other. Your 4D example does have additional three-in-a-rows, but the example you picked isn't really one of them. If you had just highlighted the same bottom left corner of all the cubes (each of them being an x), that would have been a legitimate example.

@DrTrefor 10 месяцев назад

I guess this is just a debate about what we allow in 4d, and I’m asserting a definition compatible with the theorem, but with a slightly different definition we might have to tweak the theorem. It doesn’t really matter, the definitions are all related enough the big idea holds.

@GeoffryGifari 10 месяцев назад

If we're talking about general structures, what counts as "orderly" and "chaotic"? If we have an alternating black-and-white grid (as in chess) a diagonal line (bishop) or straight line (rook) look orderly while an L-shape (knight) looks more chaotic. But in the rules of chess, the L-shape counts as a unit of structure in and of itself... How wonky and complicated should a "structure" be to count as chaotic?

@identityelement7729 10 месяцев назад

What is the OEIS sequence for W(L, 2)?

@romanvolotov 10 месяцев назад

graham's number flashbacks from the beginning

@robshaw2639 10 месяцев назад

I find it interesting that the complexity of Graph Isomorphism is still unknown... The fact that no one has found either a reduction from an NP-hard problem, or a polynomial algorithm, puts it in very rare company like factoring an integer... could there be a connection? In any case, a think a video on Graph Isomorphism could be a hit....

@DrTrefor 10 месяцев назад

That’s a great suggestion actually

@orisphera 10 месяцев назад

4:10 X can easily force a win for themselves if you add the lines consisting of an angle tile and the two non-adjacent edge tiles

@DGronki 10 месяцев назад

How VdW theorem will be related to prime numbers? Is that mean that will be some sequence which points primes?

@coffeeconfessor4747 10 месяцев назад

It must be awesome to be one of your students if you start to explain a theorem with visuals... instead of going straight to abstract information... I really wish I'd have had a professor like you in some of my theory classes... I had to make my own visuals to understand groups... dice were helpful..lol

@DrTrefor 10 месяцев назад

Ya I'm a big fan of leading with visuals & story. The precise formulas and technical details are important, but you gotta hook the students first. This is probably the biggest lesson I've taken from youtube back to my own teaching.

@coffeeconfessor4747 10 месяцев назад

@@DrTrefor When I was tutoring other students in classes, I'd find every day visuals to cement their learning. It helps them grasp a concept if you can show a person a physical object they can hold and manipulate. I am a kinetic/visual learner, so I've learned how to make theoretical mathematics "crunchy" or tactile in real terms. Trying to explain to a professor that the way they teach has the mental texutre of pudding when they ask why I started to make connections to physical things and theoretical concepts can be awkward. However, they always asked and seemed willing to try anything to make a class more engaging.

@carterthaxton 10 месяцев назад

Take a drink every time he says “combinatorical”. But seriously, great video! Thank you.

@DrTrefor 10 месяцев назад

Lol:D

@avrahamlashansky115 8 месяцев назад

So can you use Ramsey's theory to make sense of "random" irrational numbers like pi? Meaning that if we look at pi to enough numbers after the dot a sequence will emerge?

@Dr.Harvey 8 месяцев назад

We actually played 3x3x3x3 tick-tack-toe at university.

@MuonRay 10 месяцев назад

Unless you are using the word "chaos" by its meaning in contemporary parlance then fair enough but I'm not sure how chaos in dynamical systems terms is impossible by combinatorics of increasing dimension when the system is not in the first place a continuously evolving one in time. At best the whole graph-subgraph structure thing could be discrete in time but its not really shown here.

@DrTrefor 10 месяцев назад

Indeed, this is a rather different domain than dynamical systems and not meant to overlap with the precise notions there at all. Instead the use here is more colloquial about an absence of order, so for instance in the tic tac toe there is always going to be that "order" of a straight line passing through the space.

@efi3825 10 месяцев назад

Not a big deal, but around 6:30 there is a little index mistake. All of the numbers in the rightmost squares should start with a 3, right?

@DrTrefor 10 месяцев назад

Good catch!

@nicholashung7871 8 месяцев назад

The only Ramsey theory that I know is the lamp is still raw

@SystemsMedicine 10 месяцев назад

I wonder if Ramsey theory has anything for winnability of chess or variations of chess? [ It seems between Ramsey theory and Clifford algebras, there ought to be some, if minor, results… I’ll call it Clansey theory.

@JohnVKaravitis 10 месяцев назад

How does this square with entropy in thermodynamics?

@walerianrakieta4685 3 месяца назад

12:05 gaps : 4 "this is an arithmetic sequence of..." length : 3 12:20 "this is an arithmetic sequence of..." length : 3 gaps : 4 i think there is something wrong.

@huckthatdish 10 месяцев назад

Interesting that given the massive number of possible chess moves, our best guess right now is that chess with perfect play is a draw. Obviously this is far from proven, but top level engine play certainly seems to suggest that as play gets better draws become the most likely outcome and it seems like the most likely guess that perfectly played chess is a draw not a forced win

@pierrecurie 10 месяцев назад

Surprised you mentioned Graham's #, but didn't elaborate. It too is an (hilariously large) upper bound of some Ramsey theory problem.

@IsaacHarvison-mt5xt 10 месяцев назад

Graham gave solution to a cube it's can be huge numbers unimaginable at higher dimensions of possibilities

@roger7341 10 месяцев назад

What if some people don't know if they know or don't know some other people? Then that leaves some lines dotted and maybe no blue and no red triangle. So does the Ramsey Theory include fuzzy logic?

@DrTrefor 10 месяцев назад

I suppose we could imagine that a dotted line was like a third colour, in which case there are versions of this theorem for any number of colours, you just need more people!

@alasanof 10 месяцев назад

Now what if one of the lines randomly turned yellow.

@sahasananth987 10 месяцев назад

I love the T shirt. Where can I get it?

@DrTrefor 10 месяцев назад

I have a merch link in the video description!

@sahasananth987 10 месяцев назад

@@DrTrefor OMG I love your work thank you for teaching me latex it is now my favorite way to write any document. Thank you will check it out and buy the T shirt

@Priceygames 5 месяцев назад

ComSci student here 🙋‍♂️

@lincolnuland5443 Месяц назад

Entropy: defeated.

@dickybannister5192 10 месяцев назад

nice video thanks. ramsey theory is underrated IMHO. so much nice stuff out there. so is tic-tac-toe. games in general. a problem like "prove can you place 5 x's and 4 o's into a 3x3 grid so that no 3 columns or rows of either of the 3-diagonals all have the same shape" changes from one of just presenting an example, to a game with at most 3 rules (dont lose on the next move, always get nearer to winning by doubling on an unblocked row/col/diag where possible, always block as many row/cols/diags as possible) wherein you can generate the example up to symmetry. "proofs as games" by Pudlak is a great paper.

@DrTrefor 10 месяцев назад

Ya really cool area of math imo

@vootanical5512 8 месяцев назад

where is one

@obiobiero6498 6 месяцев назад

Couldn't help but notice the shirt

@loganhodgsn 10 месяцев назад

4:01 and 4:08 have different alignment... help😭

@youngxsavage 8 месяцев назад

It depends on the definition of chaos but I don’t see y’d ‘dnt b possible

@disonaroaurelo 4 месяца назад

Complete chaos is impossible as every completed Spin a new overspin is formed.

@MS-cs7gt 4 месяца назад

It’s solved now ? With recent paper probably yes

@Aodhan2717 10 месяцев назад

7:57 Can’t you just write it as {x, 1, 4-x}?

@DrTrefor 10 месяцев назад

Oh absolutely, it is just this isn’t satisfying the specific definition of “combinatorial” line used in the theorem. But this is just a technicality.

@youngxsavage 8 месяцев назад

Just /root

@billsix 10 месяцев назад

Hey my cross product video will be the greatest of all time, I've already figured out how to explain greens theorem, but I'm still trying to figure out Stokes theorem. Either way, although I'm the best, thank you for what you do player

@DrTrefor 10 месяцев назад

Hey thank you so much!

@billsix 10 месяцев назад

@@DrTreforno problem dude I'm just not convinced that the cross product follows the right hand rule, I think it follows the left hand roll

@twobob 10 месяцев назад

I'm sorry but combinatorial has only one c. Since we are being pedants.

@DrTrefor 10 месяцев назад

ha, yes, this is one of those cognitive errors that has been implanted in my brain for like 15 years and I can't get it out:D

@twobob 10 месяцев назад

quitter talk. Can't "yet" @@DrTrefor

@1994savvas 8 месяцев назад

What if those people know each other, but they also hate each other?

@ShanBojack 10 месяцев назад

Im early

@DrTrefor 10 месяцев назад

Love it!

@youngxsavage 8 месяцев назад

So is this just saying that if the options are just 2 like true or false, there are therefore also fast at least 2 e.g.~ppl~ who then have true or false in common which makes it more structured? Tbh I don’t recognize a valuable information out of this it’s very obvious & doesn’t prove less chaos afais.

@Laff700 10 месяцев назад

This isn't even related to chaos. Clickbait.

@DrTrefor 10 месяцев назад

You might be thinking of notions of chaos from dynamical systems. This is absolutely a different field, with different interpretations

@ashnur 10 месяцев назад

Only in mathematics. In real life it's just one wrong step or word away. I really wish mathematicians overall would revolutionize their outdated narratives so that it fits 21st century physics and metaphysics properly instead of confusing everyone.

@pseudolullus 10 месяцев назад

Which kind of 21st century physics? I mean, it's true that chaos in physics definitely isn't the same thing as disorder but it's being used in an informal way.

@ashnur 10 месяцев назад

@@pseudolullus physics that tells us that there is no overarching continuum that connects everything (like real numbers assume)

@oblivi8games808 10 месяцев назад

Mathematicians need not concern themselves with the thoughts of Physicists. Mathematics does not care about what is true in our Universe. It is far more fundamental than that. While Physics is derived from experimentation and observation of the real world, Mathematics is derived from pure logic and is independent of questions like whether or not reality exists or things in the real world are continuous or discrete.