A Note on Degenerate and Spectrally Degenerate Graphs

Noga AlonJ. Graph Theory 2013 · DOI

TL;DR

This paper tackles a question about the relationship between a graph's "degeneracy" (a measure of how sparse its subgraphs are) and its "spectral radius" (related to its largest eigenvalue). The authors prove that it's possible to construct graphs that are "spectrally degenerate" but still have arbitrarily large minimum degrees, settling a conjecture in the field.

What Problem Does This Paper Address?

Graph theory often studies properties related to how "connected" or "dense" a graph is. Two such properties are degeneracy and spectral radius. A graph is d-degenerate if every one of its subgraphs has at least one vertex with degree at most d. The spectral radius of a graph is the largest eigenvalue of its adjacency matrix, which is related to how "spread out" information can travel on the graph.

A known result (Proposition 1.1) states that if a graph can be oriented such that every vertex has a small outdegree and indegree, its spectral radius is bounded. This implies that d-degenerate graphs with bounded maximum degree are also spectrally degenerate (meaning their spectral radius is bounded by a function of d and the maximum degree).

The central question this paper addresses is whether there's a fundamental limit to how large a graph's minimum degree can be if it's spectrally d-degenerate. Specifically, the authors investigate if there exists a function f(d) such that any spectrally d-degenerate graph must contain a vertex of degree at most f(d). This is a question about whether spectral degeneracy "forces" a certain level of sparseness in terms of minimum degree. The paper proves that no such universal function f(d) exists, meaning we can construct spectrally degenerate graphs with arbitrarily high minimum degrees.

Methods

The paper employs a probabilistic construction method, building upon techniques from previous work ([3], [6]). The core idea is to construct a bipartite graph with specific properties.

  1. Probabilistic Construction: A bipartite graph G is constructed with vertex classes A and B. Vertices in A are given a fixed degree (M), while vertices in B are assigned degrees that are probabilistically large. This construction is designed to satisfy certain degree conditions and, crucially, to have subgraphs with high average degrees that still contain vertices of very high degrees.
  2. Coloring Argument (Lovász Local Lemma): To prove the spectral degeneracy property, the authors use a clever edge-coloring argument. They show that any subgraph H of the constructed graph G can be colored with two colors (red and green) such that:
  3. The red edges form a graph where vertices in one partition (A) have small degrees (at most 10).
  4. The green edges form a graph where vertices in the other partition (B) have small degrees (at most D/100, where D is the maximum degree of H). This coloring is achieved by a process that iteratively colors vertices and their incident edges, guided by degree constraints. The proof that this process always terminates and yields the desired coloring relies on the Lovász Local Lemma, a powerful tool for proving the existence of objects with many mutually independent properties.

  5. Spectral Bounds: The spectral radius of the original graph H is then bounded by combining the spectral bounds of the red-subgraph (which is d-degenerate) and the green-subgraph (which has bounded degrees in one partition).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Spectral Degeneracy Doesn't Imply Low Minimum Degree: The most significant insight is that spectral degeneracy, while related to sparsity, does not inherently restrict the minimum degree of a graph. This directly answers a question posed by Dvořák and Mohar.
  • Constructing "Dense" Sparse Graphs: The paper demonstrates how to build graphs that are spectrally degenerate (meaning their eigenvalues are controlled) but still possess arbitrarily high minimum degrees. This is achieved through a careful probabilistic construction.
  • Power of Edge Coloring for Spectral Analysis: The use of a two-coloring argument, inspired by the Lovász Local Lemma, is a key technique. By partitioning the edges based on degree constraints in different vertex sets, the authors can effectively bound the spectral radius of the overall graph.
  • The "Worst Case" for Spectral Degeneracy: The construction highlights a scenario where a graph can be spectrally degenerate despite having no vertices with very low degrees, pushing the boundaries of what was previously thought possible.

Key Results

  • Theorem 1.2: For every positive integer M, there exists a spectrally 50-degenerate graph G in which every vertex has a degree of at least M. This is the main result, proving that no universal function f(d) limits the minimum degree for spectrally d-degenerate graphs.
  • Theorem 2.1: A probabilistic construction yields a bipartite graph with specific degree properties: vertices in one partition have degree M, vertices in the other have degrees larger than 1000M, and any subgraph with average degree at least 10 contains a vertex of degree at least 1000M.
  • Theorem 2.3: A graph constructed using Theorem 2.1 is shown to be spectrally 50-degenerate and has a minimum degree M. This theorem directly establishes the existence of graphs that are spectrally degenerate but have high minimum degrees.

Limitations and Future Work

  • Constant Optimization: The authors explicitly state that the constant "50" in "spectrally 50-degenerate" is not optimized and can be reduced. The focus was on proving the existence result rather than finding the tightest possible constant.
  • Generalization: While the paper focuses on bipartite graphs for construction, the implications extend to general graphs. Future work could explore tighter bounds or alternative constructions for general graphs.
  • Understanding the Constant: A deeper understanding of why the constant 50 arises and whether it can be significantly reduced would be a natural next step.
  • Algorithmic Implications: The paper is primarily theoretical. Investigating algorithmic consequences of these findings, such as efficient algorithms for detecting or constructing such graphs, could be a direction for future research.

Summary updated

BibTeX
@article{alon2013note,
  author = {Noga Alon},
  title = {{A Note on Degenerate and Spectrally Degenerate Graphs}},
  journal = {J. Graph Theory},
  year = {2013},
  doi = {10.1002/jgt.21627},
}
Figure