Type of Work
Search command : Author="Στεφανίδης"
And Author="Κωνσταντίνος"
Current Record: 4 of 11

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 wellknown 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 farborescenses, i.e., acyclic spanning subgraphs of the above directed graph of P. Since farborescences 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 

Graphtheory 

Γεωμετρία 

Θεωρία γραφημάτων 
Issue date 
20210326 
Collection

School/DepartmentSchool of Sciences and EngineeringDepartment of Mathematics and Applied MathematicsPostgraduate theses


Type of Work

Permanent Link 
https://elocus.lib.uoc.gr//dlib/0/1/8/metadatadlib16182257473120544229.tkl

Views 
180 