5th Ramsey Number Example (Bruteforce)
Author: Shmulik London
5th Ramsey Number
Theorem & Defenition: For every integer k there is
an integer n, such that in every graph on n (or more) vertices,
there is either a k-clique or a k-independent-set; The minimal
such n for a given k is called the kth Ramsey number
and is denoted with Rk (both statement and defenition
are special cases of a broder theorem and defenition).
The problem: find the 5th Ramsey number.
Snapshot of RamseyProblemApplet running
About the demonstrating Applet
Above is a snapshot of an execution of RamseyProblemApplet; the applet
tries to find a graph with maximal number of vertices, which doesn't contain
a 5-clique or 5-independent-set. The applet doesn't seek for a definite
solution, but rather searches randomly for better and better graphs; it
repeatedly distribute computation-packets, each go over several cycles
of graph-building (hereafter) and return with the best graph it had build.
Each such cycle starts with an empty graph, and gradualy tries to add vertices
to it, until the introducing of a new vertex creates a 5-clique or 5-independent-set.
When adding a vertex to the graph, the edges for this vertex is choosen,
in a way that the expectation of the number of neighboors of a vertex in
the graph will be approximatly half the number of vertices.
Running the example
appletviewer ramsey.html
Source
You can look at RamseyProblemApplet.java,
RamseyPacket.java
and Graph.java
for the source code.