1. osnaDocs
  2. Fachbereich 06 - Mathematik / Informatik / Physik
  3. FB06 - E-Dissertationen

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

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
https://doi.org/10.48693/347
Open Access logo originally created by the Public Library of Science (PLoS)
Langanzeige der Metadaten
DC ElementWertSprache
dc.contributor.advisorProf. Dr. Martina Juhnke-Kubitzkeger
dc.creatorKöhne, Daniel-
dc.date.accessioned2023-07-06T13:03:54Z-
dc.date.available2023-07-06T13:03:54Z-
dc.date.issued2023-07-06T13:03:54Z-
dc.identifier.urihttps://doi.org/10.48693/347-
dc.identifier.urihttps://osnadocs.ub.uni-osnabrueck.de/handle/ds-202307069227-
dc.description.abstractIn 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.eng
dc.rightsAttribution-NonCommercial 3.0 Germany*
dc.rights.urihttp://creativecommons.org/licenses/by-nc/3.0/de/*
dc.subjectconvex polytopeseng
dc.subjecthorizontal visibility graphseng
dc.subjectsymmetric edge polytopeeng
dc.subjectlaplacian polytopeeng
dc.subjectehrhart theoryeng
dc.subjecth-star vectoreng
dc.subjectgamma vectoreng
dc.subjectcombinatoricseng
dc.subjecth-star polynomialeng
dc.subject.ddc510 - Mathematikger
dc.titleCombinatorial Aspects of Horizontal Visibility Graphs, Symmetric Edge- and Laplacian Polytopeseng
dc.typeDissertation oder Habilitation [doctoralThesis]-
thesis.locationOsnabrück-
thesis.institutionUniversität-
thesis.typeDissertation [thesis.doctoral]-
thesis.date2023-07-04-
orcid.creatorhttps://orcid.org/0000-0002-9853-657X-
dc.contributor.refereeProf. Dr. Benjamin Nillger
dc.subject.bk31.12 - Kombinatorik, Graphentheorieger
dc.subject.bk31.50 - Geometrie: Allgemeinesger
dc.subject.bk31.59 - Geometrie: Sonstigesger
dc.subject.bk31.00 - Mathematik: Allgemeinesger
Enthalten in den Sammlungen:FB06 - E-Dissertationen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
thesis_koehne.pdfPräsentationsformat4,58 MBAdobe PDF
thesis_koehne.pdf
Miniaturbild
Öffnen/Anzeigen
Zur Kurzanzeige


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