Vorträge in der Woche 16.07.2012 bis 22.07.2012

Montag, 16.07.2012: Über eine Klasse azyklischer Digraphen

Prof. Dr. Stephan Wagner

Azyklische Digraphen sind Digraphen (gerichtete Graphen) ohne gerichtete Zyklen; damit stellen sie das gerichtete Analogon von Wäldern dar. Derartige Digraphen kommen in verschiedensten Zusammenhängen in der Mathematik und Informatik vor. Die Frage nach der (asymptotischen) Anzahl azyklischer Digraphen mit gegebener Knotenzahl wurde in den 70er Jahren von Robinson beantwortet, der zu diesem Zweck auch einen speziellen Typ von erzeugenden Funktionen definierte. In diesem Vortrag soll es um azyklische Digraphen mit einer zusätzlichen Eigenschaft gehen: unter der Ausgangsnachbarschaft eines Knotens v verstehen wir die Menge all jener Knoten w, für die es eine gerichtete Kante von v nach w gibt. Wir fordern nun, dass keine zwei verschiedenen Knoten dieselbe Menge von Ausgangsnachbarn haben. Die resultierende Klasse azyklischer Digraphen steht in natürlicher Bijektion zu sogenannten transitiven Mengen aus der elementaren Mengenlehre. In einer unlängst erschienenen Arbeit behandeln Policriti und Tomescu verschiedene Abzählprobleme im Zusammenhang mit diesen von ihnen EADs (extensional acyclic digraphs) genannten Digraphen. In deren Arbeit finden sich auch diverse asymptotische Fragen und Vermutungen, wie zum Beispiel, dass etwa 32,6 Prozent aller azyklischen Digraphen die Zusatzeigenschaft erfüllen. Wie sich zeigt, kann diese Vermutung mit Hilfe von erzeugenden Funktionen und sorgfältiger Analyse der Singularitäten bestätigt werden. Auch diverse weitere Fragestellungen die Struktur solcher Digraphen betreffend können auf diese Weise beantwortet werden, wie etwa die Verteilung der Kantenzahl oder der Länge des längsten gerichteten Pfades.