Skip to main content Contents Prev Up Next \(\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\,}$}}}
\)
Section 6.5 Challenge Problems
For positive integers \(n\geq 2k\text{,}\) the Kneser graph \(K(n,k)\) is the graph with vertex set \(\binom{[n]}{k}\) where two vertices are adjacent if and only if they represent a pair of disjoint sets. Prove that \(\Theta(K(n,k))=\binom{n-1}{k-1}\) for all positive integers \(n\geq2k\text{.}\) (Note that this strengthens the Erdős–Ko–Rado Theorem).
