Titel:	Combinatorial Aspects of Horizontal Visibility Graphs, Symmetric Edge- and Laplacian Polytopes
Autor(en):	Köhne, Daniel
ORCID des Autors:	https://orcid.org/0000-0002-9853-657X
Erstgutachter:	Prof. Dr. Martina Juhnke-Kubitzke
Zweitgutachter:	Prof. Dr. Benjamin Nill
Zusammenfassung:	In this thesis we study three main objects; horizontal visibility graphs (HVGs for short), symmetric edge polytopes and Laplacian polytopes. Chapters 2 and 3 focus on HVGs. In particular, we show that HVGs corresponding to a time series of length N of pairwise distinct and arbitrary data points are counted by the (N-1)st Catalan number and the (N-2)nd Schröder number, respectively. Moreover, extending previous work by Lacasa and Luque, we prove that HVGs associated to data sequences without equal entries are completely determined by their ordered degree sequence. Additionally, we provide an algorithm, which extends the fast horizontal visibility algorithm of Zhu et al. (2012). The extended version remains in O(N) in the worst case, works efficiently on streamed data, and is parallelizable. This approach enables the computation of HVGs with millions of vertices in a short period, opening up new application areas of HVGs for time series generated batch-wise or resulting from measurements with a high sampling rate. In Chapter 4, we then focus on the symmetric edge polytope associated to a simple graph. We study their $\gamma$-vectors, which are associated with their $h^*$-vectors, both from a deterministic and a probabilistic point of view. On the deterministic side, we prove non-negativity of $\gamma_1$ and $\gamma_2$ for any graph and completely characterize the case when $\gamma_2=0$. On the probabilistic side, we show that the $\gamma$-vectors of symmetric edge polytopes of most Erdős-Rényi random graphs are asymptotically almost surely non-negative up to any fixed entry. This proves that Gal's conjecture holds asymptotically almost surely for arbitrary unimodular triangulations in this setting. In the last chapter of this thesis, we focus on Laplacian polytopes associated to simplicial complexes. Given a (finite) simplicial complex, we define its i-th Laplacian polytope as the convex hull of the columns of its i-th Laplacian matrix. This extends Laplacian simplices of finite simple graphs, as introduced by Braun and Meyer. After studying basic properties of these polytopes, we focus on the d-th Laplacian polytope of the boundary of a (d+1)-simplex $\partial(\sigma_{d+1})$. If d is odd, then as for graphs, the d-th Laplacian polytope turns out to be a (d+1)-simplex in this case. If d is even, we show that the d-th Laplacian polytope of $\partial(\sigma_{d+1})$ is combinatorially equivalent to a d-dimensional cyclic polytope on d+2 vertices. Moreover, we provide an explicit regular unimodular triangulation for the d-th Laplacian polytope of $\partial(\sigma_{d+1})$. This enables us to compute the normalized volume and to show that the $h^\ast$-polynomial is real-rooted and unimodal, if $d$ is odd and even, respectively.
URL:	https://doi.org/10.48693/347 https://osnadocs.ub.uni-osnabrueck.de/handle/ds-202307069227
Schlagworte:	convex polytopes; horizontal visibility graphs; symmetric edge polytope; laplacian polytope; ehrhart theory; h-star vector; gamma vector; combinatorics; h-star polynomial
Erscheinungsdatum:	6-Jul-2023
Lizenzbezeichnung:	Attribution-NonCommercial 3.0 Germany
URL der Lizenz:	http://creativecommons.org/licenses/by-nc/3.0/de/
Publikationstyp:	Dissertation oder Habilitation [doctoralThesis]
Enthalten in den Sammlungen:	FB06 - E-Dissertationen

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons