Existence of Small Separators Depends on Geometry for Geometric Inhomogeneous Random Graphs

We show that Geometric Inhomogeneous Random Graphs (GIRGs) with power law weights may either have or not have separators of linear size, depending on the underlying geometry. While it was known that for Euclidean geometry it is possible to split the giant component into two linear size components by removing at most n^{1-\eps} edges, we show that this is impossible if the geometry is given by the minimum component distance.

• Publication year

  2017

• Venue

  arXiv: Combinatorics

• Publication date

  2017-11-10

• Fields of study

  Mathematics

• Identifiers
  arXiv 1711.03814
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane

  2018cited by this paper
• Explosion and distances in scale-free percolation

  2017cited by this paper
• Spectral Gap of Random Hyperbolic Graphs and Related Parameters

  2016cited by this paper
• Random Graphs and Complex Networks

  2016cited by this paper
• Bootstrap percolation on geometric inhomogeneous random graphs

  2016cited by this paper
• Greedy Routing and the Algorithmic Small-World Phenomenom

  2016cited by this paper
• Average Distance in a General Class of Scale-Free Networks with Underlying Geometry

  2016cited by this paper
• Hyperbolic Random Graphs: Separators and Treewidth

  2016influential reference
• On the Largest Component of a Hyperbolic Model of Complex Networks

  2015cited by this paper
• University of Birmingham Clustering and the hyperbolic geometry of complex networks

  2015cited by this paper
• An Extension of Mcdiarmid's Inequality

  2015cited by this paper
• Cliques in Hyperbolic Random Graphs

  2015cited by this paper
• Sampling Geometric Inhomogeneous Random Graphs in Linear Time

  2015cited by this paper
• Bootstrap percolation and the geometry of complex networks

  2014cited by this paper
• A Bound for the Diameter of Random Hyperbolic Graphs

  2014cited by this paper
• Inhomogeneous Long-Range Percolation for Real-Life Network Modeling

  2014cited by this paper
• Network Mapping by Replaying Hyperbolic Growth

  2012cited by this paper
• Random Hyperbolic Graphs: Degree Sequence and Clustering - (Extended Abstract)

  2012cited by this paper
• Sustaining the Internet with Hyperbolic Mapping

  2010cited by this paper
• Hyperbolic Geometry of Complex Networks

  2010cited by this paper
• Concentration of Measure for the Analysis of Randomized Algorithms

  2009cited by this paper
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces

  2008cited by this paper
• Navigating ultra-small worlds in ultra-short time

  2008cited by this paper
• Navigability of Complex Networks

  2007cited by this paper
• Complex Graphs and Networks

  2006cited by this paper
• The phase transition in inhomogeneous random graphs

  2005influential reference
• Bisecting sparse random graphs

  2001influential reference
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• An approximation theorem for the Poisson binomial distribution.

  1960influential reference
• Annales de l'Institut Henri Poincaré

  1931cited by this paper

• Expanders in Models of Social Networks

  2025influential citation
• Expressivity of Geometric Inhomogeneous Random Graphs - Metric and Non-Metric

  2024cites this paper
• Sublinear Cuts are the Exception in BDF-GIRGs

  2024influential citation
• Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models

  2024influential citation
• Balanced Bidirectional Breadth-First Search on Scale-Free Networks

  2024cites this paper
• Maximal Cliques in Scale-Free Random Graphs

  2023cites this paper
• Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs

  2020cites this paper
• Geometric Inhomogeneous Random Graphs and Graph Coloring Games

  2018cites this paper
• Geometric Inhomogeneous Random Graphs

  2015cites this paper