Dr. J. Waldmann, Institut für Informatik, Universität Leipzig
Sei P eine Eigenschaft von Objekten, und size(X) die Größe des Objekts X. Dann gilt: Für jede Zahl n existiert ein m, so daß jedes Objekt X mit size(X) >= m wenigstens ein Unter-Objekt Y mit P(Y) und size (Y) >= n enthält.
Das hängt natürlich von P und von der Unter-Objekt-Relation ab.
Ein tatsächliches Y mit P(Y) ist im Allgemeinen schwer in X zu lokalisieren. Oft finden wir für m nur Schranken, die aber nicht scharf sind. Manchmal reicht uns schon die Aussage für n und m gleich abzählbar unendlich.
Ich möchte das an verschiedenen Beispielen erläutern.
Von dort gibt es Verbindungen zur Arithmetik: wir betrachten bestimmte Multigraphen auf Zahlen, die Summen oder arithmetische Folgen kodieren (Satz von van der Waerden).
Wechseln wir von Graphen zu Bäumen (Termen), nehmen wir als Unter-Objekte die homöomorph eingebetteten Terme. (Genauer: die Objekte sind Mengen von Bäumen, und P kodiert die Einbettung.) Das führt zu Higmans Lemma und Kruskals Satz über Wohlquasiordnungen. Den wenden wir an, um mit Simplifikationsordnungen Terminationsbeweise für Ersetzungssysteme zu führen.
Arbeiten von Robertson und Seymor übertragen das wieder auf Graphen.
Wählen wir eine andere Unter-Objekt-Beziehung (Faktor statt Einbettung), dann sind bestimmte Muster doch vermeidbar. Solche Untersuchungen bilden tatsächlich einen der Anfänge der Theorie die formalen Sprachen (Thue und Morse, um 1900).
Von dort gibt es wiederum Verbindungen zur Algebra: wir fragen, wann eine endlich erzeugte (Halb-)Gruppe, die nicht mehr frei ist, sondern zusätzlichen Bedingungen genügt, endlich wird. Das ist das Burnside-Problem.