# Alon-Chung lemma

Let $G=(V,E)$ be a undirected graph of $n$ vertices such that the degree of each vertex is equal to $d$. Let $X$ be a subset of $V$. Then the number of edges in the subgraph^{} induced by $X$ is at most

$$\frac{1}{2n}\left(d{|X|}^{2}+\lambda |X|(n-|X|)\right)$$ |

where $\lambda $ is the second largest eigenvalue^{} of the adjacency matrix^{} of $G$.

Reference: N. Alon and F. R. K. Chung, “Explicit construction of linear sized tolerant networks,” Discrete Math., vol. 72, pp. 15-19, 1988.

Title | Alon-Chung lemma |
---|---|

Canonical name | AlonChungLemma |

Date of creation | 2013-03-22 17:26:47 |

Last modified on | 2013-03-22 17:26:47 |

Owner | kshum (5987) |

Last modified by | kshum (5987) |

Numerical id | 6 |

Author | kshum (5987) |

Entry type | Theorem |

Classification | msc 05C50 |