CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)

Ramsey's theorem

From Rosetta Code
Ramsey's theorem is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

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[edit]

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).

#include <stdio.h>
 
int a[17][17], idx[4];
 
int find_group(int type, int min_n, int max_n, int depth)
{
int i, n;
if (depth == 4) {
printf("totally %sconnected group:", type ? "" : "un");
for (i = 0; i < 4; i++) printf(" %d", idx[i]);
putchar('\n');
return 1;
}
 
for (i = min_n; i < max_n; i++) {
for (n = 0; n < depth; n++)
if (a[idx[n]][i] != type) break;
 
if (n == depth) {
idx[n] = i;
if (find_group(type, 1, max_n, depth + 1))
return 1;
}
}
return 0;
}
 
int main()
{
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');
}
 
// testcase breakage
// a[2][1] = a[1][2] = 0;
 
// it's symmetric, so only need to test groups containing node 0
for (i = 0; i < 17; i++) {
idx[0] = i;
if (find_group(1, i+1, 17, 1) || find_group(0, i+1, 17, 1)) {
puts("no good");
return 0;
}
}
puts("all good");
return 0;
}
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 - 
all good

D[edit]

Translation of: Tcl
import std.stdio, std.string, std.algorithm, std.range;
 
/// Generate the connectivity matrix.
immutable(char)[][] generateMatrix() {
immutable r = format("-%b", 53643);
return r.length.iota.map!(i => r[$-i .. $] ~ r[0 .. $-i]).array;
}
 
/**Check that every clique of four has at least one pair connected
and one pair unconnected. It requires a symmetric matrix.*/

string ramseyCheck(in char[][] mat) pure @safe
in {
foreach (immutable r, const row; mat) {
assert(row.length == mat.length);
foreach (immutable c, immutable x; row)
assert(x == mat[c][r]);
}
} body {
immutable N = mat.length;
char[6] connectivity = '-';
 
foreach (immutable a; 0 .. N) {
foreach (immutable b; 0 .. N) {
if (a == b) continue;
connectivity[0] = mat[a][b];
foreach (immutable c; 0 .. N) {
if (a == c || b == c) continue;
connectivity[1] = mat[a][c];
connectivity[2] = mat[b][c];
foreach (immutable d; 0 .. N) {
if (a == d || b == d || c == d) continue;
connectivity[3] = mat[a][d];
connectivity[4] = mat[b][d];
connectivity[5] = mat[c][d];
 
// We've extracted a meaningful subgraph,
// check its connectivity.
if (!connectivity[].canFind('0'))
return format("Fail, found wholly connected: ",
a, " ", b," ", c, " ", d);
else if (!connectivity[].canFind('1'))
return format("Fail, found wholly " ~
"unconnected: ",
a, " ", b," ", c, " ", d);
}
}
}
}
 
return "Satisfies Ramsey condition.";
}
 
void main() {
const mat = generateMatrix;
writefln("%-(%(%c %)\n%)", mat);
mat.ramseyCheck.writeln;
}
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.

Elixir[edit]

Translation of: Erlang
defmodule Ramsey do
def main(n\\17) do
vertices = Enum.to_list(0 .. n-1)
g = create_graph(n,vertices)
edges = for v1 <- :digraph.vertices(g), v2 <- :digraph.out_neighbours(g, v1), do: {v1,v2}
print_graph(vertices,edges)
case ramsey_check(vertices,edges) do
true -> "Satisfies Ramsey condition."
{false,reason} -> "Not satisfies Ramsey condition:\n#{inspect reason}"
end
|> IO.puts
end
 
def create_graph(n,vertices) do
g = :digraph.new([:cyclic])
for v <- vertices, do: :digraph.add_vertex(g,v)
for i <- vertices, k <- [1,2,4,8] do
j = rem(i + k, n)
 :digraph.add_edge(g, i, j)
 :digraph.add_edge(g, j, i)
end
g
end
 
def print_graph(vertices,edges) do
Enum.each(vertices, fn j ->
Enum.map_join(vertices, " ", fn i ->
cond do
i==j -> "-"
{i,j} in edges -> "1"
true -> "0"
end
end)
|> IO.puts
end)
end
 
