Font size: Αα Αα Αα hide gadgets
You are here: Defenses » Ιούνιος 2016 » Βασιλική Βελώνα
download defense details: { pdf }

MSc thesis defense presentation

Βασιλική Βελώνα defends her MSc thesis.

Date: Παρασκευή, 24 Ιούν 2016
Ώρα: 10:00-11:00
Location: Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών, Τμήμα Μαθηματικών, Α32
Thesis title: Asymptotic analysis of outerplanar graphs with subgraph obstructions

Thesis abstract

In this thesis we study techniques for combinatorial specification and asymptotic enumeration in the context of analytic combinatorics. Our guide through this variety of techniques is the enumeration of certain types of planar graphs, under subgraph exclusion constraints. In particular, we examine outerplanar graphs where the constraint is the exclusion of cycles of certain length. We build specifications for the 2-connected components that exclude certain cycles in order to obtain asymptotics for the general constrainded outerplanar class. The challenges here are combinatorial as well as computational, as the specifications become more involved when the length of the excluded cycle grows and the generating functions obtained are in implicit form. The combinatorial language that we use is the so-called Symbolic Method that comes in hand with corresponding analytic techniques. Furthermore, we study certain parameters of general outerplanar graphs, namely the number of triangles and quadrangles. We obtain Gaussian limiting distibutions and extract explicit constants for the mean and variance.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.