Post-graduate theses
Current Record: 48 of 127
|
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
|
Views |
988 |