def ramsey_check(vertices,edges) do
listconditions =
for v1 <- vertices, v2 <- vertices, v3 <- vertices, v4 <- vertices,
v1 != v2, v1 != v3, v1 != v4, v2 != v3, v2 != v4, v3 != v4
do
all_cases = [ {v1,v2} in edges, {v1,v3} in edges, {v1,v4} in edges,
{v2,v3} in edges, {v2,v4} in edges, {v3,v4} in edges ]
{v1, v2, v3, v4, Enum.any?(all_cases), not(Enum.all?(all_cases))}
end
if Enum.all?(listconditions, fn {_,_,_,_,c1,c2} -> c1 and c2 end) do
true
else
{false, (for {v1,v2,v3,v4,false,_} <- listconditions, do: {:wholly_unconnected,v1,v2,v3,v4})
++ (for {v1,v2,v3,v4,_,false} <- listconditions, do: {:wholly_connected,v1,v2,v3,v4}) }
end
end
end
 
Ramsey.main
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.

Erlang[edit]

Translation of: C
-module(ramsey_theorem).
-export([main/0]).
 
main() ->
Vertices = lists:seq(0,16),
G = create_graph(Vertices),
String_ramsey =
case ramsey_check(G,Vertices) of
true ->
"Satisfies Ramsey condition.";
{false,Reason} ->
"Not satisfies Ramsey condition:\n"
++ io_lib:format("~p\n",[Reason])
end,
io:format("~s\n~s\n",[print_graph(G,Vertices),String_ramsey]).
 
create_graph(Vertices) ->
G = digraph:new([cyclic]),
[digraph:add_vertex(G,V) || V <- Vertices],
[begin
J = ((I + K) rem 17),
digraph:add_edge(G, I, J),
digraph:add_edge(G, J, I)
end || I <- Vertices, K <- [1,2,4,8]],
G.
 
print_graph(G,Vertices) ->
Edges =
[{V1,V2} ||
V1 <- digraph:vertices(G),
V2 <- digraph:out_neighbours(G, V1)],
lists:flatten(
[[
[case I of
J ->
$-;
_ ->
case lists:member({I,J},Edges) of
true -> $1;
false -> $0
end
end,$ ]
|| I <- Vertices] ++ [$\n] || J <- Vertices]).
 
ramsey_check(G,Vertices) ->
Edges =
[{V1,V2} ||
V1 <- digraph:vertices(G),
V2 <- digraph:out_neighbours(G, V1)],
ListConditions =
[begin
All_cases =
[lists:member({V1,V2},Edges),
lists:member({V1,V3},Edges),
lists:member({V1,V4},Edges),
lists:member({V2,V3},Edges),
lists:member({V2,V4},Edges),
lists:member({V3,V4},Edges)],
{V1,V2,V3,V4,
lists:any(fun(X) -> X end, All_cases),
not(lists:all(fun(X) -> X end, All_cases))}
end
|| V1 <- Vertices, V2 <- Vertices, V3 <- Vertices, V4 <- Vertices,
V1/=V2,V1/=V3,V1/=V4,V2/=V3,V2/=V4,V3/=V4],
case lists:all(fun({_,_,_,_,C1,C2}) -> C1 and C2 end,ListConditions) of
true -> true;
false ->
{false,
[{wholly_unconnected,V1,V2,V3,V4}
|| {V1,V2,V3,V4,false,_} <- ListConditions]
++ [{wholly_connected,V1,V2,V3,V4}
|| {V1,V2,V3,V4,_,false} <- ListConditions]}
end.
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.

J[edit]

Interpreting this task as "reproduce the output of all the other examples", then here's a stroll to the goal through the J interpreter:
   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 _

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.
)
 
NB. returns 1 iff the subbmatrix of y consisting of the columns and rows labelled x contains both 1 and 0
checkRow =. 4 : 0 "1 _
*./ 0 1 e. ,x{"1 x{y
)
 
*./ (4 comb 17) checkRow ramsey 17
1
 

Java[edit]

Translation of Tcl via D

Works with: Java version 8
import java.util.Arrays;
import java.util.stream.IntStream;
 
