Exceptional rotations of random graphs: a VC theory

Louigi Addario-Berry, Shankar Bhamidi, Sébastien Bubeck, Luc Devroye, Gábor Lugosi, Roberto Imbuzeiro OliveiraJMLR 2015

TL;DR

This paper introduces a novel framework for studying "atypical" behaviors in random graph ensembles, inspired by Vapnik-Chervonenkis (VC) theory. By analyzing how graph properties like clique number, chromatic number, and connectivity deviate from their typical behavior as the dimensionality of the underlying random structure increases, the authors establish fundamental threshold dimensions for these deviations.

What Problem Does This Paper Address?

The core problem this paper tackles is understanding the "richness" required in a random structure to observe behaviors that deviate significantly from the norm. Specifically, it asks how the dimensionality of the underlying random geometric objects (vectors in $\mathbb{R}^d$) influences the properties of the resulting random graphs. While the typical behavior of random graphs like Erdős-Rényi $G(n,p)$ is well-understood, this work explores the extremes – how to find graphs within a family of random graphs that exhibit unusual properties. This is analogous to how VC theory studies deviations of averages from their means, but applied to the more complex combinatorial structures of graphs. The authors aim to develop a "VC theory of random graphs" by quantifying the dimensional thresholds at which exceptional behaviors emerge for fundamental graph properties.

Methods

The paper introduces a random graph process $G_{d,p}(X_n)$ indexed by unit vectors in $\mathbb{R}^d$. For a set of $n$ points $X_n$ in $\mathbb{R}^d$, and a unit vector $s \in S^{d-1}$ and a threshold $t$, a graph $\Gamma(X_n, s, t)$ is formed where an edge exists between two vertices $i$ and $j$ if their corresponding random vectors $X_{i,j}$ have a dot product with $s$ greater than or equal to $t$. By varying $s$, one can generate a collection of random graphs.

The authors then investigate three key graph properties:

  1. Clique Number: The size of the largest complete subgraph.
  2. Chromatic Number: The minimum number of colors needed for a proper vertex coloring.
  3. Connectivity: Whether the graph is connected.

For each property, they establish upper and lower bounds on the "threshold dimension" $d$. This dimension dictates when "exceptional directions" (specific choices of $s$) lead to atypical graph properties. The proofs combine techniques from:

  • VC Theory: Concepts like shattering, covering, packing, and symmetrization are adapted.
  • High-Dimensional Random Geometry: Leveraging properties of random vectors and hyperplanes in high dimensions.
  • Probabilistic Method: Using tools like the second moment method and Chernoff bounds.
  • Concentration Inequalities: For bounding deviations of random variables.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of random graph models rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Dimensionality as a Control Knob: The dimension $d$ of the ambient space acts as a crucial parameter controlling the "richness" of the random graph ensemble. Increasing $d$ allows for more diverse graph structures to emerge from the same underlying random process.
  • Asymmetry in Deviations: A striking finding is the asymmetry between "supercritical" (property typically obtains) and "subcritical" (property typically does not obtain) regimes for deviations. For instance, achieving significantly larger cliques or chromatic numbers often requires much higher dimensions than achieving significantly smaller ones.
  • Threshold Dimensions: The paper rigorously quantifies the dimensional thresholds for these exceptional behaviors. These thresholds are often polynomial or logarithmic in $n$, revealing how quickly dimensionality can unlock atypical graph structures.
  • VC Theory Analogy: The successful application of VC-style arguments to graph properties highlights a powerful new avenue for analyzing complex combinatorial objects.

Key Results

The paper presents four theorems for each of the three properties (clique number, chromatic number, connectivity), detailing upper and lower bounds for the threshold dimension in both subcritical and supercritical regimes.

  • Clique Number:
    • To find graphs with significantly larger cliques (e.g., $3 \log_2 n$), $d$ needs to be on the order of $(\log n)^2 / \log \log n$.
  • To find graphs with significantly smaller cliques (e.g., $\omega - 3$), $d$ needs to be on the order of $n^2$.
  • Chromatic Number:
    • To find graphs with significantly larger chromatic numbers, $d$ needs to be on the order of $n^2$.
  • To find graphs with significantly smaller chromatic numbers, $d$ needs to be on the order of $n$.
  • Connectivity:
    • For $p = c \log n / n$ with $c > 1$ (supercritical regime), to find a disconnected graph, $d$ needs to be on the order of $(c-1) \log n / \log \log n$.
  • For $p = c \log n / n$ with $c < 1$ (subcritical regime), to find a connected graph, $d$ needs to be on the order of $n^{1-c}$.

Limitations and Future Work

  • Conjectures: While lower bounds for connectivity in the subcritical regime are established ($d \gtrsim n^{1-c}$), matching upper bounds are not yet proven. The authors suspect these lower bounds might be sharp.
  • Generalizations: The paper focuses on specific parameters ($p=1/2$ for clique/chromatic number, $p=c \log n / n$ for connectivity). Extending the results to a wider range of $p$ values and other graph properties would be valuable.
  • Combinatorial Geometry Connection: The authors suggest exploring the relationship between the combinatorial geometry of the graph classes and their complexity.
  • Other Graph Properties: Investigating other graph properties (e.g., diameter, spectral gap) within this VC-theoretic framework is a natural next step.

Summary updated

BibTeX
@article{addarioberry2015exceptional,
  author = {Louigi Addario-Berry and Shankar Bhamidi and Sébastien Bubeck and Luc Devroye and Gábor Lugosi and Roberto Imbuzeiro Oliveira},
  title = {{Exceptional rotations of random graphs: a VC theory}},
  journal = {J. Mach. Learn. Res.},
  year = {2015},
}
Figure