Party problem / Ramsey's theorem R(3,3)

Question

I'm looking for an algorithm that solve Party problem. The party problem asks to find the minimum number of guests that must be invited so that at least 3 will know each other or at least 3 will not know each other. I know that the answer is 6 but i have to write a program that will check if 4 is enough, 5 people are enough, 6 ... 7 ... etc.

Edit: I want this unsophisticated algorithm, but i dont know how to enumerate all possible assignments and check whether they know each other.

Answer 1

I know what you mean, but on a certain level this question doesn't really make sense.

If you want a sophisticated algorithm, just check whether the input (number of guests) is below 6 or not. You already know that 6 is the number of guests required.

If you want an unsophisticated algorithm, given a number $n$ of guests, just enumerate all possible assignments of "knows" and "does not know" and check whether there are three people that either know each other or don't know each other.

This algorithm is obviously not very efficient. But it is likely that you can't do much better: the Ramsey number $R(4,4)$ is already not so easy to determine (it is 18, by the way), and $R(5,5)$ is not known. $R(5,5)$ is only known to be between 43 and 49 (see here).

Answer 2

Note: I have modeled the relationships between the people by a graph. One vertex for each guest. Two vertices are adjacent iff they know each other.

You can enumerate all possible adjacency matrices by using a binary number to represent each row. At each step increment the first number by 1. The n-th number is incremented iff the n-1-th number has returned to zero.(Remark: As there is a symmetry in the adjacency matrix of a graph, when incrementing a row you must only change the entries that are not determined by some previous row. In other words the first number is n bits long, the second n-1, the i-th n-i+1)

For checking if there exists such a group of people in a given graph you can check for each vertex it's neighbors to see whether they are all adjacent, and all of it's non-neighbors to see if they are all non-adjacent.

Answer 3

Here's Perl code. It's not sophisticated, but it does solve the case you asked about. It does a depth-first search of all possible graph colorings. To use breadth-first search instead, change pop @queue to shift @queue. To use depth-first iterative deepening, mumble mumble mumble. The code is intended to be simple and easy to understand, rather than to be space- or time-efficient.

To run the program, use perl ramsey.pl 6 and it will inform you there is no triangle-free 2-coloring of $K_6$. If you instead try perl ramsey.pl 5 it will print out all the triangle-free 2-colorings of $K_5$. To find triangle-free 3-colorings of $K_{16}$, use perl ramsey.pl 16 3 and go get a cup a coffee. A big cup of coffee. From Timbuktu.

    #!/usr/bin/perl
    use strict;

    my ($N, $c) = @ARGV;
    $N || usage();
    $c ||= 2;

    my @queue = ({ "0,1" => 1, NEXT => [0,1] });
    my $COUNT = 0;

    while (@queue) {
      my $config = pop @queue;
      for my $color (1 .. $c) {
        my $new_config = extend($config, $color);
        if (ok($new_config)) {
          if (is_complete($new_config)) {
            print_conf($new_config);
            $COUNT++;
          } else {
            advance_next($new_config);
            push @queue, $new_config;
          }
        }
      }
    }
    print "No solution.\n" unless $COUNT;
    exit;

    # Take a partly-colored graph and color the next edge with the specified color
    sub extend {
      my ($config, $color) = @_;
      my $new = copy($config);

      my $next_edge = $new->{NEXT};
      $new->{join ",", @$next_edge} = $color;

      return $new;
    }

    # Update the record that says which edge to color next
    sub advance_next {
      my ($config) = @_;

      if ($config->{NEXT}[1] == $N-1) {
        $config->{NEXT} = [ $config->{NEXT}[0] + 1, $config->{NEXT}[0] + 2 ];
      } else {
        $config->{NEXT}[1]++;
      }
    }

    # Is the graph completely colored?
    sub is_complete {
      my ($config) = @_;
      $config->{NEXT}[0] == $N-1;
    }

    # Is the graph triangle-free so far?
    sub ok {
      my ($config) = @_;
      my ($u, $v) = @{$config->{NEXT}};
      my $c = $config->{"$u,$v"};
      for my $i (0 .. $u-1) {
        return if $config->{"$i,$u"} == $c
          && $config->{"$i,$v"} == $c;
      }
      return 1;
    }

    sub copy {
      my ($graph) = @_;
      my %new = %$graph;
      $new{NEXT} = [ @{$graph->{NEXT}} ];
      return \%new;
    }

   sub print_conf {
      my ($graph) = @_;
      for my $i (0 .. $N-2) {
        for my $j ($i+1 .. $N-1) {
          my $k = "$i,$j";
          print qq{$i-$j: $graph->{$k}\n};
        }
      }
      print "---\n\n";
    }

Perhaps you are wondering why I used Perl. My contact specifies that I cannot be required to write Haskell code between midnight and 8 AM.