Expandéry

Úkol: Dejte první a druhé největší vlastní číslo ( $ \lambda_{1},\lambda_{2}$) matice incidence $ d$-regulárního grafu s $ n$ vrcholy do souvislosti s následujícím výrazem:

$\displaystyle E=\min_{\ssty W\subset V(G)\atop\ssty 0<\vert W\vert\le\frac{1}{2}n} \frac{\vert W\cup\{v\vert\exists w\in W, (vw)\in E(G)\}\vert}{\vert W\vert}\,.$ (44)

Použijte výsledek příkladu 7.10.

Výraz za znakem minima je poměr počtu vrcholů ve $ W$ plus jejich přímých sousedů ku $ \vert W\vert$. Je tedy nasnadě, proč se grafy, pro něž je výraz 44 ,,velký'', nazývají expandéry.


Řešení: Proveďme nejprve přímočarou úpravu

$\displaystyle E=1+\min_{\ssty W\subset V(G)\atop \ssty 0<\vert W\vert\le\frac{1...
...rac{\vert\{v\not\in W\vert\exists w\in W, (vw)\in
E(G)\}\vert}{\vert W\vert}\,.$

Označme $ n_W$ počet vrcholů ležících mimo $ W$, které jsou ale spojeny hranou s nějakým vrcholem z $ W$. Toto číslo lze odhadnout pomocí počtu hran $ h_W$ mezi $ W$ a ostatními vrcholy. Pokud u nějakého vrcholu z $ W$ nějaká hrana ,,neuteče'' jinam, než do $ V(G)\setminus W$ (tedy pokud jsou $ W$, $ V(G)\setminus W$ partity grafu), bude $ h_W=n_Wd$. Jinak bude samozřejmě $ h_W<n_Wd$, tedy

\begin{multline*}
E\ge 1+\min_{\ssty W\subset V(G)\atop\ssty 0<\vert W\vert\le\...
...}
\frac{(\lambda_1-\lambda_2)\vert V(G)\setminus W\vert}{dn}\,.
\end{multline*}

Nalezli jsme tedy odhad

$\displaystyle E\ge 1+\frac{\lambda_1-\lambda_2}{2d}=
\frac{3}{2}-\frac{\lambda_2}{2\lambda_1}\,.$

$ \ast$DK$ \ast$