E-Locus - Institutional Repository of the University of Crete

Type of Work

Technical reports	[13]	Publications	[15]
Graduate theses	[1446]	Conference Proceedings
Post-graduate theses	[5632]	Studies
Doctoral theses	[2221]	Studies programs
Various	[72]

Current Record: 13 of 23

[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