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.
@@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.
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!
One important thing about Ramsey Theory is even though we're sure that structure will emerge eventually, we're not guaranteed that the point where it emerges will be small. Some famous large numbers like TREE(3) also came out of proofs related to Ramsey Theory. Similar to Van der Waerden's theorem, in TREE function's case it's about sequences of trees with coloured nodes where you're trying to avoid a certain relation for as long as you can, but you're guaranteed it will show up eventually.
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.
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.
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.
Just playing along here trying to work out the answer myself. 1:25 there will always be a triangle of people that know or don't know each other. Why? : Skipping some other approaches I had that didn't work out. Here is why I think. First just looking at 1 person. For them to not be part of an triangle the people they know must not know each other. And the people they don't know must be familiar with each other. Because if you know 2 people or more and they know each other then you got an triangle of yourself and the two others. Same in reverse. But if you are with a group of 5 this is an issue. Once you have any group of 3 or more people that know you (or not know you, as long as they all are the same) they will form a triangle amongst themselves. Because if they know you in order for you not to be in an triangle they may not know each other. Meaning the 3 form a triangle of not knowing each other. And because you are amongst 5 other people that you have to devide by 2 (knowing or not knowing) you will always have 1 group of 3 At 4 (5 including yourself) this isn't an issue yet. You can know 2 people and not know the other 2. The 2 you know don't know each other and the 2 you don't do know each other. This does leave open the question of can those 2 groups of 2 be linked to each other without making a traingle. (Because apparently I want a solution that works for every size group? Idk just a stream of thought here. We'll see where we end). We know that each of the 2 in each group both know and not know someone right now. If they know you then they don't know the other in the group of those that know you. But for the group that doesn't know you they do know each other. So in order for their not to be an triangle you would have to know one and not know the other of the opposite group. (I hope people can still follow this cause im not sure how well I'm writing this down xD maybe ill try make a simple rule at the end). The connections between the two groups themselves should not have the ability to create a triangle containing yourself because you know one group and you don't know the other. So no matter the connection between them there is always a line that is the opposite in the triangle between you and the two groups. So 4 is possible to have no triangles. I think ill skip 3,2 and 1 😅 So how would I formulise this to make it work for any size of group. Well I think 4 (5 including yourself) may be the last group this works with. Like i said earlier: TlDR; if one person has a group of either 3 or more people that they do know or don't know. Then it is not possible for there not to be a traingle (in a graph with just 2 states of connections at least) ... So what if there where more? Lets call them colors because that's easier then "know or don't know". 2 colors has a max size of 5 points before things break down. But a 3 color can expand things. In the 6 point graph you can break the traingle of 3 you know by making one connection diffrent. So first they where all red connections and now we replace one of them with green (a person you may know? Idk xD) so to summarise a 6 point graph from the perspective of 1 point has 2 groups, blue and red. In this case you know 3 blue and 2 red. The 3 blue amongst themselves share red connections but because that would make a traingle we made 1 green. The red group has 1 blue connection amongst themselves so no alterations necessary. Now the connections between the 2 groups. Again like before we don't have to keep in mind our reverence point as making a traingle there is impossible between the 2 groups. So let's ignore it's existence. We are now back at a 5 point graph only this time some lines have been coloured already. Taking the perspective of 1 of the red points i have to connect to the 4 other points. One point we are already connecteded to. The other red point using a blue line. And the other 3 are still open. If we had 2 colors to work with it would be an issue because the 3 blue points where already connected to each other. But with one of them being green we can pretend that the green line is red. Given that we are ignoring the original reference point anyway this should be fine (i think? I hope that this will help later when generalising the solution) back to the red points perspective. 4 other points to connect to. Lets devide them by 2 again to make sure there will be no triangle containing it self. Lets first do the red connections. in order to prevent a triangle we have to make sure two point we connect to are part of the blue points, and because we decided that green now acts as red we have to make sure not to connect both red lines to a blue point connected to green. There are but 3 blue points though so one of them has to but that is fine. This leaves 1 point left to connect with the blue line and now the first red point is hooked up. The second red point also has to be connected to the blue points and same thing here, we don't want to connect both red lines to green. We just swap around which end of the green line we use here. Leaving the other end for a blue line. And that leaves us fully connected for a graph of 6 points with 3 colors. I think that as long as you can manage to connect 1 point to the graph without making traingles with its self there should be a solution. So, and im not going to work this one out fully I hope xD, if you take a graph of say 100 points. To big for my head lol. You extract 1 point to make the center and split the rest up into 2 groups. 1 blue. 1 red. Amongst that group any direct connection has to be a different color in order to prevent a traingle from forming. This becomes an issue as soon as that group is bigger than 3. If so from that group take again 1 point and use it to split the subgroup in 2. But this time use 1 different color. To summarise what we done so far. A graph of 100 points. Take 1 point as center and now we have 2 groups 50 blue 49 red. 50 > 3 so we split it in 2 again. Making 25 red connections and 24 green ones. Keep doing this till you are a group smaller than 3. As for new colors, I haven't checked this but I expect that you can treat them as distance from the original perspective node. Meaning each itteration i go deaper I add 1 color but because like i did earlier when I treated the green line as red, I suspect (getting sloppy but i have typed too much already xD) that I can use that same green line in the red group later and then treat is as an blue line from the perspective of a node in the blue group. So only when you go one step further from the original perspective node do you have to create a new color i order to make no triangles. And if this is true (no proof here just conjecture xD) then the number of colors for a graph of 100 is 2 makes 50, 3-25, 4>13, 5>7,6>4,7>2. 7 colors. Or for each number it would be the amount of times you can devide it -1 by 2 using whole numbers till the group size is 2 or smaller. I think ill end here xD been typing for way to long lol
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.
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
Cool video! Are there any similar theorems which work with custom definitions of connectedness and lines? I'm curious about what are the minimal assumptions/properties to get such structures. The cases mentioned in this video were pretty dense, it'd be interesting to see how various sparsities affect the dimensions count
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.
Another proof of friends and strangers: Let x be a vertex, A be the friends of x and B be the strangers. No pair of vertices in A can be friends else they create a triangle with x however if A contains 3 or more vertices we have a no friend triangle, the same logic follows with B however one of these sets must contain 3 or more elements
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.
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.
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?
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?
I'll assume that O goes first. Suppose that X has a winning strategy. O plays any first move -- call it square a. X has a strategy to beat that, and responds by playing to square b. Now O says, "Where would X play if I had started at square b?" If that is square a, O plays anywhere; otherwise, O plays where X would. And so on. Basically, O is just playing X's strategy, with the benefit of having an extra O on the board the whole time. That extra O can only make it easier for O to win the game.
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.
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?
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
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.
Funny. I made a version of tic-tac-toe with 3 players. Also used pluses. But played it on an infinite board and your goal was to get 4 in a row. Not 3. I called it XO Plus. I found it pretty fun. You generally get a dynamic of two people always cooperating to stop 3rd player in the lead. But that player always shift, so you do not have any stable alliances. And the fun part is actually the interaction between the 3 players. Now I am sure someone have had the same idea.
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.
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.
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
This is very interesting, though I would have liked a definition of 'chaos' as used in the video. From the examples, it would seem to be 'completely random', and I'm not sure I like that definition. There are many definitions of chaos (e.g., maximum unpredictability, maximum entropy) that don't require randomness., and this would lead to different results. As an example of the arithmetic sequence, what's the longest string of numbers that can be constructed that has no arithmetic sequences of length n? From the standpoint of looking for such sequences, this would seem more 'chaotic' than random chance.
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?
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....
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?
This is interesting yet, "complete chaos" is loosely defined term. What is "complete chaos"? It's not a snapshot or still structure, rather it's dynamic. And this relation between the different phases in the dynamic motion being very sensitive is chaos. I'd say "complete chaos" WILL have some level of structure hence it is chaos. There is a structural predictable aspect to it, yet it can only be seen once it is present in front of you. Kind of like prime numbers. There is "some" obvious patterns which one can see or "almost" close to patterns, but not quiet.
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!
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
@@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
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.
@@beeble2003 Hi Beeble. Imagine an extremely high dimensional version of chess, with many many different colors, and the rules & associated metrics for winning are somewhat wilder than tic-tac-toe, or for that matter, Go. The very high dimensional Go situation should be relatively easy to grasp; then maybe very high dimensional checkers (since this is a finite and ‘fully elaborated’ game). To make the Ramsey analogy for checkers, the metric(s) might have to be altered substantially. Now, if you buy into the high dimensional Go and checkers homologues, very very high dimensional Ramsey chess seems only a hop, skip, and a jump away. [Or… maybe not. Cheers.]
@@SystemsMedicine I mean, I see the analogy you're drawing, but I don't see any way of making that precise. Ramsey theory is about the existence of specific substructures in high-dimensional objects. Chess is two-dimensional, and you're not looking for substructures (e.g., lines of pieces).
You're missing some steps in your argument: You must first assume that life is possible within the laws of physics supported by the universe, and that the necessary ingredients are available, and most importantly that they are sufficiently randomly distributed. If all of the carbon were somehow kept on the west half of the universe, and all of the hydrogen were kept on the east half, then life would not develop. That is to say, Ramsey theory only applies when there is sufficient connectivity in the graph.
@@codahighland We know life is possible with the current laws of physics. The distribution is nearly irrelevant if the Universe is large enough. Of course some distributions make life impossible, but those are very non-random. If there is the slightest randomness, than there exists a sufficient size. This is what I meant.
@@shardator I said you're missing steps, not that you're wrong: We know life is possible, yes, but that's a precondition to the argument that has to be included before you can call it a proof. However, your last message IS wrong. "The slightest randomness" is not correct. Ramsey Theory only applies to complete graphs -- that is, a graph where everything is connected to everything else. Randomness doesn't even play into it; it's combinatoric, not probabilistic. If you remove even a single connection, the theorem no longer holds. In order to apply Ramsey Theory to the existence of life, you have to make the assertion that every possible connection is available. If you're only depending on physical proximity and randomness, then to guarantee the precondition for Ramsey Theory, you need MAXIMAL randomness in the distribution, not "the slightest" randomness. (Proving THAT involves getting into much deeper theories than just Ramsey Theory.)
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.
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.
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.
Did anyone mention Erdös Discrepancy Conjecture? en.wikipedia.org/wiki/Sign_sequence This conjecture popped up again in 2014 when it could be proven for C = 2 by using a SAT solver.
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.
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
Reminds me of scientist noticing the correlation between oatmeal consumption and cancer (explain by both being correlated with age)
"Why complete chaos is impossible"
You haven't seen my apartment.
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!
One important thing about Ramsey Theory is even though we're sure that structure will emerge eventually, we're not guaranteed that the point where it emerges will be small. Some famous large numbers like TREE(3) also came out of proofs related to Ramsey Theory. Similar to Van der Waerden's theorem, in TREE function's case it's about sequences of trees with coloured nodes where you're trying to avoid a certain relation for as long as you can, but you're guaranteed it will show up eventually.
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.
Just playing along here trying to work out the answer myself.
1:25 there will always be a triangle of people that know or don't know each other. Why? :
Skipping some other approaches I had that didn't work out. Here is why I think. First just looking at 1 person. For them to not be part of an triangle the people they know must not know each other. And the people they don't know must be familiar with each other. Because if you know 2 people or more and they know each other then you got an triangle of yourself and the two others. Same in reverse. But if you are with a group of 5 this is an issue. Once you have any group of 3 or more people that know you (or not know you, as long as they all are the same) they will form a triangle amongst themselves. Because if they know you in order for you not to be in an triangle they may not know each other. Meaning the 3 form a triangle of not knowing each other. And because you are amongst 5 other people that you have to devide by 2 (knowing or not knowing) you will always have 1 group of 3
At 4 (5 including yourself) this isn't an issue yet. You can know 2 people and not know the other 2. The 2 you know don't know each other and the 2 you don't do know each other. This does leave open the question of can those 2 groups of 2 be linked to each other without making a traingle. (Because apparently I want a solution that works for every size group? Idk just a stream of thought here. We'll see where we end). We know that each of the 2 in each group both know and not know someone right now. If they know you then they don't know the other in the group of those that know you. But for the group that doesn't know you they do know each other. So in order for their not to be an triangle you would have to know one and not know the other of the opposite group. (I hope people can still follow this cause im not sure how well I'm writing this down xD maybe ill try make a simple rule at the end). The connections between the two groups themselves should not have the ability to create a triangle containing yourself because you know one group and you don't know the other. So no matter the connection between them there is always a line that is the opposite in the triangle between you and the two groups.
So 4 is possible to have no triangles. I think ill skip 3,2 and 1 😅
So how would I formulise this to make it work for any size of group. Well I think 4 (5 including yourself) may be the last group this works with. Like i said earlier:
TlDR; if one person has a group of either 3 or more people that they do know or don't know. Then it is not possible for there not to be a traingle (in a graph with just 2 states of connections at least)
...
So what if there where more? Lets call them colors because that's easier then "know or don't know". 2 colors has a max size of 5 points before things break down. But a 3 color can expand things. In the 6 point graph you can break the traingle of 3 you know by making one connection diffrent. So first they where all red connections and now we replace one of them with green (a person you may know? Idk xD) so to summarise a 6 point graph from the perspective of 1 point has 2 groups, blue and red. In this case you know 3 blue and 2 red. The 3 blue amongst themselves share red connections but because that would make a traingle we made 1 green. The red group has 1 blue connection amongst themselves so no alterations necessary. Now the connections between the 2 groups. Again like before we don't have to keep in mind our reverence point as making a traingle there is impossible between the 2 groups. So let's ignore it's existence. We are now back at a 5 point graph only this time some lines have been coloured already. Taking the perspective of 1 of the red points i have to connect to the 4 other points. One point we are already connecteded to. The other red point using a blue line. And the other 3 are still open. If we had 2 colors to work with it would be an issue because the 3 blue points where already connected to each other. But with one of them being green we can pretend that the green line is red. Given that we are ignoring the original reference point anyway this should be fine (i think? I hope that this will help later when generalising the solution) back to the red points perspective. 4 other points to connect to. Lets devide them by 2 again to make sure there will be no triangle containing it self. Lets first do the red connections. in order to prevent a triangle we have to make sure two point we connect to are part of the blue points, and because we decided that green now acts as red we have to make sure not to connect both red lines to a blue point connected to green. There are but 3 blue points though so one of them has to but that is fine. This leaves 1 point left to connect with the blue line and now the first red point is hooked up. The second red point also has to be connected to the blue points and same thing here, we don't want to connect both red lines to green. We just swap around which end of the green line we use here. Leaving the other end for a blue line. And that leaves us fully connected for a graph of 6 points with 3 colors.
I think that as long as you can manage to connect 1 point to the graph without making traingles with its self there should be a solution.
So, and im not going to work this one out fully I hope xD, if you take a graph of say 100 points. To big for my head lol. You extract 1 point to make the center and split the rest up into 2 groups. 1 blue. 1 red. Amongst that group any direct connection has to be a different color in order to prevent a traingle from forming. This becomes an issue as soon as that group is bigger than 3. If so from that group take again 1 point and use it to split the subgroup in 2. But this time use 1 different color.
To summarise what we done so far. A graph of 100 points. Take 1 point as center and now we have 2 groups 50 blue 49 red. 50 > 3 so we split it in 2 again. Making 25 red connections and 24 green ones. Keep doing this till you are a group smaller than 3. As for new colors, I haven't checked this but I expect that you can treat them as distance from the original perspective node. Meaning each itteration i go deaper I add 1 color but because like i did earlier when I treated the green line as red, I suspect (getting sloppy but i have typed too much already xD) that I can use that same green line in the red group later and then treat is as an blue line from the perspective of a node in the blue group. So only when you go one step further from the original perspective node do you have to create a new color i order to make no triangles. And if this is true (no proof here just conjecture xD) then the number of colors for a graph of 100 is 2 makes 50, 3-25, 4>13, 5>7,6>4,7>2. 7 colors. Or for each number it would be the amount of times you can devide it -1 by 2 using whole numbers till the group size is 2 or smaller.
I think ill end here xD been typing for way to long lol
reminds me how much I missed getting into Ramsey theory in grad work. Really enjoyed your work!
Glad you enjoyed it!
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.
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
it's all fun and games until the aliens ask for the 6th Ramsey Number
:D
Or busy beavers 6
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
Cool video! Are there any similar theorems which work with custom definitions of connectedness and lines?
I'm curious about what are the minimal assumptions/properties to get such structures. The cases mentioned in this video were pretty dense, it'd be interesting to see how various sparsities affect the dimensions count
14:47 "I'm going to go massively overkill"
I'd argue that proving that W(3,2)
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
Another proof of friends and strangers: Let x be a vertex, A be the friends of x and B be the strangers. No pair of vertices in A can be friends else they create a triangle with x however if A contains 3 or more vertices we have a no friend triangle, the same logic follows with B however one of these sets must contain 3 or more elements
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!
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.
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 think this hammers the nails into the coffin of apologists' Watchmaker argument.
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.
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.
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?
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?
Take a drink every time he says “combinatorical”.
But seriously, great video! Thank you.
Lol:D
Where can i find details on the "strategy switching argument" mentioned at 10:16?
I'll assume that O goes first. Suppose that X has a winning strategy. O plays any first move -- call it square a. X has a strategy to beat that, and responds by playing to square b. Now O says, "Where would X play if I had started at square b?" If that is square a, O plays anywhere; otherwise, O plays where X would. And so on. Basically, O is just playing X's strategy, with the benefit of having an extra O on the board the whole time. That extra O can only make it easier for O to win the game.
graham's number flashbacks from the beginning
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.
Hi Dr. Bazett!
Very cool!
This looks like something that could pop up in physics
statistical mechanics?
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?
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
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.
Funny. I made a version of tic-tac-toe with 3 players. Also used pluses. But played it on an infinite board and your goal was to get 4 in a row. Not 3. I called it XO Plus. I found it pretty fun. You generally get a dynamic of two people always cooperating to stop 3rd player in the lead. But that player always shift, so you do not have any stable alliances. And the fun part is actually the interaction between the 3 players.
Now I am sure someone have had the same idea.
So simple yet so easy to overlook.
At 8:00 The correct phrasing of the theorem should be "that every colouring of the [...] cube *by c colours*"
It's implicit that "colouring" means "c-colouring".
Brilliant video. I am curious on practical applications for the math.
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.
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?
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.
I was expecting a connection to chaos theory at some point, and it just never came.
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
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
This is very interesting, though I would have liked a definition of 'chaos' as used in the video. From the examples, it would seem to be 'completely random', and I'm not sure I like that definition.
There are many definitions of chaos (e.g., maximum unpredictability, maximum entropy) that don't require randomness., and this would lead to different results. As an example of the arithmetic sequence, what's the longest string of numbers that can be constructed that has no arithmetic sequences of length n? From the standpoint of looking for such sequences, this would seem more 'chaotic' than random chance.
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?
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
The universe is fundamentally structured.
What is the OEIS sequence for W(L, 2)?
4:01 and 4:08 have different alignment... help😭
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?
Now what if one of the lines randomly turned yellow.
How does this square with entropy in thermodynamics?
The only Ramsey theory that I know is the lamp is still raw
We actually played 3x3x3x3 tick-tack-toe at university.
This is interesting yet, "complete chaos" is loosely defined term. What is "complete chaos"? It's not a snapshot or still structure, rather it's dynamic. And this relation between the different phases in the dynamic motion being very sensitive is chaos.
I'd say "complete chaos" WILL have some level of structure hence it is chaos. There is a structural predictable aspect to it, yet it can only be seen once it is present in front of you. Kind of like prime numbers. There is "some" obvious patterns which one can see or "almost" close to patterns, but not quiet.
How VdW theorem will be related to prime numbers? Is that mean that will be some sequence which points primes?
There's a theorem due to Ben Green and Terry Tao that the prime numbers contain arithmetic progressions of arbitrary finite length.
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!
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 🙋♂️
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.
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
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
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
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.
I don't see why it would. Chess isn't a colouring problem.
@@beeble2003 Hi Beeble. Imagine an extremely high dimensional version of chess, with many many different colors, and the rules & associated metrics for winning are somewhat wilder than tic-tac-toe, or for that matter, Go. The very high dimensional Go situation should be relatively easy to grasp; then maybe very high dimensional checkers (since this is a finite and ‘fully elaborated’ game). To make the Ramsey analogy for checkers, the metric(s) might have to be altered substantially. Now, if you buy into the high dimensional Go and checkers homologues, very very high dimensional Ramsey chess seems only a hop, skip, and a jump away. [Or… maybe not. Cheers.]
@@SystemsMedicine I mean, I see the analogy you're drawing, but I don't see any way of making that precise. Ramsey theory is about the existence of specific substructures in high-dimensional objects. Chess is two-dimensional, and you're not looking for substructures (e.g., lines of pieces).
where is one
Entropy: defeated.
This has a strong indicaton. If the Universe is large enough, life is inevitable. No creator is needed.
You're missing some steps in your argument: You must first assume that life is possible within the laws of physics supported by the universe, and that the necessary ingredients are available, and most importantly that they are sufficiently randomly distributed. If all of the carbon were somehow kept on the west half of the universe, and all of the hydrogen were kept on the east half, then life would not develop. That is to say, Ramsey theory only applies when there is sufficient connectivity in the graph.
Also, if the universe is large enough. And another option doesn't prove the first option wrong.
@@codahighland We know life is possible with the current laws of physics.
The distribution is nearly irrelevant if the Universe is large enough. Of course some distributions make life impossible, but those are very non-random. If there is the slightest randomness, than there exists a sufficient size.
This is what I meant.
@@shardator I said you're missing steps, not that you're wrong: We know life is possible, yes, but that's a precondition to the argument that has to be included before you can call it a proof.
However, your last message IS wrong. "The slightest randomness" is not correct. Ramsey Theory only applies to complete graphs -- that is, a graph where everything is connected to everything else. Randomness doesn't even play into it; it's combinatoric, not probabilistic. If you remove even a single connection, the theorem no longer holds. In order to apply Ramsey Theory to the existence of life, you have to make the assertion that every possible connection is available. If you're only depending on physical proximity and randomness, then to guarantee the precondition for Ramsey Theory, you need MAXIMAL randomness in the distribution, not "the slightest" randomness. (Proving THAT involves getting into much deeper theories than just Ramsey Theory.)
@@codahighland I don't think your argument holds. However, my proof wouldn't fit on this margin of a comment.
Couldn't help but notice the shirt
It depends on the definition of chaos but I don’t see y’d ‘dnt b possible
It’s solved now ? With recent paper probably yes
What if those people know each other, but they also hate each other?
Just /root
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.
Im early
Love it!
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.
Did anyone mention Erdös Discrepancy Conjecture? en.wikipedia.org/wiki/Sign_sequence This conjecture popped up again in 2014 when it could be proven for C = 2 by using a SAT solver.
Super pedantic point, there's no second 'c' in combinatorial. It is not pronounced as combinactorical.