Combinatorial Aspects of Horizontal Visibility Graphs, Symmetric Edge- and Laplacian Polytopes

Please use this identifier to cite or link to this item:
Open Access logo originally created by the Public Library of Science (PLoS)
Title: Combinatorial Aspects of Horizontal Visibility Graphs, Symmetric Edge- and Laplacian Polytopes
Authors: Köhne, Daniel
ORCID of the author:
Thesis advisor: Prof. Dr. Martina Juhnke-Kubitzke
Thesis referee: Prof. Dr. Benjamin Nill
Abstract: 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.
Subject Keywords: convex polytopes; horizontal visibility graphs; symmetric edge polytope; laplacian polytope; ehrhart theory; h-star vector; gamma vector; combinatorics; h-star polynomial
Issue Date: 6-Jul-2023
License name: Attribution-NonCommercial 3.0 Germany
License url:
Type of publication: Dissertation oder Habilitation [doctoralThesis]
Appears in Collections:FB06 - E-Dissertationen

Files in This Item:
File Description SizeFormat 
thesis_koehne.pdfPräsentationsformat4,58 MBAdobe PDF

This item is licensed under a Creative Commons License Creative Commons