7.2. 独立集合の個数に対する弱いものの単純な下界

定理 7.1.3 を弱めると次の系が得られる:

系 7.2.1

\(n\) 個の頂点と \(m\) 個の辺を持つループレスな多重グラフを \(G\) とする。このとき、\(G\) は要素数が

\[ \dfrac{n^{2}}{n+2m} \]

以上の独立集合を持つ。

この系を証明するには、次の不等式が必要になる:

補題 7.2.2

\(a_{1},a_{2},\ldots,a_{n}\) を \(n\) 個の正の実数とするとき、次の不等式が成り立つ:

\[ \dfrac{1}{a_{1}}+\dfrac{1}{a_{2}}+\cdots+\dfrac{1}{a_{n}}\geq\dfrac{n^{2}}{a_{1}+a_{2}+\cdots+a_{n}} \]

[証明] いくかの証明が知られている¹:

Jensen の不等式 (Jensen's inequality) を凸関数 \(\mathbb{R}^{+}\rightarrow\mathbb{R}^{+},\ x\mapsto\dfrac{1}{x}\) に適用する。
Cauchy-Schwarz の不等式 (Cauchy-Schwarz inequality) を使う:

\[ \begin{aligned} & \left( a_{1}+a_{2}+\cdots+a_{n}\right) \left( \dfrac{1}{a_{1}}+\dfrac {1}{a_{2}}+\cdots+\dfrac{1}{a_{n}}\right) \\ & \qquad \geq\left( \underbrace{\sqrt{a_{1}\dfrac{1}{a_{1}}}+\sqrt{a_{2}\dfrac {1}{a_{2}}}+\cdots+\sqrt{a_{n}\dfrac{1}{a_{n}}}}_{=n}\right) ^{2}=n^{2} \end{aligned} \]
AM-HM 不等式 (AM-HM inequality) を使う。
AM-GM 不等式 (AM-GM inequality) を使う。
直接的な証明もある。この証明では次の有名な不等式が利用される:

\[ \dfrac{u}{v}+\dfrac{v}{u}\geq2 \qquad (5) \]

この不等式は任意の正の実数 \(u\), \(v\) に対して成り立つ。これは次の不等式から分かる:

\[ \dfrac{u}{v}+\dfrac{v}{u}-2=\dfrac{\left( u-v\right) ^{2}}{uv}\geq0 \]

ここから次が分かる:

\[ \begin{aligned} & \left( a_{1}+a_{2}+\cdots+a_{n}\right) \left( \dfrac{1}{a_{1}}+\dfrac {1}{a_{2}}+\cdots+\dfrac{1}{a_{n}}\right) \\ &\quad =\left( \sum_{i=1}^{n}a_{i}\right) \left( \sum_{j=1}^{n}\dfrac{1}{a_{j}}\right) =\sum_{i=1}^{n}\ \ \sum_{j=1}^{n}a_{i}\dfrac{1}{a_{j}}=\sum _{i=1}^{n}\ \ \sum_{j=1}^{n}\dfrac{a_{i}}{a_{j}}\\ &\quad =\dfrac{1}{2}\left( \sum_{i=1}^{n}\ \ \sum_{j=1}^{n}\dfrac{a_{i}}{a_{j}}+\sum_{i=1}^{n}\ \ \sum_{j=1}^{n}\dfrac{a_{i}}{a_{j}}\right) \qquad \left(\because\ \text{任意の } x \in \mathbb{R} \text{ で } x=\dfrac{1}{2}\left( x+x\right)\right) \\ &\quad =\dfrac{1}{2}\left( \sum_{i=1}^{n}\ \ \sum_{j=1}^{n}\dfrac{a_{i}}{a_{j}}+\sum_{j=1}^{n}\ \ \sum_{i=1}^{n}\dfrac{a_{j}}{a_{i}}\right) \qquad \left( \text{添え字を変更した} \right) \\ &\quad =\dfrac{1}{2}\left( \sum_{i=1}^{n}\ \ \sum_{j=1}^{n}\dfrac{a_{i}}{a_{j}}+\sum_{i=1}^{n}\ \ \sum_{j=1}^{n}\dfrac{a_{j}}{a_{i}}\right) \qquad \left( \text{和の順番を変更した}\right) \\ &\quad =\dfrac{1}{2}\sum_{i=1}^{n}\ \ \sum_{j=1}^{n}\underbrace{\left( \dfrac{a_{i}}{a_{j}}+\dfrac{a_{j}}{a_{i}}\right) }_{\substack{\geq 2\\[3pt](\because\ \text{式 } (5) \text{ より})}}\geq\dfrac{1}{2}\underbrace{\sum_{i=1}^{n}\ \ \sum_{j=1}^{n}2}_{=n^{2}\cdot2}=\dfrac{1}{2}n^{2}\cdot2=n^{2} \end{aligned} \]

これを変形すれば補題 7.2.2 を得る。□

[系 7.2.1 の証明] 多重グラフ \(G\) を \(G=\left( V,E,\varphi\right) \) と書く。このとき \(\left\vert V\right\vert =n\) と \(\left\vert E\right\vert =m\) が成り立つ。\(\left\vert V\right\vert =n\) より、一般性を失うことなく \(V=\left\{ 1,2,\ldots ,n\right\} \) と仮定する。このとき握手補題 (命題 2.4.3) より次の等式が成り立つ:

\[ \begin{aligned} \sum_{v=1}^{n}\deg v & = \sum_{v\in V}\deg v \\ & = 2\cdot\underbrace{\left\vert E\right\vert }_{=m} \qquad \left(\because\ \text{握手補題}\right) \\ & = 2m \end{aligned} \]

一方で定理 7.1.3 からは、\(G\) が次に示す大きさの独立集合を持つことが分かる:

\[ \begin{aligned} \sum_{v\in V}\dfrac{1}{1+\deg v} & = \sum_{v=1}^{n}\dfrac{1}{1+\deg v}\qquad \left(\because\ V=\left\{ 1,2,\ldots,n\right\} \right) \\ & \geq\dfrac{n^{2}}{\displaystyle \sum_{v=1}^{n}\left( 1+\deg v\right) } \qquad \left(\because\ \href{/graph/independent-set/weaker-but-simpler-lower-bound/#lem.indep.cauchy-lame}{\text{系 7.2.2}} \right) \\ & = \dfrac{n^{2}}{n+2m} \\ & \qquad \Bigl(\because\ \sum_{v=1}^{n}\left( 1+\deg v\right) =n+\underbrace{\sum_{v\in V}\deg v}_{=2m}=n+2m \Bigr) \end{aligned} \]

以上で系 7.2.1 は証明された。□

以降で説明なしに使われている用語については [Steele04] などの不等式に関する教科書を見てほしい (ただし、用語が完全に標準化されているわけではない。本書が「AM-HM 不等式」と呼ぶ不等式は [Steele04] で「HM-AM 不等式」と呼ばれる)。 ↩︎