Institute of
Discrete Mathematics and Geometry



Arbeitsgemeinschaft Diskrete Mathematik

Info: Das Seminar AGDM wird gemeinsam mit Kollegen der Universität Wien veranstaltet.

Die Arbeitsgemeinschaft findet wie immer 15:15-16:45 statt, allerdings (!!!!!) auf Grund der aktuellen Coronakrise online via Zoom statt..

Ort: Online via Zoom


Aktueller Termin



Zeit: Dienstags, 15.15 - 16.45h,

Datum: 12.1.2021
Titel: "Compacted binary trees and minimal automata admit stretched exponentials"
Vortragender: Michael Wallner (TU Wien)



Inhalt: A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size n is asymptotically equal to Theta( n! 4^n e^(3 a_1 n^(1/3)) n^(3/4) ), where a_1 is the largest root of the Airy function and approximately equal to -2.338. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity for computing the number of compact trees of a given size. We use empirical methods to estimate the values of all terms defined by the recurrence. Then we prove by induction that these estimates are sufficiently accurate for large n to determine the asymptotic form of the number of compacted trees. Our method also allows to enumerate minimal finite automata recognizing a finite language on a binary alphabet. This again shows the appearance of a stretched exponential. This is joint work with Andrew Elvey Price and Wenjie Fang.


 

Vorträge in früheren Jahren

Übersicht: Vorträge Zeitraum 2005 - 2020


Bereits gehaltene Vorträge

Datum: 1.12.2020
Titel: "Weight-preserving bijections between integer partitions and a family of alternating sign trapezoids"
Vortragende: Hans Höngesberg (Universität Wien)

Datum: 24.11.2020
Titel: "Basic hypergeometric proofs of two quadruple equidistributions of Euler-Stirling statistics on ascent sequences"
Vortragende: Michael Schlosser (Universität Wien)

Datum: 17.11.2020
Titel: "Geometric Dominating Sets - A minimum version of the No-3-In-Line problem and related problems "
Vortragende: Eva-Maria Hainzl (TU Wien)

Datum: 10.11.2020
Titel: "qRSt: A probabilistic Robinson-Schensted correspondence for Macdonald polynomials"
Vortragende: Florian Aigner (Universite de Quebec a Montreal)

Datum: 3.11.2020
Titel: "Cut vertices in random planar maps"
Vortragende: Benedikt Stufler (TU Wien)

Datum: 27.10.2020
Titel: "A refinement of the Murnaghan-Nakayama rule by descents for border strip tableaux"
Vortragende: Stephan Pfannerer-Mittas (TU Wien)

Datum: 20.10.2020
Titel: "Bounded Dyck paths, bounded alternating sequences, and reciprocity laws"
Vortragende: Christian Krattenthaler (Universität Wien)