1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

グラフ理論の問題: 〜を含まないグラフの〜を求めよ

Last updated at Posted at 2020-09-23

問題

任意の$t\geq 2$に対して、$K_{2,t}$を部分グラフとして含まないグラフの最大辺数が次式以下であることを証明せよ。
$$\frac{1}{2}(\sqrt{t-1}n^{3/2}+n)$$

解法

解法を見る

 問題の条件を満たすグラフを$G=(V,E)$とする。$G$に含まれる以下のような部分グラフを考え、これを順序列$M=(v, \{u_1, u_2\})$で表す。$G$に含まれる$M$の数を2通りの方法で数える。

graph2.png

 $\{u_1, u_2\}$を固定し、$v$を探すと、最大で$t-1$個の$v$がありえる。なぜなら、$t$個以上の$v$があれば$K_{2,t}$が$G$に含まれることになってしまうためである。よって
$$ |M| \leq (t-1){n \choose 2} $$が成り立つ。
 一方、$v$を固定して$M$を成すような$\{u_1,u_2\}$を探す。各頂点の次数$d_i=\deg(v_i)$に注目すると、
$$ |M| = \sum_{i\in [n]} {d_i \choose 2} $$となる。
 これらを組み合わせると、
$$|M| = \sum_{i\in [n]} {d_i \choose 2} \leq (t-1){n \choose 2}$$が成り立つ。 ・・・ (A)
 さらに、コーシーシュヴァルツの不等式と(A)より、

\begin{align}
\sum_{i\in [n]} (d_i - 1) &\leq \sqrt{\sum_{i\in [n]} (d_i-1)^2} \sqrt{\sum_{i∈ [n]} 1}\\
&\leq \sqrt{(t-1)n^2} \times \sqrt{n}
\end{align}

下式を変形し、元の式を見ると、

\begin{align}
2|E| - \sum_{i\in [n]} 1 &\leq & (\sqrt{t-1})n^{3/2}\\
|E| &\leq & \frac{1}{2}(\sqrt{t-1}n^{3/2} + n)
\end{align}

が得られる。

まとめ

  • コーシーシュヴァルツの不等式を、次数の式に適用するといいことがある。
  • 3つの頂点で成るグラフを数える!これより多いと数えにくいので注意が必要。
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?