4 ms·
For those who want a prefilter, Ramsey numbers are the minimum number of guests, written R(m, n), that must be invited so that at least m guests will know each
by TheRealPomax 2y ago
For those who want a prefilter, Ramsey numbers are the minimum number of guests, written R(m, n), that must be invited so that at least m guests will know each other or at least n guests will not know each other.
Or in math: the minimum number of vertices in a fully connected graph that guarantee a clique of order m, or an independent set of order n.
- n4r9 2y agoWhat do you mean by "fully connected" here?
- IncreasePosts 2y agoFor every set of two vertices, there is at least one path that connects them.
- n4r9 2y agoBut... That's not part of the definition of Ramsey numbers. Often it's defined in terms of a complete graph where the egdmmdges are coloured either red or blue. But there's nothing about the blue subgraph or red subgraph needing to be connected. https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem
- TheRealPomax 2y agoScroll down a bit to https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers https://en.m.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_nu.... Ramsey numbers arise from the original problem, and play a role in its proof, but they are not "the same thing" as Ramsey's Theorem.
- n4r9 2y agoSure, Ramsey's Theorem guarantees that Ramsey numbers exist. But at no point is it assumed that the graph is connected. The section you linked puts it quite simply: > The Ramsey number is the minimum number of vertices, v = R(m, n), such that all undirected simple graphs of order v, contain a clique of order m, or an independent set of order n. The graph is undirected and simple. But it need not be connected.