Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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)

Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs

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:   2024  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