Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Kombinatorik: Unordentliche Graphen

Je größer ein Netzwerk wird, desto leichter lassen sich gewisse Strukturen darin erkennen. Dafür muss ein Graph aber sehr viel mehr Punkte enthalten als gedacht, wie Mathematiker nun gezeigt haben.
Ein näherungsweise zweidimensionaler Graph in drei Dimensionen vor blauem Hintergrund.Laden...

Je größer ein Netzwerk wird, desto leichter lassen sich gewisse Strukturen darin erkennen. Dafür muss ein Graph aber sehr viel mehr Punkte enthalten als gedacht, wie Mathematiker nun gezeigt haben.

Nach mehr als 70 Jahren sind Mathematiker nun endlich einem der hartnäckigsten Zahlenwerte etwas näher gekommen. In einer noch nicht begutachteten Arbeit lieferten David Conlon vom Caltech und Asaf Ferber von der University of California in Irvine im September 2020 die bisher genaueste Schätzung für so genannte mehrfarbige Ramsey-Zahlen. Diese geben an, wie groß ein Netzwerk sein darf, bevor zwangsläufig bestimmte Arten von Mustern auftreten. »Im Universum gibt es keinen absoluten Zufall«, so Maria Axenovich vom Karlsruher Institut für Technologie in Deutschland. »Man findet immer geordnete Gruppen, und Ramsey-Zahlen stellen ein Maß dafür dar.«

Ein Graph oder Netzwerk ist eine Sammlung von Punkten, die durch Kanten miteinander verbunden sind …

Kennen Sie schon …

Highlights 1/2021

Spektrum der Wissenschaft – Highlights 1/2021: Mathematische Spiele und Strategien

Ziegenproblem: Ist hinter der nächsten Tür eine Ziege oder das Auto? • Gefangenendilemma: Kooperieren, betrügen oder ganz aussteigen? • Strategien der besten Wahl: Wie lange soll die Prinzessin auf den Traumprinzen warten?

46/2020

Spektrum - Die Woche – 46/2020

Vor 125 Jahren entdeckte Wilhelm Conrad Röntgen die nach ihm benannten Strahlen. Weltraumforschern öffnen sie ein Fenster zum Kosmos. Außerdem: Wie sinnvoll wäre es, Herdenimmunität durch Infektionen zu erreichen?

Meins! - Warum weniger manchmal mehr ist

Spektrum Kompakt – Meins! - Warum weniger manchmal mehr ist

Wer einen Umzug vor sich hat, wird häufiger mal seufzen: Hätte man doch bloß nicht so viele Bücher, sperrige Möbel oder andere Habseligkeiten angesammelt - und beneidet gleichzeitig Menschen, die regelmäßig und konsequent ausmisten.

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Quellen

Conlon, D., Ferber, A.: Lower bounds for multicolor Ramsey numbers. ArXiv: 2009.10458, 2020

Widgerson, Y.: An improved lower bound on multicolor Ramsey numbers. ArXiv: 2009.12020, 2020