Ramsey@Home (beendet)
Das Projekt sucht neue untere Schranken für Ramsey Zahlen.
Es werden vollständige Graphen auf die Existenz von bestimmten Untergraphen untersucht. Die Existenz ist hierbei leicht zu zeigen. Die Frage, ab welcher Größe eines Graphen diese Untergraphen auftreten müssen ist schwerer und wird hier untersucht.
Gesucht wird eine bessere (also höhere) untere Schranke für die Ramsey-Zahl R(3,3,3,3,3).
Veranschaulichen wir R(3,3) einmal. R(3,3) ist anschaulich die Zahl von Leuten, die man auf eine Feier einladen muss, so dass sich immer mindestens 3 Leute untereinander kennen, oder mindestens 3 Leute untereinander nicht kennen.
- R(3,3)>3, denn bei drei Leuten A,B,C können sich zum Beispiel nur A und B kennen
- R(3,3)>4, denn bei vier Leuten A-D können sich z.B. nur A&B und C&D kennen. Es kennen sich hier 2 Leute untereinander nicht (z.B A&C und A&D), und 2 kennen sich
- R(3,3)>5, denn es lässt sich eine Gruppe von 5 Leuten konstuieren (siehe Bild), so dass sich nur maximal 2 Leute gegenseitig kennen (rote Verbindungen) und maximal 2 Leute nicht kennen (blaue Verbindungen).
- R(3,3)=6. Für jede beliebige Sechsergruppe existiert eine Untergruppe von mindestens 3 Leute, die sich untereinander kennen, oder eben nicht kennen. Das bedeutet für ein analoges Bild, dass man ein einfarbiges Dreieck findet (finden muss).
Betrachtet man statt R(3,3) jetzt R(3,3,3), so kann muss man sich das eine dritte Eigenschaft vorstellen, also z.B. hat gehört von. Für die Suche nach R(3,3,3,3,3) zwei weitere Eigenschaften. Das Projekt benutzt daher einen Zusammenhang zwischen solchen Eigenschaften in Graphen und summenfreien Mengen.
Ein Paper von Exoo zeigt R(3,3,3,3,3) >= S(5) + 2. Weiter zeigte Exoo, dass S(5) >= 160 gilt, woraus folgt R(3,3,3,3,3) >= 162. Das Projekt sucht jetzt also nach einer Verteilung der Zahlen 1-162 in 5 summenfreien Mengen. Die bisher beste Lösung kann man sich auf der Homepage anschauen.
Man benutzt hier eine heuristische Suche durch die möglichen 5162 Mengen, die auftreten können. Ein Bruteforce-Ansatz ist bei dieser Größe ausgeschlossen.
Siehe Satz von Ramsey.
Ende 2008 wurde das Projekt erstmal gestoppt, da man mit der bisherigen Anwendung keine wirklichen Fortschritte mehr machen konnte. Die Seite ist momentan nicht erreichbar.
Inhalt
Projektübersicht
Ramsey | |
---|---|
Name | Ramsey |
Kategorie | Mathematik |
Ziel | Minimieren von Ramsey Zahlen |
Kommerziell | nein |
Homepage | ramseyathome.com/ramsey |
Dieses Projekt wird in Wisconsin, USA durchgeführt. |
Projektstatus
Projektlinks
Neuigkeiten (RSS-Feed)
Statistiken
Wo | Übersicht | Top Teams | Top User |
---|---|---|---|
Projekt Home Page | Top Teams | Top User | |
BOINCstats.com | Übersicht | Top Teams | Top User |
BOINCsynergy.com: Der Service wurde eingestellt. | |||
stats.free-dc.org | Übersicht | Top Teams | Top User |
allprojectstats.com: Der Service wurde eingestellt. |
Clientprogramm
Betriebssysteme
Windows | ||
Windows 64bit | ||
Linux | ||
Linux 64bit | ||
DOS | ||
MacOS X | ||
BSD | ||
Solaris | ||
Java (betriebssystemunabhängig) |
Client-Eigenschaften
Funktioniert auch über Proxy | |
Normal ausführbares Programm | |
Als Bildschirmschoner benutzbar | |
Kommandozeilenversion verfügbar | |
Personal Proxy für Work units erhältlich | |
Work units auch per Mail austauschbar | |
Quellcode verfügbar | |
Auch offline nutzbar | |
Checkpoints |
Dies und das
- Im Herbst 2008 wurde entschieden keine Credits mehr zu vergeben. Dazu entschied sich der Projektbetreiber, nachdem er bis zu 80% seiner Zeit ins Creditsystem zu stecken.
Installation
Ramsey@Home (beendet) benutzt die BOINC-Infrastruktur. Die Anmeldung, Installation und Konfiguration sind auf der allgemeinen BOINC-Seite beschrieben.
Veröffentlichte Versionen
- 20.09.2008: 1.12 erste MacOS X-Version
- 17.09.2008: 1.03 erste Linux-Version
Die neuesten Anwendungen findet man hier.
Screenshots
Bisher zeigt der Client noch keine eigenen Grafiken bei der Berechnung an, die allgemeinen BOINC-Screenshots zeigen aber, wie der Client arbeitet. Wenn BOINC als Bildschirmschoner läuft, wird bei diesem Projekt das BOINC-Logo angezeigt.