Ramsey's theorem
The task is to find a graph with 17 Nodes such that any 4 Nodes are neither totally connected nor totally unconnected, so demonstrating Ramsey's theorem. A specially-nominated solution may be used, but if so it must be checked to see if if there are any sub-graphs that are totally connected or totally unconnected.
C
For 17 nodes, (4,4) happens to have a special solution: arrange nodes on a circle, and connect all pairs with distances 1, 2, 4, and 8. It's easier to prove it on paper and just show the result than let a computer find it (you can call it optimization). <lang c>#include <stdio.h>
int main() { int a[17][17] = Template:0; int i, j, k; const char *mark = "01-";
for (i = 0; i < 17; i++) a[i][i] = 2;
for (k = 1; k <= 8; k <<= 1) { for (i = 0; i < 17; i++) { j = (i + k) % 17; a[i][j] = a[j][i] = 1; } }
for (i = 0; i < 17; i++) { for (j = 0; j < 17; j++) printf("%c ", mark[a[i][j]]); putchar('\n'); } return 0; }</lang>
- Output:
(17 x 17 connectivity matrix)
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
D
<lang d>import std.stdio;
void main() {
enum size_t N = 17; char[N][N] mat = '0';
foreach (immutable i, ref row; mat) row[i] = '-';
foreach (immutable e; 0 .. 4) { foreach (immutable i, ref row; mat) { immutable j = (i + (2 ^^ e)) % N; row[j] = mat[j][i] = '1'; } }
writefln("%(%(%c %)\n%)", mat);
}</lang>
- Output:
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
Erlang
<lang erlang>-module(ramsey_theorem). -export([main/0]).
main() -> G = digraph:new([cyclic]), List = lists:seq(0,16), [digraph:add_vertex(G,V) || V <- List], [begin J = ((I + K) rem 17), digraph:add_edge(G, I, J), digraph:add_edge(G, J, I) end || I <- List, K <- [1,2,4,8]], Edges = [{V1,V2} || V1 <- digraph:vertices(G), V2 <- digraph:out_neighbours(G, V1)], Connectivity_matrix = lists:flatten( [[ [case I of J -> $-; _ -> case lists:member({I,J},Edges) of true -> $1; false -> $0 end end,$ ] || I <- List] ++ [$\n] || J <- List]), io:format("~s",[Connectivity_matrix]).</lang>
- Output:
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
J
Interpreting this task as "reproduce the output of all the other examples", then here's a stroll to the goal through the J interpreter: <lang j> i.@<.&.(2&^.) N =: 17 NB. Count to N by powers of 2 1 2 4 8
1 #~ 1 j. 0 _1:} i.@<.&.(2&^.) N =: 17 NB. Turn indices into bit mask
1 0 1 0 0 1 0 0 0 0 1
(, |.) 1 #~ 1 j. 0 _1:} i.@<.&.(2&^.) N =: 17 NB. Cat the bitmask with its own reflection
1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1
_1 |.^:(<N) _ , (, |.) 1 #~ 1 j. 0 _1:} <: i.@<.&.(2&^.) N=:17 NB. Then rotate N times to produce the array
_ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _
NB. Packaged up as a re-usable function ramsey =: _1&|.^:((<@])`(_ , [: (, |.) 1 #~ 1 j. 0 _1:} [: <: i.@<.&.(2&^.)@])) ramsey 17
_ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _</lang> Yes, this is really how you solve problems in J.
Mathematica
<lang mathematica>CirculantGraph[17, {1, 2, 4, 8}]</lang>
Mathprog
<lang>/*Ramsey 4 4 17
This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully connected, nor fully disconnected Nigel_Galloway January 18th., 2012
- /
param Nodes := 17; var Arc{1..Nodes, 1..Nodes}, binary;
clique{a in 1..(Nodes-3), b in (a+1)..(Nodes-2), c in (b+1)..(Nodes-1), d in (c+1)..Nodes} : 1 <= Arc[a,b] + Arc[a,c] + Arc[a,d] + Arc[b,c] + Arc[b,d] + Arc[c,d] <= 5;
end;</lang>
This may be run with: <lang bash>glpsol --minisat --math R_4_4_17.mprog --output R_4_4_17.sol</lang> The solution may be viewed on this page. In the solution file, the first section identifies the number of nodes connected in this clique. In the second part of the solution, the status of each arc in the graph (connected=1, unconnected=0) is shown.
PARI/GP
This takes the C solution to its logical extreme. <lang parigp>matrix(17,17,x,y,my(t=(x-y)%17);t==2^min(valuation(t,2),3))</lang>
Perl 6
<lang Perl 6>my @a = [ 0 xx 17 ] xx 17; @a[$_][$_] = 2 for ^17;
loop (my $k = 1; $k <= 8; $k +<= 1) {
for ^17 -> $i { my $j = ($i + $k) % 17; @a[$i][$j] = @a[$j][$i] = 1; }
}
say <0 1 ->[@a[$_][]] for ^17;</lang>
Python
<lang python>if __name__ == '__main__':
range17 = range(17) a = [['0'] * 17 for i in range17] for i in range17: a[i][i] = '-' for k in range(4): for i in range17: j = (i + pow(2, k)) % 17 a[i][j] = a[j][i] = '1' for row in a: print(' '.join(row))</lang>
- Output same as C:
Racket
Kind of a translation of C (ie, reducing this problem to generating a printout of a specific matrix). <lang racket>#lang racket
(define N 17)
(define (dist i j)
(define d (abs (- i j))) (if (<= d (quotient N 2)) d (- N d)))
(define v
(build-vector N (λ(i) (build-vector N (λ(j) (case (dist i j) [(0) '-] [(1 2 4 8) 1] [else 0]))))))
(for ([row v]) (displayln row))</lang>
REXX
<lang rexx>/*REXX programs finds and displays a 17 node graph such that any four */ /*────── nodes are neither totally connected nor totally unconnected.*/ @.=0 /*initialize the node graph to 0.*/
do d=0 for 17; @.d.d=2; end /*set the diagonal elements to 2.*/
k=1
do while k<=8 do i=0 for 17 /*process each column in array. */ j= (i+k) // 17 /*set a row,col and col,row. */ @.i.j=1; @.j.i=1 /*set two array elements to one. */ end /*i*/ k=k*2 /*double the value of K each loop*/ end /*while k≤8*/
do r=0 for 17; _=; do c=0 for 17 /*show each row, build col by col*/ _=_ @.r.c /*add this column to the row. */ end /*c*/
say left(,9) translate(_,'-',2) /*display the constructed row. */ end /*r*/ /*stick a fork in it, we're done.*/</lang>
- Output:
(17x17 connectivity matrix):
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
Ruby
<lang ruby>a = Array.new(17){['0'] * 17} 17.times{|i| a[i][i] = '-'} 4.times do |k|
17.times do |i| j = (i + 2 ** k) % 17 a[i][j] = a[j][i] = '1' end
end a.each {|row| puts row.join(' ')}</lang>
- Output:
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
Run BASIC
<lang runbasic>dim a(17,17) for i = 1 to 17: a(i,i) = -1: next i k = 1 while k <= 8
for i = 1 to 17 j = (i + k) mod 17 a(i,j) = 1 a(j,i) = 1 next i k = k * 2
wend for i = 1 to 17
for j = 1 to 17 print a(i,j);" "; next j print
next i</lang>
-1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 -1 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -1 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -1 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 -1
Tcl
<lang tcl>package require Tcl 8.6
- Generate the connectivity matrix
set init [split [format -%b 53643] ""] set matrix {} for {set r $init} {$r ni $matrix} {set r [concat [lindex $r end] [lrange $r 0 end-1]]} {
lappend matrix $r
}
- Check that every clique of four has at least *one* pair connected and one
- pair unconnected. ASSUMES that the graph is symmetric.
proc ramseyCheck4 {matrix} {
set N [llength $matrix] set connectivity [lrepeat 6 -] for {set a 0} {$a < $N} {incr a} {
for {set b 0} {$b < $N} {incr b} { if {$a==$b} continue lset connectivity 0 [lindex $matrix $a $b] for {set c 0} {$c < $N} {incr c} { if {$a==$c || $b==$c} continue lset connectivity 1 [lindex $matrix $a $c] lset connectivity 2 [lindex $matrix $b $c] for {set d 0} {$d < $N} {incr d} { if {$a==$d || $b==$d || $c==$d} continue lset connectivity 3 [lindex $matrix $a $d] lset connectivity 4 [lindex $matrix $b $d] lset connectivity 5 [lindex $matrix $c $d]
# We've extracted a meaningful subgraph; check its connectivity if {0 ni $connectivity} { puts "FAIL! Found wholly connected: $a $b $c $d" return } elseif {1 ni $connectivity} { puts "FAIL! Found wholly unconnected: $a $b $c $d" return } } } }
} puts "Satisfies Ramsey condition"
}
puts [join $matrix \n] ramseyCheck4 $matrix</lang>
- Output:
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - Satisfies Ramsey condition
- Draft Programming Tasks
- C
- C examples needing attention
- Examples needing attention
- D
- D examples needing attention
- Erlang
- Erlang examples needing attention
- Erlang digraph
- J
- J examples needing attention
- Mathematica
- Mathprog
- Mathprog examples needing attention
- PARI/GP
- PARI/GP examples needing attention
- Perl 6
- Perl 6 examples needing attention
- Python
- Python examples needing attention
- Racket
- Racket examples needing attention
- REXX
- REXX examples needing attention
- Ruby
- Ruby examples needing attention
- Run BASIC
- Run BASIC examples needing attention
- Tcl