Why complete chaos is impossible || Ramsey Theory
Вставка
- Опубліковано 13 чер 2024
- 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 - Наука та технологія
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.
Oh quite right, thank for catching that!
so while the universe can't be chaotic in theory, humans can induce chaos in practice
@@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
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.
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.
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.
A classic example is the 'face' on Mars.
Well, that explains the humongous structure called string theory.
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
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!
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!
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.
Such a cool guy!
With a middle name like "Plumpton," he was bound to do great things . 🤓
What are the prequistes for functional analysis and quantum physics
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.
Ya that’s a really cool one!
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.
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
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.
hmm, this video would be complete if you mentioned one of the strangest side products of ramsey theory: graham's number.
That's true! I actually did a special video on graham's number once so it didn't make the cut here:D
@@DrTrefor lots of people complained about the audio quality though
reminds me how much I missed getting into Ramsey theory in grad work. Really enjoyed your work!
Glad you enjoyed it!
"Why complete chaos is impossible"
You haven't seen my apartment.
This has a strong indicaton. If the Universe is large enough, life is inevitable. No creator is needed.
it's all fun and games until the aliens ask for the 6th Ramsey Number
:D
Hi Dr. Bazett!
Very cool!
3:49 haha caughtcha! Bro messed up his voice line so they re-recorded the word "o's" later lol
Lmao: ya I said “exes and odds”. It was weird:D
@@DrTreforLol, x's and odds, evens and o's, it's all relative right?
So simple yet so easy to overlook.
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.
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.
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.
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.
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.
prac.im.pwr.edu.pl/~zak/Ramsey_theory.pdf
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.
Brilliant video. I am curious on practical applications for the math.
This looks like something that could pop up in physics
statistical mechanics?
graham's number flashbacks from the beginning
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.
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
@@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?
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.
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?
At 8:00 The correct phrasing of the theorem should be "that every colouring of the [...] cube *by c colours*"
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
Where can i find details on the "strategy switching argument" mentioned at 10:16?
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?
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.
How VdW theorem will be related to prime numbers? Is that mean that will be some sequence which points primes?
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
What is the OEIS sequence for W(L, 2)?
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?
I was expecting a connection to chaos theory at some point, and it just never came.
Take a drink every time he says “combinatorical”.
But seriously, great video! Thank you.
Lol:D
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?
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.
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.
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
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.
@@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.
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?
Good catch!
How does this square with entropy in thermodynamics?
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....
That’s a great suggestion actually
We actually played 3x3x3x3 tick-tack-toe at university.
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
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.
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.
The only Ramsey theory that I know is the lamp is still raw
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.
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.
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?
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!
I love the T shirt. Where can I get it?
I have a merch link in the video description!
@@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
Now what if one of the lines randomly turned yellow.
Surprised you mentioned Graham's #, but didn't elaborate. It too is an (hilariously large) upper bound of some Ramsey theory problem.
Graham gave solution to a cube it's can be huge numbers unimaginable at higher dimensions of possibilities
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
ComSci student here 🙋♂️
Entropy: defeated.
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.
Ya really cool area of math imo
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
Hey thank you so much!
@@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
where is one
4:01 and 4:08 have different alignment... help😭
Couldn't help but notice the shirt
Complete chaos is impossible as every completed Spin a new overspin is formed.
It depends on the definition of chaos but I don’t see y’d ‘dnt b possible
7:57 Can’t you just write it as {x, 1, 4-x}?
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.
Just /root
It’s solved now ? With recent paper probably yes
Im early
Love it!
I'm sorry but combinatorial has only one c. Since we are being pedants.
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
quitter talk. Can't "yet" @@DrTrefor
What if those people know each other, but they also hate each other?
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.
This isn't even related to chaos. Clickbait.
You might be thinking of notions of chaos from dynamical systems. This is absolutely a different field, with different interpretations
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.
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.
@@pseudolullus physics that tells us that there is no overarching continuum that connects everything (like real numbers assume)
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.
the fact that you think about this kind of stuff this deeply shows you need help.
Super pedantic point, there's no second 'c' in combinatorial. It is not pronounced as combinactorical.