Friends and Strangers Theorem - Numberphile
Why Mathematics Stack Exchange recommends it
Mathematics Stack Exchange answerers link it when explaining the K_6 / Ramsey R(3,3) pigeonhole argument that any 2-colored complete graph on six vertices contains a monochromatic triangle.
Recommended by 2 people across 2 different months, 2015 to 2020.
What it is
A Numberphile video in which Simon Pampena explains the friends and strangers theorem: among any six people, there are three mutual friends or three mutual strangers. He demonstrates it using Facebook and One Direction examples and a group of Numberphile followers.
What people said
Recommends JMoravitz · 2015-05 · Mathematics Stack Exchange · on “Prove that if a graph has six vertices, then at least one of G or $\bar{G}$ has a subgraph isomorphic to $K_3$”
See the youtube video on the subject posted by Numberphile here [this video] . Theorem : A graph, $G$, with six or more vertices will always contain $K_3$ as an induced subgraph or its complement, $\overline{G}$, will contain $K_3$ as an induced subgraph. The argument is as follows: Suppose you have a graph, $G$, on six vertices. (The vertices may represent people, and edges between vertices represents that the two people are friends. We assume friendship is a symmetric binary relation) Pick one of those vertices and call it $v$. Among the five other vertices one of the following two things will be true: $v$ has at least 3 neighbors $v$ has at least 3 non-neighbors (seen easily from pigeon-hole p
Recommends Pedro Juan Soto · 2020-05 · Mathematics Stack Exchange · on “Prove that there is either a red triangle whose vertices are in S, or a set of 4 points in S such that”
Notice that you are proving $R(3,4) \leq 10$ btw You started (your pigeonholing) a bit too weak; if you fix a point $A$ the pigeon-hole principle gives that there are either 4 points that are red connected to A or there 6 that are blue connected to $A$ (because of $x+y-1 = 9 $ means either ...) Case # 1 there are 4 red connected to $A$ call them $B,C,D,E$ then either there is a red edge amongst them or not ... you know the rest Case # 2 there are 6 blue connected to $A$ call them $B,C,D,E,F,G$ then either there is a ... you know the rest ... ( hint either a blue or red triangle amongst the $B,C,D,E,F,G$ ) ... and just in case you don't, read this article about friends and strangers [LINK] an
Cites user645636 · 2019-03 · Mathematics Stack Exchange · on “Chromatic Triangles on a $K_{17}$ graph”
Here's my attempt, using a result (stronger cousin as well)from a $K_6$ which Numberphile [this video] showed: $$4\\3_\nwarrow\hspace{6 pt}\uparrow\hspace{6pt}\nearrow^5\\\hspace{-2pt}2\leftarrow1\rightarrow6$$ Imagine we have an arbitrary $K_6$ (not that I can create one properly, without rotate or turn, or using an image). If we examine it from one vertex, and do a coloring with at most 2 colors (key words there are at most), by pigeonhole principle, we have 1 color with at least 3 of the 5 connecting lines to the other vertices. Let us assume they are red ( blue being the other for consistency with the video), then we get the following(labelling is arbitrary here, graph isn't supposed to be di