ramsey_theorem (483B)
1 # Ramsey theorem 2 3 Consequence: any sufficiently large [undirected_graph] contains either a big [clique] or a big [independent_set] 4 - so the [union] of both problems is trivial 5 6 Generalizations: 7 8 - more than 2 colors 9 - https://en.wikipedia.org/wiki/Ramsey%27s_theorem#More_colors 10 - [hypergraphs] 11 - https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Hypergraphs 12 13 Can also be useful in [formal_language_theory]: [ramsey_formal_languages] 14 15 Up: [mathematics] 16 17 Aliases: Ramsey's theorem