Eigenvalues of K1, k-Free Graphs and the Connectivity of Their Independence Complexes

Ron Aharoni, Noga Alon, Eli BergerJ. Graph Theory 2016 · DOI

TL;DR

This paper establishes new bounds on the largest eigenvalue of the Laplacian of $K_{1,k}$-free graphs and the topological connectivity of their independence complexes. These results offer improved estimates for the existence of independent transversals, a fundamental problem in graph theory with implications for combinatorial designs and theoretical computer science.

What Problem Does This Paper Address?

The paper tackles two main problems in graph theory:

  1. Bounding the Laplacian Eigenvalue: For a graph $G$ with maximum degree $d$, it's known that its largest Laplacian eigenvalue, $\lambda(G)$, is at most $2d$. This bound is tight for $d$-regular bipartite graphs. However, if $G$ is restricted to not contain an induced $K_{1,k}$ (a star graph with $k$ leaves), this upper bound can be improved. The authors aim to find a tighter upper bound for $\lambda(G)$ in $K_{1,k}$-free graphs.
  2. Connectivity of Independence Complexes: The independence complex $I(G)$ of a graph $G$ is a simplicial complex whose vertices are the independent sets of $G$. The connectivity of this complex, denoted by $\eta(I(G))$ or its homological counterpart $\eta_H(I(G))$, is a measure of its "hole-free" nature. Existing results provide lower bounds on this connectivity, often related to the graph's structure. The paper seeks to improve these lower bounds for $K_{1,k}$-free graphs, particularly by leveraging the results on Laplacian eigenvalues.

These problems are connected because improved bounds on the Laplacian eigenvalue can lead to better guarantees for the existence of independent transversals, which are sets of vertices that intersect every part of a given partition of the graph's vertex set exactly once.

Methods

The paper employs a combination of algebraic and combinatorial techniques:

  • Laplacian Eigenvalue Analysis: Theorem 1.1 uses a proof that involves manipulating the definition of the Laplacian eigenvalue and its corresponding eigenvector. It leverages the property that $K_{1,k}$-free graphs have a certain minimum number of edges in induced subgraphs of their neighborhoods, relating this to Turán's theorem. The proof involves summing contributions over triangles and edges, carefully bounding terms using the graph's properties.
  • Connectivity via Mayer-Vietoris Sequence: For the connectivity of independence complexes, the authors utilize a standard result based on the Mayer-Vietoris sequence for simplicial complexes. Lemma 1 states that for any complex $C$ and vertex $v$, $\eta_H(C) \geq \min(\eta_H(C-v), \eta_H(\text{link}_C(v)) + 1)$. This recursive relationship allows for the development of game-theoretic approaches (like the CON vs. NON game) to bound connectivity.
  • Game Theory for Connectivity: Theorem 2.3 introduces a game-theoretic framework, $\Psi(G)$, to bound the connectivity of $I(G)$. This game involves two players, CON (trying to show high connectivity) and NON (trying to thwart it), making "deletion" or "explosion" moves on the graph. The payoff of the game provides a lower bound for $\eta(I(G))$.
  • Inductive Constructions and Graph Properties: Theorem 2.6 uses an inductive argument to construct an eigenvector for the independence complex connectivity, leveraging the $K_{1,k}$-free property and properties of induced subgraphs.

Datasets

Not discussed in the paper. The paper deals with theoretical graph properties and does not rely on specific datasets for empirical evaluation.

Key Insights and Ideas

  • Tighter Laplacian Bounds for $K_{1,k}$-free Graphs: The paper shows that the maximum Laplacian eigenvalue of a $K_{1,k}$-free graph with maximum degree $d$ is strictly less than $2d$, specifically bounded by $2d - t(d,k)$, where $t(d,k)$ is related to Turán's theorem. This is a significant improvement over the general bound of $2d$.
  • Improved Connectivity Bounds: By combining their new Laplacian bounds with existing results on the connectivity of independence complexes, the authors derive improved lower bounds for $\eta_H(I(G))$ for $K_{1,k}$-free graphs.
  • Game-Theoretic Approach to Connectivity: The introduction of the $\Psi(G)$ game provides a novel and intuitive way to think about and bound the connectivity of independence complexes, connecting combinatorial game theory to topological properties of graph structures.
  • Connection to Independent Transversals: The improved bounds on Laplacian eigenvalues and connectivity directly translate to better guarantees for the existence of independent transversals in certain graph structures, particularly for $K_{1,k}$-free graphs.

Key Results

  • Theorem 1.1: For a $K_{1,k}$-free graph $G$ with maximum degree $d$, the largest Laplacian eigenvalue $\lambda(G)$ satisfies $\lambda(G) < 2d - t(d,k)$, where $t(d,k)$ is the minimum number of edges in a $d$-vertex graph with no independent set of size $k$. Asymptotically, this is $\lambda(G) \leq (2 - \frac{2}{k-1} + o(1))d$.
  • Theorem 2.3: The topological connectivity of the independence complex of a graph $G$, $\eta(I(G))$, is bounded below by $\Psi(G)$, a value derived from a game played on the graph.
  • Theorem 2.6: For a $K_{1,k}$-free graph $G$ on $n$ vertices with maximum degree $d$, $\eta_H(I(G)) \geq \frac{1}{2} \frac{k-1}{k} \frac{n}{d}$. This result is derived using a game-theoretic approach.
  • Corollaries and Applications: The paper derives corollaries that provide specific bounds for $\eta_H(I(G))$ and discusses how these results improve guarantees for the existence of independent transversals, particularly for $K_{1,k}$-free graphs. For instance, it implies that for such graphs, sets of size $(2 - \frac{2}{k-1} + o(1))d$ suffice for independent transversals.

Limitations and Future Work

  • Open Questions: The paper concludes by posing two open questions:
  • Is the estimate $\lambda(G) \leq (2 - \frac{2}{k-1} + o(1))d$ for $K_{1,k}$-free graphs tight?
  • Do the results for $K_{1,k}$-free graphs extend to graphs that contain no induced copy of $K_{k,k}$?
  • Potential for Further Improvement: The authors suggest that the constant $3/2$ in one of the applications (related to Steiner Triple Systems) might be reducible, possibly to $1/2$. They also pose a similar question for line graphs of simple graphs.
  • Generalization to $K_{k,k}$-free Graphs: The paper explicitly asks whether the derived bounds and theorems hold for the broader class of graphs that are $K_{k,k}$-free, indicating this as a natural direction for future research.

Summary updated

BibTeX
@article{aharoni2016eigenvalues,
  author = {Ron Aharoni and Noga Alon and Eli Berger},
  title = {{Eigenvalues of K1, k-Free Graphs and the Connectivity of Their Independence Complexes}},
  journal = {J. Graph Theory},
  year = {2016},
  doi = {10.1002/jgt.22004},
}
Figure