81–90 of 116 posts
>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three who all know each other, or a group of three who have never met. Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three who all know each other, or a group of three who have never met. Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
I found this enlightening (particularly "Sketch of a Proof"), though I also admit that it seemed fairly straightforward, with elegance borne of simplicity rather than of brilliance or cleverness: https://en.m.wikipedia.org/wiki/Theorem_on_friends_and_stran...
>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three who all know each other, or a group of three who have never met. Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
If you imagine a six vertices arranged around a point and make any number of edges connecting them to represent knows each other. For any choice of edges, you can either find 3 vertices that are fully connected or you can find three vertices that have no connections.
Earlier quoted context omitted.
It is worse than that. Here is the calculation. The number of graphs of size n is 2^(n choose 2). (There are n choose 2 pairs of points, each of which could be or not be an edge.) If the answer is 43, that's 2^903 which is roughly 6.762 * 10^271. If the answer is 48, that's 2^1128 which is roughly 3.646 x 10^339. Naive plus better computers is not enough to tackle this problem.
>The number of graphs of size n is 2^(n choose 2). This is overcounting by many orders of magnitude. For example, there's only one graph with one edge, not (n choose 2). For n = 43 you're overcounting these graphs by a factor of 903. Similarly there are only two graphs with two edges (either the two edges are connected or not), not ((n choose 2) choose 2). For n = 43 you're overcounting these graphs by a factor of ~2…
But suppose that we are able to do so. How much does this do for us? Well, it can help us by a factor of at most n!, because you generate isomorphic graphs by permuting the vertices. Which for 43 is around 6.04152630633738e+52. For 48 is around 1.24139155925361e+61. Those are big savings to be sure, but are still dwarfed by the size of the search space.
So the next thing to do is to not only try to look at each graph up to isomorphism once, but to somehow generate them in an order that makes it likely that you find cliques or independent sets early. Thereby letting you prune out big chunks of the search space. With the ability to start different computers out in different ranges so we can parallelize the search. But by now we're well down on the path to something that is very much not a naive search.
Earlier quoted context omitted.
Pentagons are 5-sided polygons where all the sides are equal. Not all 5-sided polygons are pentagons. What am I missing?
What you're describing is called a regular pentagon.
>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three who all know each other, or a group of three who have never met. Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
The 'who have never met' isn't the opposite of 'all know each other', it's no two people of these three know each other. The opposite would be don't all know each other. If you imagine a six vertices arranged around a point and make any number of edges connecting them to represent knows each other. For any choice of edges, you can either find 3 vertices that are fully connected or you can find three vertices that hav…
>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three who all know each other, or a group of three who have never met. Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
If this seems so trivial to you, simply write down the proof. If you are not really mathematically gifted, you will soon see where the problem is ... ;-)
> the pentagon (or really any five-sided polygon) An odd line. Surprising given the quality of the rest of the article.
>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three who all know each other, or a group of three who have never met. Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
Earlier quoted context omitted.
A bit of an aside, but this was always my biggest bugbear when learning maths way back when I was in school - we were never given any practical reasons of why any of it was useful. Even if you explicitly asked the maths teacher "what's it for", they could never give a useful response - it often seemed like they'd never considered this themselves. Around 13-14 years old, I got interested in building mods for Quake. Wh…
As a teacher, I believe applications must be discussed - I am a physicist after all. But I remember my peers asking for applications from math teachers when we were in school, but I never saw them ask the same from art teachers. Somehow, everyone understood that drawing and coloring were just for pleasure and stroking our aesthetic sensibilities, and an application was not needed. But people rarely think of math the…
To phrase it another way: practicing scales can be boring. But playing a walking bassline is a whole lot more similar to scales than it is anything else, and one of the most fun things to do with an instrument is to jam with other people using the fundamentals you all share.
I never felt the same way with math, because I never felt like math allowed me to put anything unique and of my own into the mix. Learning the same proof from a book that a million other kids taking geometry learned was much less interesting to me than transcribing a solo some musician played so that I could try to riff on the style they put into the world.
Sure, yeah, there's rules in music theory too. You're expected to learn them, and get graded on them in tests if you study music academically. But I don't know of any famous mathematician who ever said something like the various Duke Ellington quotes around "if it sounds good, it IS good". In the art world, similar riffs on an existing idea are everything. In math, they're just... wrong. Or at least thats the understanding I had as a student which led me to only care about the parts of math that seemed to be directly applicable to me, or really intuitive.