On a Cheeger type inequality in Cayley graphs of finite groups

Arindam BiswasEuropean Journal of Combinatorics 2019 · DOI · arXiv

TL;DR

This paper establishes a new bound on the spectral gap of Cayley graphs for finite groups, specifically relating the Cheeger constant to the eigenvalues of the adjacency operator. This provides a more precise understanding of how "connected" these graphs are, with implications for their use in areas like theoretical computer science and quantum computing.

What Problem Does This Paper Address?

The paper tackles the problem of understanding the "expansion" properties of Cayley graphs of finite groups. Cayley graphs are fundamental objects in group theory and are used to model various structures. A key measure of a graph's expansion is its spectral gap, which is related to the Cheeger constant. Previous work showed that for expander graphs, the spectral gap is bounded away from zero, implying good connectivity. However, explicit bounds were lacking, especially for the non-trivial eigenvalues of the adjacency operator. This paper aims to provide such explicit bounds, specifically for Cayley graphs of finite groups, and to connect them to the Cheeger constant.

Methods

The authors employ a proof strategy that combines combinatorial arguments with spectral graph theory. They leverage the definition of the Cheeger constant (both vertex and edge versions) and the properties of the normalized Laplacian and adjacency operators. A crucial part of their method involves constructing a specific subset $A$ within the group that exhibits certain expansion properties. This set $A$ is then used to construct a subgroup $H$ of index 2. The core of the proof relies on showing that if the Cayley graph has an eigenvalue close to -1 (indicating poor expansion), then this subgroup $H$ must be disjoint from the generating set $S$. This leads to a contradiction with the assumption that the graph is non-bipartite, thus establishing the desired spectral bound. They also utilize the discrete Cheeger-Buser inequality and properties of translates of sets within the group.

Datasets

Not discussed in the paper. The paper deals with theoretical constructions of graphs from finite groups, not empirical evaluation on datasets.

Key Insights and Ideas

  • Connecting Cheeger Constant to Spectral Bounds: The paper provides a concrete, quantitative link between the Cheeger constant (a combinatorial measure of expansion) and the spectral gap of the adjacency operator for Cayley graphs of finite groups.
  • Constructing Subgroups for Contradiction: A clever technique is used: assuming a "bad" eigenvalue (close to -1) allows the construction of a specific set $A$, which in turn leads to the construction of a subgroup $H$. The properties of $H$ then create a contradiction with the graph's non-bipartite nature.
  • Explicit Bounds: The paper moves beyond qualitative statements about expansion to provide explicit, calculable bounds on the eigenvalues, which are crucial for practical applications.
  • Non-Bipartite Focus: The results are specifically tailored for non-bipartite Cayley graphs, a common and important class of graphs in this context.

Key Results

The main result is Theorem 1.4, which states that for a non-bipartite Cayley graph $C(G, S)$ that is an expander with Cheeger constant $h(G)$, the non-trivial eigenvalues $\lambda$ of the adjacency operator $T$ satisfy:

$$ \lambda \ge -1 + \frac{\alpha h(G)^4}{d^2(d+1)^2} $$

where $d = |S|$ is the degree of the graph and $\alpha$ is an absolute constant (taken as 29). This provides a lower bound on the spectral gap, directly related to the graph's expansion property.

Limitations and Future Work

  • Constant $\alpha$: The constant $\alpha=29$ is stated as an absolute constant, but its precise derivation and potential for improvement are not deeply explored.
  • General Graphs: The results are specific to Cayley graphs of finite groups. Extending these bounds to more general finite graphs or other algebraic structures might be a direction for future research.
  • Dual Cheeger Constant: The paper briefly mentions the dual Cheeger constant and higher-order Cheeger constants, suggesting potential avenues for further investigation into these more generalized notions of graph expansion.
  • Practical Applications: While the theoretical implications are clear, the paper doesn't delve into specific applications where these precise bounds would be directly utilized, leaving room for future work in that direction.

Summary updated

BibTeX
@article{biswas2019cheeger,
  author = {Arindam Biswas},
  title = {{On a Cheeger type inequality in Cayley graphs of finite groups}},
  journal = {European Journal of Combinatorics},
  year = {2019},
  doi = {10.1016/j.ejc.2019.06.009},
}
Figure