Combinatorial Aspects of Horizontal Visibility Graphs, Symmetric Edge- and Laplacian Polytopes
Creators: name: Köhne, Daniel
Publisher: name: Universität Osnabrück
Year: 2023
Subjects: subject: convex polytopes
subject: horizontal visibility graphs
subject: symmetric edge polytope
subject: laplacian polytope
subject: ehrhart theory
subject: h-star vector
subject: gamma vector
subject: combinatorics
subject: h-star polynomial
subject: 510 - Mathematik
subject: 31.12 - Kombinatorik, Graphentheorie
subject: 31.50 - Geometrie: Allgemeines
subject: 31.59 - Geometrie: Sonstiges
subject: 31.00 - Mathematik: Allgemeines

description: 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.