The Secret of Ramsey Numbers
47 points by pseudolus 4 days ago | 7 comments
  • pvg 3 days ago |
    Related thread about a year ago https://news.ycombinator.com/item?id=38590156
  • TheRealPomax 3 days 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 3 days ago |
      What do you mean by "fully connected" here?
      • IncreasePosts 3 days ago |
        For every set of two vertices, there is at least one path that connects them.
        • n4r9 2 days ago |
          But... 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

          • TheRealPomax 2 days ago |
            Scroll down a bit to 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 2 days ago |
              Sure, 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.