Your browser does not support JavaScript!

Post-graduate theses

Current Record: 45 of 123

Back to Results Previous page
Next page
Add to Basket
[Add to Basket]
Identifier 000439132
Title Monotone paths on polytopes
Alternative Title Μονότονα μονοπάτια σε πολύτοπα
Author Αποστολάκης, Σήφης
Thesis advisor Τζανάκη, Ελένη
Reviewer Κολουντζάκης, Μιχαήλ
Φραντζικινάκης, Νικόλαος
Abstract This thesis consists of three parts. The first part, Chapter 1, includes a brief introduction to convex polytopes, basic definitions and background. In detail, we provide the two equivalent definitions of a convex polytope and, after a short discussion on algorithmic considerations, we present some examples of well-known and widely studied polytopes. In the second part, Chapter 2, we present and prove three important results on polytope theory; Euler’s formula, the Upper Bound Theorem and the Lower Bound Theorem. Finally, in Chapter 3, we present part of the results from a recent paper by C.A. Athanasiadis, J. De Loera and Z. Zhang [3]. More explicitly, we encounter some enumerative problems, the nature of which has to do with counting monotone paths and subgraphs of the graph of a polytope, structures strongly related to linear programming and the simplex method. More precisely, we firstly consider the problem of counting the maximum and the minimum number of monotone paths induced on the directed graph of a polytope P from a linear functional in general position with respect to P. We then consider f-arborescenses, i.e., acyclic spanning subgraphs of the above directed graph of P. Since f-arborescences can be thought of as equivalence groups of pivot rules on the simplex algorithm, estimating upper and lower bounds of their number gives an estimate of the size of the simplex method. We would like to thank Christos Athanasiadis for making article [3] available in a preliminary form
Language English
Subject Geometry
Graph-theory
Γεωμετρία
Θεωρία γραφημάτων
Issue date 2021-03-26
Collection   School/Department--School of Sciences and Engineering--Department of Mathematics and Applied Mathematics--Post-graduate theses
  Type of Work--Post-graduate theses
Permanent Link https://elocus.lib.uoc.gr//dlib/0/1/8/metadata-dlib-1618225747-312054-4229.tkl Bookmark and Share
Views 958

Digital Documents
No preview available

Download document
View document
Views : 4