monochromatic Cn in 2-coloring for arbitrary n
Source: VTRMC 2004 P6
August 2, 2021
combinatorics
Problem Statement
An enormous party has an infinite number of people. Each two people either know or don't know each other. Given a positive integer , prove there are people in the party such that either they all know each other, or nobody knows each other (so the first possibility means that if and are any two of the people, then knows , whereas the second possibility means that if and are any two of the people, then does not know ).