Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Monday, June 19, 2023, 04:15 pm

**Duration**: 30 minutes

**Location**: OAT S 13

**Speaker**: Leon Schiller (Hasso-Plattner Institute, Potsdam, Germany)

Random graph models are useful tools for bringing theoretical analyses of algorithms closer to empirical observations. One random graph model that particularly attracted the attention of researchers in this regard are geometric inhomogeneous random graphs (GIRGs) which were found to reproduce the characteristic properties of many realistic instances. This is achieved by randomly distributing n vertices in a d-dimensional torus and subsequently expressing the probability that two vertices are adjacent as a function of their heterogeneous weights and their distance. GIRGs can also be seen as a generalization of hyperbolic random graphs (HRGs) with the main novelty that the dimension of the underlying space is freely adjustable. In spite of this, it is still largely unexplored how this new parameter explicitly influences the properties of the resulting graphs. In this talk, we present first results that address this question and further complement existing research on the behavior of random geometric graphs (RGGs) in high dimensions. We prove that, in the infinite-dimensional limit, GIRGs lose their geometry, i.e., they converge in total variation distance to their non-geometric counterparts (Chung–Lu graphs) where edges are sampled independently of each other. To quantify how quickly this transition occurs and how it impacts important graph structures, we further study the number, size, and position of cliques and identify phase transitions at which their behavior changes fundamentally. Our analysis covers all relevant parameter regimes and generalizes the results of previous work regarding the clique structure of GIRGs. We conclude that geometric effects prevail as long as d is asymptotically smaller than log(n), which manifests in a large number of cliques forming among vertices of low weight. On the other hand, if d scales faster than log(n), the clique structure of our model behaves essentially like that of a Chung–Lu Graph, whereby slightly stronger results apply if d scales faster than log(n)^2. We conclude the talk by giving an overview of how our results compare to what is known for other geometric random graph models and by presenting further open questions and possible starting points for future research we identified.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login