A classical theorem by Erdös, Kleitman and Rothschild on the structure of triangle-free graphs shows that with high probability such graphs are bipartite. Our first main result refines this theorem by investigating the structure of the "few" triangle-free graphs which are not bipartite. We prove that with high probability these graphs are bipartite up to a few vertices. Similar results hold if we replace triangle-free by Kl+1-free and bipartite by l-partite. In our second main result we examine the class of epsilon-regular graphs in the context of the famous Regularity Lemma by Szemerédi. Whereas the case of dense graphs is well understood, the application of the Regularity Lemma for sparse random graphs still lacks an important keystone. This led to a conjecture by Kohayakawa, Luczak and Rödl, which is considered one of the most important open problems in the theory of random graphs. The conjecture states that complete subgraphs Kl occur with extremely high probability in sufficiently dense epsilon-regular graphs. We prove their conjecture for the subgraphs K4 and K5.
Translated abstract:
Ein klassisches Resultat von Erdös, Kleitmann und Rothschild zur Struktur dreiecksfreier Graphen besagt, dass solche Graphen mit hoher Wahrscheinlichkeit bipartit sind. Die Ergebnisse des ersten Hauptteils unserer Arbeit verfeinern diese Aussage und zeigen, dass die "wenigen" nicht-bipartiten dreiecksfreien Graphen mit hoher Wahrscheinlichkeit "fast" bipartit sind, d.h. bipartit bis auf wenige Knoten. Dies lässt sich verallgemeinern, indem man dreiecksfrei durch Kl+1-frei und bipartit durch l-partit ersetzt. Im zweiten Hauptteil unserer Arbeit untersuchen wir die Klasse epsilon-regulärer Graphen im Zusammenhang mit dem berühmten Regularitätslemma von Szemerédi. Für die Anwendung von Varianten des Regularitätslemmas auf dünne Zufallsgraphen fehlt ein zentrales Lemma, das von Kohayakawa, Luczak und Rödl als Vermutung formuliert wurde. Sie besagt, dass vollständige Teilgraphen Kl mit extrem hoher Wahrscheinlichkeit in hinreichend dichten epsilon-regulären Graphen auftreten. Wegen der zahlreichen möglichen Anwendungen wird der Beweis dieser Vermutung als eines der wichtigsten offenen Probleme in der Theorie zufälliger Graphen angesehen. Wir beweisen in unserer Arbeit die "kleinsten" offenen Fälle K4 und K5.
Login
BibTeX