Research Seminar

Über die Jahre hat sich die von Szemeredi Mitte der 70er Jahre initiierte Regularitätsmethode als ein fundamentales Instrument der modernen Graphentheorie erwiesen. In ihrer Zentrum steht die Erkenntnis, dass dichte Graphen durch eine konstante Anzahl quasizufälliger, bipartiter Graphen approximiert werden können. Ziel dieses Vortrages ist es, Verbindungen zur Theorie der Quasizufälligkeit vorzustellen und Verallgemeinerungen jener Ansätze für dünne Graphen und für Hypergraphen zu betrachten. Diese neuen Ergebnisse und ihre Anwendungen im Bereich der Extremalen Hypergraphentheorie und Algorithmik werden vorgestellt. Im Besonderen wird ein Approximationsalgorithmus für das MaxCut-Problem für Teilgraphen dünner Zufallsgraphen und minimale, hinreichende Gradbedingungen für Matchings und Hamiltonkreise in Hypergraphen diskutiert.

Let Perf(n,c) be the set of perfect graphs on n vertices with c * (n choose 2) edges. We give a function h(c) s.t. log_2(|Perf(n,c)|) = h(c) (n choose 2) + o(n^2). The proof of this result uses the idea of coloured homomorphisms introduced by Alon and Shapira and the regularity lemma .