public class RamseysTheorem {
 
static char[][] createMatrix() {
String r = "-" + Integer.toBinaryString(53643);
int len = r.length();
return IntStream.range(0, len)
.mapToObj(i -> r.substring(len - i) + r.substring(0, len - i))
.map(String::toCharArray)
.toArray(char[][]::new);
}
 
/**
* Check that every clique of four has at least one pair connected and one
* pair unconnected. It requires a symmetric matrix.
*/

static String ramseyCheck(char[][] mat) {
int len = mat.length;
char[] connectivity = "------".toCharArray();
 
for (int a = 0; a < len; a++) {
for (int b = 0; b < len; b++) {
if (a == b)
continue;
connectivity[0] = mat[a][b];
for (int c = 0; c < len; c++) {
if (a == c || b == c)
continue;
connectivity[1] = mat[a][c];
connectivity[2] = mat[b][c];
for (int d = 0; d < len; d++) {
if (a == d || b == d || c == d)
continue;
connectivity[3] = mat[a][d];
connectivity[4] = mat[b][d];
connectivity[5] = mat[c][d];
 
// We've extracted a meaningful subgraph,
// check its connectivity.
String conn = new String(connectivity);
if (conn.indexOf('0') == -1)
return String.format("Fail, found wholly connected: "
+ "%d %d %d %d", a, b, c, d);
else if (conn.indexOf('1') == -1)
return String.format("Fail, found wholly unconnected: "
+ "%d %d %d %d", a, b, c, d);
}
}
}
}
return "Satisfies Ramsey condition.";
}
 
public static void main(String[] a) {
char[][] mat = createMatrix();
for (char[] s : mat)
System.out.println(Arrays.toString(s));
System.out.println(ramseyCheck(mat));
}
}
[-, 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.

Kotlin[edit]

Translation of: C
// version 1.1.0
 
val a = Array(17) { IntArray(17) }
val idx = IntArray(4)
 
fun findGroup(type: Int, minN: Int, maxN: Int, depth: Int): Boolean {
if (depth == 4) {
print("\nTotally ${if (type != 0) "" else "un"}connected group:")
for (i in 0 until 4) print(" ${idx[i]}")
println()
return true
}
 
for (i in minN until maxN) {
var n = depth
for (m in 0 until depth) if (a[idx[m]][i] != type) {
n = m
break
}
if (n == depth) {
idx[n] = i
if (findGroup(type, 1, maxN, depth + 1)) return true
}
}
return false
}
 
fun main(args: Array<String>) {
for (i in 0 until 17) a[i][i] = 2
var j: Int
var k = 1
while (k <= 8) {
for (i in 0 until 17) {
j = (i + k) % 17
a[i][j] = 1
a[j][i] = 1
}
k = k shl 1
}
val mark = "01-"
for (i in 0 until 17) {
for (m in 0 until 17) print("${mark[a[i][m]]} ")
println()
}
for (i in 0 until 17) {
idx[0] = i
if (findGroup(1, i + 1, 17, 1) || findGroup(0, i + 1, 17, 1)) {
println("\nRamsey condition not satisfied.")
return
}
}
println("\nRamsey condition satisfied.")
}
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 -

Ramsey condition satisfied.

Mathematica[edit]

This example may be incorrect.
The task has been changed to also require demonstrating that the graph is a solution.
Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.
CirculantGraph[17, {1, 2, 4, 8}]

Ramsey.png

Mathprog[edit]

Some lines in this example are too long (more than 80 characters). Please fix the code if it's possible and remove this message.
/*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;

This may be run with:

glpsol --minisat --math R_4_4_17.mprog --output R_4_4_17.sol

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[edit]

This takes the C solution to its logical extreme.

 
 
check(M)={
my(n=#M);
for(a=1,n-3,
for(b=a+1,n-2,
my(goal=!M[a,b]);
for(c=b+1,n-1,
if(M[a,c]==goal || M[b,c]==goal, next(2));
for(d=c+1,n,
if(M[a,d]==goal || M[b,d]==goal || M[c,d]==goal, next(3));
)
);
print(a" "b);
return(0)
)
);
1
};
 
M=matrix(17,17,x,y,my(t=abs(x-y)%17);t==2^min(valuation(t,2),3))
check(M)

Perl 6[edit]

Works with: rakudo version 2017.01
my @a = [ 0 xx 17 ] xx 17;
@a[$_;$_] = '-' for ^17;
 
for flat ^17 X 1,2,4,8 -> $i, $k {
my $j = ($i + $k) % 17;
@a[$i;$j] = @a[$j;$i] = 1;
}
.say for @a;
 
for combinations(17,4).Array -> $quartet {
my $links = [+] $quartet.combinations(2).map: -> $i,$j { @a[$i;$j] }
die "Bogus!" unless 0 < $links < 6;
}
say "OK";
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 -
OK

Python[edit]

Works with: Python version 3.4.1
Translation of: C
range17 = range(17)
a = [['0'] * 17 for i in range17]
idx = [0] * 4
 
 
def find_group(mark, min_n, max_n, depth=1):
if (depth == 4):
prefix = "" if (mark == '1') else "un"
print("Fail, found totally {}connected group:".format(prefix))
for i in range(4):
print(idx[i])
return True
 
for i in range(min_n, max_n):
n = 0
while (n < depth):
if (a[idx[n]][i] != mark):
break
n += 1
 
if (n == depth):
idx[n] = i
if (find_group(mark, 1, max_n, depth + 1)):
return True
 
return False
 
 
if __name__ == '__main__':
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'
 
# testcase breakage
# a[2][1] = a[1][2] = '0'
 
for row in a:
print(' '.join(row))
 
for i in range17:
idx[0] = i
if (find_group('1', i + 1, 17) or find_group('0', i + 1, 17)):
print("no good")
exit()
 
print("all good")
Output same as C:

Racket[edit]

This example is incorrect. Please fix the code and remove this message.
Details: 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).

#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))

REXX[edit]

Mainline programming was borrowed from   C.

/*REXX program finds and displays a 17 node graph such that any four nodes are neither  */
/*─────────────────────────────────────────── totally connected nor totally unconnected.*/
@.=0; #=17 /*initialize the node graph to zero. */
do d=0 for #; @.d.d=2; end /*d*/ /*set the diagonal elements to two. */
 
do k=1 by 0 while k<=8 /*K is doubled each time through loop.*/
do i=0 for #; j= (i+k) // # /*set a row,column and column,row. */
@.i.j=1; @.j.i=1 /*set two array elements to unity. */
end /*i*/
k=k+k /*double the value of K for each loop*/
end /*k*/
/* [↓] display a connection grid. */
do r=0 for #; _=; do c=0 for # /*build rows; build column by column. */
_=_ @.r.c /*add (append) the column to the row.*/
end /*c*/
 
say left('', 9) translate(_, "-", 2) /*display the constructed row. */
end /*r*/
/*verify the sub-graphs connections. */
!.=0; ok=1 /*Ramsey's connections; OK (so far).*/
/* [↓] check col. with row connections*/
do v=0 for # /*check the sub-graphs # of connections*/
do h=0 for # /*check column connections to the rows.*/
if @.v.h==1 then !._v.v= !._v.v + 1 /*if connected, then bump the counter.*/
end /*h*/ /* [↑] Note: we're counting each */
ok=ok &  !._v.v==# % 2 /* connection twice, so divide */
end /*v*/ /* the total by two. */
/* [↓] check col. with row connections*/
do h=0 for # /*check the sub-graphs # of connections*/
do v=0 for # /*check the row connection to a column.*/
if @.h.v==1 then !._h.h= !._h.h + 1 /*if connected, then bump the counter.*/
end /*v*/ /* [↑] Note: we're counting each */
ok=ok &  !._h.h==# % 2 /* connection twice, so divide */
end /*h*/ /* the total by two. */
say /*stick a fork in it, we're all done. */
say space("Ramsey's condition is" word('not', 1+ok) "satisfied.") /*yea─or─nay.*/
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 -

Ramsey's condition is satisfied.

Ruby[edit]

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(' ')}
# check taken from Perl6 version
(0...17).to_a.combination(4) do |quartet|
links = quartet.combination(2).map{|i,j| a[i][j].to_i}.reduce(:+)
abort "Bogus" unless 0 < links && links < 6
end
puts "Ok"
 
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 -
Ok

Run BASIC[edit]

This example is incorrect. Please fix the code and remove this message.
Details: The task has been changed to also require demonstrating that the graph is a solution.
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
-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

Sidef[edit]

Translation of: Ruby
var a = 17.of { 17.of(0) }
 
17.itimes{|i| a[i][i] = '-' }
4.itimes { |k|
17.itimes { |i|
var j = ((i + 1<<k) % 17)
a[i][j] = (a[j][i] = 1)
}
}
 
a.each {|row| say row.join(' ') }
 
@(0..16).combinations(4).each { |quartet|
var links = quartet.combinations(2).map{|p| a.dig(p...) }.sum
((0 < links) && (links < 6)) || die "Bogus!"
}
say "Ok"
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 -
Ok

Tcl[edit]

Works with: Tcl version 8.6
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
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