6 papers
Uniqueness, analyticity and mixing for Gibbs point processes via spectral gaps
Andreas Göbel, Matthew Jenssen, Marcus Michelen +3
A Gibbs point process models particles interacting in the continuum through a potential. Among the most classical examples is the hard-sphere model, where given an activity paramet…
A simple proof of rapid mixing on random regular graphs beyond uniqueness
Andreas Göbel, Matthew Jenssen, Marcus Michelen +3
A recent breakthrough of Chen, Chen, Chen, Yin, and Zhang shows rapid mixing for Glauber dynamics for the hard-core model on random regular graphs beyond the tree uniqueness thresh…
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
Andreas Göbel, Janosch Ruff, Leon Schiller
We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, cliques of size approximately are randomly plant…
Information-Theoretic Thresholds for Bipartite Latent-Space Graphs under Noisy Observations
Andreas Göbel, Marcus Pappik, Leon Schiller
We study information-theoretic phase transitions for the detectability of latent geometry in bipartite random geometric graphs RGGs with Gaussian d-dimensional latent vectors while…
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions
Samuel Baguley, Andreas Göbel, Marcus Pappik +1
We study high-dimensional random geometric graphs (RGGs) of edge-density with vertices uniformly distributed on the -dimensional torus and edges inserted between sufficientl…