\( \providecommand{\glspostdescription}{} \renewcommand{\glspostdescription}{} \def\cprime{\char"7E } \def\cdprime{\char"7F } \def\eoborotnoye{\char'013} \def\Eoborotnoye{\char'003} \newcommand{\beq}[1]{\begin{equation}\label{#1}} \newcommand{\eeq}{\end{equation}} \newcommand{\weakstar}{weak${}^*$ } \newcommand{\rng}{\operatorname{rng}} \newcommand{\ex}{\operatorname{ex}} \newcommand{\colex}{\prec_{\operatorname{colex}}} \newcommand{\lex}{\prec_{\operatorname{lex}}} \newcommand{\per}{\operatorname{per}} \newcommand{\permat}{\operatorname{pm}} \renewcommand{\hom}{\operatorname{hom}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\degree}{d} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Introduction

The purpose of this chapter is to bring together several beautiful techniques for analyzing independent sets in graphs. Specifically, how large of an independent set must a triangle-free graph contain? How many independent sets can there be in a $d$-regular graph with $n$ vertices? Also, at the end of the chapter, we will look at a nice connection between independent sets in graphs and questions about communicating over a noisy channel originating in information theory.

Prev Top Next