Philipp Sprüssel
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Philipp Sprüssel has a total of 24 co-authors. Here are the top co-authors by number of shared publications:
- Mihyun Kang
Institute of Discrete Mathematics Graz University of Technology Graz Austria
11 shared publications Reinhard Diestel
5 shared publications- Oliver Cooley
Graz University of Technology
3 shared publications Agelos Georgakopoulos
2 shared publications- Agelos Georgakopoulos
Technische Universität Graz, Steyrergasse 30, 8010 Graz, Austria
2 shared publications Chris Dowden
2 shared publications
Latest Publications
- Open Access
- 1 July 2022
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 29 (3) , P3.27
Phase Transition in Cohomology Groups of Non-Uniform Random Simplicial Complexes
We consider a generalised model of a random simplicial complex, which arises from a random hypergraph. Our model is generated by taking the downward-closure of a non-uniform binomial random hypergraph, in which for each $k$, each set of $k+1$ vertices forms an edge with some probability $p_k$ independently. As a special case, this contains an extensively studied model of a (uniform) random simplicial complex, introduced by Meshulam and Wallach [Random Structures & Algorithms 34 (2009), no. 3, pp. 408–417].We consider a higher-dimensional notion of connectedness on this new model according to the vanishing of cohomology groups over an arbitrary abelian group $R$. We prove that this notion of connectedness displays a phase transition and determine the threshold. We also prove a hitting time result for a natural process interpretation, in which simplices and their downward-closure are added one by one. In addition, we determine the asymptotic behaviour of cohomology groups inside the critical window around the time of the phase transition.- 1 July 2022
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 29 (3) , P3.27
Open AccessPhase Transition in Cohomology Groups of Non-Uniform Random Simplicial Complexes
We consider a generalised model of a random simplicial complex, which arises from a random hypergraph. Our model is generated by taking the downward-closure of a non-uniform binomial random hypergraph, in which for each $k$, each set of $k+1$ vertices forms an edge with some probability $p_k$ independently. As a special case, this contains an extensively studied model of a (uniform) random simplicial complex, introduced by Meshulam and Wallach [Random Structures & Algorithms 34 (2009), no. 3, pp. 408–417].We consider a higher-dimensional notion of connectedness on this new model according to the vanishing of cohomology groups over an arbitrary abelian group $R$. We prove that this notion of connectedness displays a phase transition and determine the threshold. We also prove a hitting time result for a natural process interpretation, in which simplices and their downward-closure are added one by one. In addition, we determine the asymptotic behaviour of cohomology groups inside the critical window around the time of the phase transition. - 13 January 2020
- Published by Wiley in Random Structures & Algorithms
- Vol. 56 (4) , 1117-1170
Phase transitions in graphs on orientable surfaces
Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erdős‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces.
- 13 January 2020
- Published by Wiley in Random Structures & Algorithms
- Vol. 56 (4) , 1117-1170
Phase transitions in graphs on orientable surfaces
Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erdős‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces.
- 23 April 2019
- Published by Wiley in Random Structures & Algorithms
- Vol. 56 (2) , 461-500
Vanishing of cohomology groups of random simplicial complexes
We consider k‐dimensional random simplicial complexes generated from the binomial random (k + 1)‐uniform hypergraph by taking the downward‐closure. For 1 ≤ j ≤ k − 1, we determine when all cohomology groups with coefficients in from dimension one up to j vanish and the zero‐th cohomology group is isomorphic to . This property is not deterministically monotone for this model, but nevertheless we show that it has a single sharp threshold. Moreover we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. We also study the asymptotic distribution of the dimension of the j‐th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced by Linial and Meshulam, previously only known for dimension two.
- 23 April 2019
- Published by Wiley in Random Structures & Algorithms
- Vol. 56 (2) , 461-500
Vanishing of cohomology groups of random simplicial complexes
We consider k‐dimensional random simplicial complexes generated from the binomial random (k + 1)‐uniform hypergraph by taking the downward‐closure. For 1 ≤ j ≤ k − 1, we determine when all cohomology groups with coefficients in from dimension one up to j vanish and the zero‐th cohomology group is isomorphic to . This property is not deterministically monotone for this model, but nevertheless we show that it has a single sharp threshold. Moreover we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. We also study the asymptotic distribution of the dimension of the j‐th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced by Linial and Meshulam, previously only known for dimension two.
- Open Access
- 12 January 2018
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 25 (1) , P1.34
Symmetries of Unlabelled Planar Triangulations
We derive a decomposition scheme of unlabelled triangulations rooted at a single cell, where the decomposition depends on whether the automorphism group of the triangulation contains reflections, rotations, or both. Furthermore, the decomposition scheme is constructive in the sense that for each of the three cases, there is a $k\in\mathbb{N}$ such that the scheme defines a one-to-$k$ correspondence between the respective triangulations and their decompositions.- 12 January 2018
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 25 (1) , P1.34
Open AccessSymmetries of Unlabelled Planar Triangulations
We derive a decomposition scheme of unlabelled triangulations rooted at a single cell, where the decomposition depends on whether the automorphism group of the triangulation contains reflections, rotations, or both. Furthermore, the decomposition scheme is constructive in the sense that for each of the three cases, there is a $k\in\mathbb{N}$ such that the scheme defines a one-to-$k$ correspondence between the respective triangulations and their decompositions. - Open Access
- 12 January 2018
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 25 (1) , P1.30
Cubic Graphs and Related Triangulations on Orientable Surfaces
Let $\mathbb{S}_g$ be the orientable surface of genus $g$ for a fixed non-negative integer $g$. We show that the number of vertex-labelled cubic multigraphs embeddable on $\mathbb{S}_g$ with $2n$ vertices is asymptotically $c_g n^{5/2(g-1)-1}\gamma^{2n}(2n)!$, where $\gamma$ is an algebraic constant and $c_g$ is a constant depending only on the genus $g$. We also derive an analogous result for simple cubic graphs and weighted cubic multigraphs. Additionally, for $g\ge1$, we prove that a typical cubic multigraph embeddable on $\mathbb{S}_g$ has exactly one non-planar component.- 12 January 2018
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 25 (1) , P1.30
Open AccessCubic Graphs and Related Triangulations on Orientable Surfaces
Let $\mathbb{S}_g$ be the orientable surface of genus $g$ for a fixed non-negative integer $g$. We show that the number of vertex-labelled cubic multigraphs embeddable on $\mathbb{S}_g$ with $2n$ vertices is asymptotically $c_g n^{5/2(g-1)-1}\gamma^{2n}(2n)!$, where $\gamma$ is an algebraic constant and $c_g$ is a constant depending only on the genus $g$. We also derive an analogous result for simple cubic graphs and weighted cubic multigraphs. Additionally, for $g\ge1$, we prove that a typical cubic multigraph embeddable on $\mathbb{S}_g$ has exactly one non-planar component. - 1 January 2018
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 32 (1) , 695-727
The Evolution of Random Graphs on Surfaces
For integers $g,m \geq 0$ and $n>0$, let $S_{g}(n,m)$ denote the graph taken uniformly at random from the set of all graphs on $\{1,2, \ldots, n\}$ with exactly $m=m(n)$ edges and with genus at most $g$. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of $S_{g}(n,m)$, finding that there is often different asymptotic behavior depending on the ratio $\frac{m}{n}$. In our main results, we show that the probability that $S_{g}(n,m)$ contains any given nonplanar component converges to 0 as $n \to \infty$ for all $m(n)$, the probability that $S_{g}(n,m)$ contains a copy of any given planar graph converges to 1 as $n \to \infty$ if $\liminf \frac{m}{n} > 1$, the maximum degree of $S_{g}(n,m)$ is $\Theta (\ln n)$ with high probability if $\liminf \frac{m}{n} > 1$, and the largest face size of $S_{g}(n,m)$ has a threshold around $\frac{m}{n}=1$, where it changes from $\Theta (n)$ to $\Theta (\ln n)$ with high probability.- 1 January 2018
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 32 (1) , 695-727
The Evolution of Random Graphs on Surfaces
For integers $g,m \geq 0$ and $n>0$, let $S_{g}(n,m)$ denote the graph taken uniformly at random from the set of all graphs on $\{1,2, \ldots, n\}$ with exactly $m=m(n)$ edges and with genus at most $g$. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of $S_{g}(n,m)$, finding that there is often different asymptotic behavior depending on the ratio $\frac{m}{n}$. In our main results, we show that the probability that $S_{g}(n,m)$ contains any given nonplanar component converges to 0 as $n \to \infty$ for all $m(n)$, the probability that $S_{g}(n,m)$ contains a copy of any given planar graph converges to 1 as $n \to \infty$ if $\liminf \frac{m}{n} > 1$, the maximum degree of $S_{g}(n,m)$ is $\Theta (\ln n)$ with high probability if $\liminf \frac{m}{n} > 1$, and the largest face size of $S_{g}(n,m)$ has a threshold around $\frac{m}{n}=1$, where it changes from $\Theta (n)$ to $\Theta (\ln n)$ with high probability.- 1 August 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 61, 687-693
Evolution of the giant component in graphs on orientable surfaces
- 1 August 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 61, 687-693
Evolution of the giant component in graphs on orientable surfaces
- 1 August 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 61, 279-285
Homological connectedness of random hypergraphs
- 1 August 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 61, 279-285
Homological connectedness of random hypergraphs
- 1 August 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 61, 367-373
The evolution of random graphs on surfaces
- 1 August 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 61, 367-373
The evolution of random graphs on surfaces
- 1 November 2015
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 49, 587-594
Characterisation of symmetries of unlabelled triangulations
- 1 November 2015
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 49, 587-594
Characterisation of symmetries of unlabelled triangulations