Ramsey's theorem: Difference between revisions

{{draft task}}

 

=={{header|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).

 

int a[17][17], idx[4];

puts("all good");

return 0;

{{out}} (17 x 17 connectivity matrix):

<pre>

=={{header|D}}==

{{trans|Tcl}}

 

/// Generate the connectivity matrix.

writefln("%-(%(%c %)\n%)", mat);

mat.ramseyCheck.writeln;

{{out}}

<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1

1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -

Satisfies Ramsey condition.</pre>

 

=={{header|Erlang}}==

{{trans|C}} {{libheader|Erlang digraph}}

-export([main/0]).

 

++ [{wholly_connected,V1,V2,V3,V4}

|| {V1,V2,V3,V4,_,false} <- ListConditions]}

{{out}}

<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1

 

Satisfies Ramsey condition.</pre>

 

=={{header|J}}==

1 2 4 8

1 #~ 1 j. 0 _1:} i.@<.&.(2&^.) N =: 17 NB. Turn indices into bit mask

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

 

To test if all combinations of 4 rows and columns contain both a 0 and a 1

comb=: 4 : 0 M. NB. All size x combinations of i.y

if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end.

*./ (4 comb 17) checkRow ramsey 17

1

 

=={{header|Java}}==

Translation of Tcl via D

{{works with|Java|8}}

import java.util.stream.IntStream;

 

System.out.println(ramseyCheck(mat));

}

 

<pre>[-, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1]

Satisfies Ramsey condition.</pre>

 

[[File:Ramsey.png]]

 

=={{header|Mathprog}}==

{{lines too long|Mathprog}}

This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully

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;

 

 

This may be run with:

The solution may be viewed on [[Solution Ramsey Mathprog|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=<tt>1</tt>, unconnected=<tt>0</tt>) is shown.

 

=={{header|PARI/GP}}==

This takes the [[#C|C]] solution to its logical extreme.

 

check(M)={

 

M=matrix(17,17,x,y,my(t=abs(x-y)%17);t==2^min(valuation(t,2),3))

 

 

 

}

{{out}}

<pre>- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1

1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -

OK</pre>

 

=={{header|Python}}==

{{trans|C}}

 

a = [['0'] * 17 for i in range17]

idx = [0] * 4

exit()

 

 

{{out|Output same as C}}

 

=={{header|Racket}}==

{{incorrect|Racket|The task has been changed to also require demonstrating that the graph is a solution.}}

Kind of a translation of C (ie, reducing this problem to generating a printout of a specific matrix).

 

(define N 17)

(λ(j) (case (dist i j) [(0) '-] [(1 2 4 8) 1] [else 0]))))))

 

 

=={{header|REXX}}==

 

 

<pre>

 

</pre>

 

=={{header|Ruby}}==

17.times{|i| a[i][i] = '-'}

4.times do |k|

end

a.each {|row| puts row.join(' ')}

(0...17).to_a.combination(4) do |quartet|

links = quartet.combination(2).map{|i,j| a[i][j].to_i}.reduce(:+)

end

puts "Ok"

{{out}}

<pre>

=={{header|Run BASIC}}==

{{incorrect|Run BASIC|The task has been changed to also require demonstrating that the graph is a solution.}}

for i = 1 to 17: a(i,i) = -1: next i

k = 1

next j

print

<pre>-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 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</pre>

 

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

# Generate the connectivity matrix

 

puts [join $matrix \n]

{{out}}

<pre>

Satisfies Ramsey condition

</pre>