On the number of copies of one graph in another

Fri Apr 10 2026

정해진 그래프 $H$가 있을 때, 간선 수가 $m$인 그래프 $G$ 안에 $H$의 copy가 최대 몇 개까지 들어갈 수 있을까? $H$를 고정하고 $m \to \infty$를 보내면, 답은 대략 $m$의 어떤 지수꼴이 된다. 이 글의 주제는 그 지수가 정확히 무엇이냐는 질문이다.

정확히는 labeled embedding의 개수 $\operatorname{Emb}(H, G)$를 세겠다. embedding이란 injective map

$$ \phi: V(H) \to V(G) $$

으로서, 임의의 $uv \in E(H)$에 대해 $\phi(u)\phi(v) \in E(G)$를 만족하는 것이다. 또 $H$에 isolated vertex가 있으면 $m$만으로는 상한을 줄 수 없으니, 이하에서는 $H$가 connected graph라고 가정한다.

이제 우리는 다음과 같은 statement를 원한다: $H$에 대한 함수 $\rho(H)$가 있어서

$$ \operatorname{Emb}(H, G) = O(m^{\rho(H)}) $$

꼴이 되기를 바라는 것이다. 문제는 저 $\rho(H)$가 정확히 무엇이냐이다.

Example: triangle $K_3$

제일 간단한 정점 $3$개짜리 그래프 $H$부터 보자. 우리는 triangle의 embedding 개수가 $O(m^{3/2})$라는 사실을 알고 있다. 증명은 degree를 $\sqrt m$을 기준으로 나누면 된다. degree가 $\sqrt m$ 이상인 정점을 high, 아닌 정점을 low라고 하자. 먼저 low 정점을 적어도 하나 포함하는 triangle들을 세자. low 정점 $v$를 하나 고정하면, $v$를 포함하는 triangle의 수는 많아야 $v$의 이웃 둘을 고르는 경우의 수이므로

$$ \binom{d(v)}{2} \le \frac{d(v)^2}{2} \le \frac{\sqrt m}{2} d(v) $$

이다. 따라서 low 정점을 적어도 하나 포함하는 triangle의 전체 개수는

$$ \sum_{v\text{ low}} \binom{d(v)}{2} \le \frac{\sqrt m}{2} \sum_{v\text{ low}} d(v) \le \frac{\sqrt m}{2} \cdot 2m = m^{3/2} $$

이다. 다음으로 남은 triangle들은 모두 high 정점만으로 이루어져 있다. 그런데 high 정점의 개수는 handshake lemma에 의해

$$ |V_{\mathrm{high}}| \cdot \sqrt m \le \sum_{v \in V_{\mathrm{high}}} d(v) \le 2m $$

로 bound되므로, 따라서 high 정점만으로 이루어진 triangle의 개수는 많아야

$$ \binom{|V_{\mathrm{high}}|}{3} = O\bigl((\sqrt m)^3\bigr) = O(m^{3/2}) $$

이다.

두 경우를 합치면 triangle copy의 개수가 $\smash{O(m^{3/2})}$이고, 따라서 labeled embedding의 개수도 역시 $O(m^{3/2})$이다. 하지만 이 방법은 triangle의 구조를 꽤 많이 써서 얻는 bound라서, 임의의 그래프 $H$로 그대로 일반화하기는 어렵다.

Naive bound: edge cover

그래서 다른 관점으로 이 문제를 접근해 보겠다. 가장 naive하게 bound를 잡으면 아마 다음과 같을 것이다: triangle의 세 간선 각각이 $G$의 어느 간선으로 가는지를 다 정하면 embedding이 유일하게 결정된다. 따라서 경우의 수는 $O(m^3)$이다. 그런데 triangle에서는 세 간선을 다 고를 필요도 없다. triangle의 두 인접한 간선을 $ab, bc$라고 하자. embedding $\phi$가 주어졌을 때 ordered edge $(\phi(a), \phi(b))$와 $(\phi(b), \phi(c))$를 알면, 두 ordered edge가 공유하는 끝점이 $\phi(b)$이고 나머지 끝점들이 각각 $\phi(a), \phi(c)$이므로 embedding 전체가 정해진다. 따라서 실제로는 "간선 두 개의 image"만으로 충분하고, 곧바로 $O(m^2)$가 나온다.

이 현상은 triangle만의 일이 아니다. 예를 들어 사각형, 즉 $H = C_4$라면 naive하게는 간선 네 개를 다 고르니까 $O(m^4)$를 먼저 떠올릴 수 있다. 하지만 cycle order를 $a,b,c,d$라 두고 서로 마주 보는 두 간선 $ab, cd$를 보자. embedding $\phi$가 주어졌을 때 ordered edge $(\phi(a), \phi(b))$와 $(\phi(c), \phi(d))$를 알면 네 정점의 image가 모두 정해지므로 embedding 전체도 정해진다. 따라서 이 경우에도 $O(m^2)$의 bound를 얻는다.

방금 triangle과 $C_4$에서 쓴 원리의 공통점은, 간선 집합을 잘 골랐을 때 고른 간선들이 항상 $H$의 모든 정점을 덮고 있는 집합을 잡았다는 것이고, 그러한 집합의 크기를 작게 만들수록 좋은 bound가 얻어진다는 점이다. 이러한 bound는 임의의 그래프 $H$에 대해 적용 가능하다는 장점이 있다. 이건 실제로도 잘 알려진 개념이다: 그래프 $H$의 간선 부분집합 $F \subseteq E(H)$가 모든 정점을 덮는다면, 즉 각 정점이 $F$의 간선 중 적어도 하나에 incident하다면, $F$를 $H$의 edge cover라고 부른다. 따라서 minimum edge cover의 크기를 $\rho(H)$라고 쓰면

$$ \operatorname{Emb}(H, G) = O(m^{\rho(H)}) $$

를 얻는다.

Exact bound: fractional edge cover

위 방법은 여전히 triangle에서 우리가 진짜 알고 있는 값 $3/2$를 주지 않는다. 그러나 매우 흥미롭게도, 이 edge cover라는 notion을 더 추상화하면 우리가 원하는 exact bound에 도달할 수 있다. Edge cover라는 건, 결국 각 간선을 "고른다 / 안 고른다"를 선택하고, 그 때 모든 정점이 $1$개 이상의 선택된 간선에 incident하게 하는 것이다. 그런데 간선을 분수 개만큼, fractional하게 고른다고 생각하면 어떨까? 즉 각 간선 $e \in E(H)$에 대해 nonnegative weight $x_e$를 하나 주고, 각 정점은 자기에 incident한 간선들로부터 받은 가중치의 총합이 적어도 $1$이 되게 만든다고 하자.

놀랍게도 이러면 triangle에서 이 fractional edge cover의 최솟값은 $3/2$가 된다. 세 간선 각각에 $1/2$씩 주면, triangle의 각 정점은 incident한 두 간선으로부터 총 $1$을 받는다. 그러므로 feasible solution이고, total weight는 $3/2$다! 이제 이걸 조금 수학적으로 써 보자. $H$의 incidence matrix를

$$ A \in \{0,1\}^{V(H) \times E(H)}, \qquad A_{v,e} = \begin{cases} 1 & \text{if } v \in e, \\ 0 & \text{otherwise} \end{cases} $$

로 정의하자.

그러면 ordinary한 minimum edge cover는

$$ \begin{aligned} \rho(H) = \min \ & \mathbf{1}^\top x \\ \text{s.t. } & A x \ge \mathbf{1}, \\ & x \in \{0,1\}^{E(H)} \end{aligned} $$

로 쓸 수 있다. 변수 $x_e$는 간선 $e$를 선택했는지 여부를 뜻한다. objective $\mathbf{1}^\top x$는 선택한 간선의 수를 세는 것이고, constraint $A x \ge \mathbf{1}$는 각 정점이 incident한 선택된 간선이 적어도 하나 있다는 뜻, 즉 edge cover 조건이다.

Fractional edge cover 조건은 정확히 edge cover의 LP representation에 대한 relaxation이다: $ x \in \{0,1\}^{E(H)} $ 조건 대신

$$ x \in \mathbb{R}^{E(H)}, \qquad x \ge 0 $$

을 사용하는 것이다. 따라서

$$ \begin{aligned} \rho^*(H) = \min \ & \mathbf{1}^\top x \\ \text{s.t. } & A x \ge \mathbf{1}, \\ & x \ge 0 \end{aligned} $$

를 $H$의 fractional edge cover number로 정의한다. 이제 우리가 증명하고자 하는 formal statement를 쓰면 다음과 같다:

Main Theorem

고정된 그래프 $H$와 간선 수가 $m$인 모든 그래프 $G$에 대하여

$$ \operatorname{Emb}(H, G) = O(m^{\rho^*(H)}) $$

가 성립하고, 또한 충분히 큰 $m$에 대해 간선 수가 $m$인 어떤 그래프 $G$가 존재하여

$$ \operatorname{Emb}(H, G) = \Omega(m^{\rho^*(H)}) $$

를 만족한다.

이 정리는 Friedgut-Kahn의 hypergraph version [@FK98]에서 graph case를 뽑아 쓴 것이다. 증명의 구조는 probabilistic method와 꽤 비슷한데, 다만 여기서는 단순히 expectation을 세는 게 아니라 random embedding 하나가 담고 있는 entropy를 측정한다.

What is entropy?

지금부터 필자는 사실 entropy 개념을 잘 아는 독자를 상정하고 글을 쓰겠지만, 아주 elementary한 설명은 하도록 하겠다. 어떤 finite random variable $X$의 entropy는 다음과 같이 정의된다:

$$ H(X) = \sum_x \Pr[X=x] \log \frac{1}{\Pr[X=x]}. $$

그러나 이 식은 매우 지루하고 현학적이다. Entropy를 이해하는 더 좋고 intuitive한 방법은 다음과 같다. Entropy란 저 random variable $X$의 정보량이다. 여기서 정보량이란, 다음을 의미한다:

$X$를 한 번 sampling했을 때, 그 결과가 무엇인지 표현하려면 on average 몇 bit가 필요한가?

몇 가지 예시를 보자.

Example 1: $X$가 항상 같은 값만 나온다고 하자. 그럼 $X$를 sampling했을 때 무슨 결과가 나오는지가 고정이다. 알려줄 정보가 없으므로, 이 결과를 표현하기 위해 0 bit면 충분하다. 따라서 $ H(X) = 0 $.
Example 2: $X$가 가능한 값 $N$개 중 하나를 확률 $1/N$로 가진다고 하자. 그럼 각각의 값에 다른 bit representation을 배정해야 하므로, 서로 다른 $N$개의 결과를 표현하려면 최소 $\log N$ bit가 필요하다. 실제로 계산해보면 $ H(X) = \log N $.
Example 3: $0$이 $9/10$, $1$이 $1/10$ 확률로 나온다고 하자. 그러면 당연히 1 bit로 표현이 가능하지만, 실제 entropy는 1보다 작다. 즉 그냥 0/1로 $X$의 결과를 표현하는 건 최적이 아니라는 뜻이다. 위에 써 있는 정보량의 의미를 다시 읽어보면, on average라는 문구가 달려 있다. 즉 여러 번 sampling한 결과를 전부 표현했을 때의 평균 소모 bit 수가 entropy고, 딱 한 번 sampling한 결과를 표현하는 게 목적이 아니다. 정확히 하나의 결과만 표현하려고 한다면, 이 경우엔 1 bit가 필요한 게 맞다.

다시 돌아가서, 이 변수를 100번 sampling했다고 해 보자. 공평한 동전이면 결과를 다 적으려면 거의 100 bit가 필요하다. 하지만 $1$이 10% 확률로만 나온다면, "1이 나온 위치들", 혹은 "인접한 1이 나온 시간의 간격"만 기록하는 쪽이 평균적으로 훨씬 짧다. 그래서 한 번당 필요한 평균 bit 수는 1보다 작아진다.

Joint entropy

이제 random variables $X_1, X_2, \ldots, X_n$이 있다고 하자. Joint entropy $ H(X_1, X_2, \ldots, X_n) $는 tuple $(X_1, X_2, \ldots, X_n)$ 전체를 한 번에 표현하는 데 필요한 정보량으로 정의된다. Tuple의 좌표들이 서로 독립이라면 각 random variable을 각각 encoding하는 게 최적이 맞는데, 독립이 아니면 그렇지 않다. 예를 들어 $X_1 \in \{0,1\}$이고 $ X_2 = 1 - X_1 $라고 하자. 그러면 $X_1$을 알면 $X_2$는 자동으로 정해진다. 따라서 $(X_1, X_2)$를 표현하는 데 필요한 정보량은 사실 $X_1$ 하나를 표현하는 것과 똑같다.

즉 $ H(X_1, X_2) = H(X_1) = H(X_2) $이고, 이게 아니더라도 일반적으로 $ H(X_1, X_2) \le H(X_1) + H(X_2) $가 성립한다. 이를 entropy의 subadditivity라고 부른다. 우리가 이 증명에서 활용할 entropy에 관련된 성질은 아래 두 가지뿐이다:

첫째는 chain rule:

$$ H(X_1, \ldots, X_n) = \sum_{i=1}^n H(X_i \mid X_1, \ldots, X_{i-1}). $$

둘째는 conditioning reduces entropy:

$$ H(U \mid V, W) \le H(U \mid V). $$

Conditioning을 많이 할수록, 즉 random variable에 대해 알고 있는 정보가 많아질수록 불확실성, 즉 정보량은 줄어든다는 뜻이다.

Technical lemma: Shearer's inequality

$X_1, \ldots, X_n$을 random variables라고 하자. $\mathcal{A}$를 [n]의 부분집합들의 multiset이라 하자. 그리고 각 $i \in [n]$가 $\mathcal{A}$의 원소들 중 적어도 $t$개에 속한다고 하자. 또한 각 부분집합 $S \subseteq [n]$에 대해 $ X_S := (X_i)_{i \in S} $라고 쓰자. 그러면

$$ \sum_{S \in \mathcal{A}} H(X_S) \ge t \, H(X_1, \ldots, X_n) $$

가 성립한다.

Shearer의 lemma 증명

각 $S \in \mathcal{A}$에 대해, $S$의 원소들을 증가하는 순서로 나열해서 chain rule을 적용하자. 그러면

$$ H(X_S) = \sum_{i \in S} H(X_i \mid X_{S \cap [i-1]}) $$

를 얻는다. 이제 $S \cap [i-1] \subseteq [i-1]$이므로, conditioning reduces entropy 성질에 의해

$$ H(X_i \mid X_{S \cap [i-1]}) \ge H(X_i \mid X_{[i-1]}) $$

이다. 따라서

$$ H(X_S) \ge \sum_{i \in S} H(X_i \mid X_{[i-1]}). $$

이걸 이제 모든 $S \in \mathcal{A}$에 대해 더하면

$$ \sum_{S \in \mathcal{A}} H(X_S) \ge \sum_{S \in \mathcal{A}} \sum_{i \in S} H(X_i \mid X_{[i-1]}). $$

오른쪽의 합 순서를 바꾸면

$$ \sum_{S \in \mathcal{A}} \sum_{i \in S} H(X_i \mid X_{[i-1]}) = \sum_{i=1}^n c_i \, H(X_i \mid X_{[i-1]}), $$

여기서 $c_i$는 원소 $i$를 포함하는 $\mathcal{A}$의 집합 개수이다. 가정에 의해 각 $i$는 적어도 $t$번 등장하므로 $c_i \ge t$이다. 따라서

$$ \sum_{S \in \mathcal{A}} H(X_S) \ge t \sum_{i=1}^n H(X_i \mid X_{[i-1]}) = t \, H(X_1, \ldots, X_n). $$

직관적 설명

엄밀하진 않지만, 이 부등식을 설명하는 직관적인 설명을 하나 언급하고 가겠다. 위에서 살펴봤듯이, entropy에는 subadditivity 성질이 있다. 즉 random variable 여러 개를 뭉칠수록 joint entropy는 작아진다. Lemma statement에서 좌변의

$$ \sum_{S \in \mathcal{A}} H(X_S) $$

은 같은 좌표들을 여러 작은 부분 tuple들로 나누어 본 것이다. 각 좌표는 적어도 $t$번씩 등장하지만, 큰 덩어리 하나로 보는 대신 작은 조각들로 흩어져 있다. 반면 우변의 $ t \, H(X_1, \ldots, X_n) $ 는 전체 tuple $(X_1,\ldots,X_n)$을 통째로 본 것을 $t$번 반복한 것이다. 말하자면 가능한 한 크게 묶은 형태다.

그러므로 각각의 random variable singleton들이 $t$개씩 있을 때, 좌변은 이를 $\mathcal{A}$에 등장하는 set들의 형태로 부분적으로 묶어서 본 것이고, 우변은 그 좌표들을 최대한 크게, 즉 전체 tuple이라는 한 덩어리로 묶어 놓은 것이다. 그러니까 entropy의 subadditivity를 고려했을 때, 정보량은 묶을 수 있는 최대한으로 묶었을 때 더 많이 감소하게 되므로, 전체를 크게 묶어서 $t$번 보는 것보다 부분적으로 잘라서 여러 번 보는 쪽의 total entropy가 더 크다.

Proof of main theorem

$x = (x_e)_{e \in E(H)}$를 $H$의 optimal fractional edge cover라고 하자. 즉

$$ x \ge 0, \qquad A x \ge \mathbf{1}, \qquad \sum_{e \in E(H)} x_e = \rho^*(H). $$

이 때 LP의 모든 계수가 유리수이므로, optimal solution을 유리수 해로 잡을 수 있다. LP의 feasible region은

$$ \{x \in \mathbb{R}^{E(H)} : A x \ge \mathbf{1}, \ x \ge 0\} $$

인데, 사실 optimal solution을 찾을 때는 여기에 $x_e \le 1$도 추가해도 된다. 직관적으로는 edge를 1개보다 많게 고르는 것이 의미가 없기 때문이다. 조금 더 자세히는, 어떤 feasible solution에서 $x_e > 1$인 좌표가 있으면, 그 좌표를 $1$로 낮춰도 모든 constraint $A x \ge \mathbf{1}$는 그대로 유지되고 objective $\mathbf{1}^\top x$는 더 작아지기 때문이다. 따라서 우리는 아래의 compact polytope

$$ P := \{x \in \mathbb{R}^{E(H)} : A x \ge \mathbf{1}, \ 0 \le x \le \mathbf{1}\} $$

위에서 minimum을 구한다고 생각해도 완전히 같은 문제를 푸는 셈이다. 이 compact polytope region에서 임의의 linear objective는 어떤 vertex에서 최솟값을 달성한다. 그리고 polytope $P$의 임의의 vertex는 적당한 $\lvert E(H)\rvert$개의 linearly independent tight constraints에 의한 square linear system $B x = c$ 의 해로 주어지는데, 여기서 $B$와 $c$의 계수는 전부 유리수다. 그러면 Cramer's rule로부터 $x$의 좌표도 전부 유리수임을 알 수 있다.

$G$를 간선 수가 $m$인 그래프라고 하자. 그리고 $H$의 모든 embedding들 가운데 하나를 균등하게 무작위로 뽑은 random embedding을 $X$라고 하자. 또한 무작위로 뽑힌 embedding이 $X = \phi$일 때, 각 정점 $v \in V(H)$에 대해 $X_v := \phi(v)$라고 표기한다.

위에서 살펴보았듯이, 적당한 양의 정수 $q$를 골라서 모든 $q x_e$를 정수로 만들 수 있다. 이제 multiset $\mathcal{A}$를 다음과 같이 만든다: 각 간선 $e = uv \in E(H)$에 대해 2-element set $\{u,v\}$를 $\mathcal{A}$에 정확히 $q x_e$번 넣는다. 그러면 각 정점 $v \in V(H)$는 $\mathcal{A}$의 원소들 중 최소한

$$ \sum_{e \ni v} q x_e = q \sum_{e \ni v} x_e \ge q $$

개에 속해 있다. 따라서 Shearer's inequality를 random variable $ (X_v)_{v \in V(H)} $와 multiset $\mathcal{A}$에 적용하면

$$ q \, H\bigl((X_v)_{v \in V(H)}\bigr) \le \sum_{e \in E(H)} q x_e \, H(X_e) $$

를 얻는다. 여기서 간선 $e = uv$에 대해 $ X_e := (X_u, X_v) $이다. 양변을 $q$로 나누면

$$ H\bigl((X_v)_{v \in V(H)}\bigr) \le \sum_{e \in E(H)} x_e \, H(X_e). $$

이제 증명이 거의 끝났다. 먼저 좌변의 의미를 해석해보자. $X$는 random embedding을 나타내는 random variable이므로, $ (X_v)_{v \in V(H)} $ tuple 전체는 어떤 embedding function 하나를 지정한 것과 같다. 그러므로 이 tuple들로 가능한 값의 수는 정확히 $\operatorname{Emb}(H,G)$개이고, $X$는 모든 embedding 위의 uniform distribution이므로, 이 tuple의 joint entropy는

$$ H\bigl((X_v)_{v \in V(H)}\bigr) = \log \operatorname{Emb}(H,G). $$

이제 간선 $e = uv \in E(H)$를 하나 고정하자. 그러면 $ X_e = (X_u, X_v) $는 정의상으로는 단순히 $G$의 두 정점의 ordered pair이지만, $X$가 valid embedding이므로 $X_e$는 $H$의 간선 $e$가 $G$의 어떤 간선으로 embedding되었는가를 나타내는 random variable이 된다. 그러므로 $X_e$로 가능한 값의 총 개수는 $G$의 간선만큼인데, 여기서는 정점의 순서가 중요하므로 최대 $2m$개이다. 따라서 $X_e$의 joint entropy는:

$$ H(X_e) \le \log(2m) $$

을 만족한다. 여기서 주의할 점은, $X_e$가 ordered edge들 위에서 uniform distribution은 아니라는 것이다. 하지만 우리는 필요한 것은 entropy의 상한이므로, $X_e$로 가능한 값을 encoding할 방법만 하나 찾으면 그 때 사용되는 최대 bit 수가 곧 entropy의 상한이다.

그러므로, 좌변과 우변을 전부 대치하면

$$ \log \operatorname{Emb}(H,G) \le \sum_{e \in E(H)} x_e \log(2m) = \rho^*(H)\log(2m) $$

이므로, 양변에 $\mathrm{exp}$를 취하면

$$ \operatorname{Emb}(H,G) \le (2m)^{\rho^*(H)} = O(m^{\rho^*(H)}). $$

Q.E.D.

Lower bound side

위에서 증명한 것은 embedding 개수의 upper bound이다. 그러므로 이제 정확히 $\Theta(m^{\rho^*(H)})$개의 embedding을 가지게 하는 graph family를 찾을 수 있다는 것도 증명하자. 증명의 시작은 재밌게도, fractional edge cover LP relaxation에 대한 LP dual에서 시작한다. LP dual은 다음과 같이 표현된다:

$$ \begin{aligned} \max \ & \mathbf{1}^\top y \\ \text{s.t. } & y_u + y_v \le 1 \qquad \text{for all } uv \in E(H). \\ & y \ge 0 \end{aligned} $$

즉 dual 변수는 이제 간선이 아니라 정점에 대해 정의된다. Strong duality에 의해 dual optimum은 primal optimum과 같으므로, optimal dual solution $y$에 대해

$$ \sum_{v \in V(H)} y_v = \rho^*(H). $$

이제 $H$의 embedding이 충분히 많은 graph family $G$를 construct할 수 있으면 증명이 끝난다. 적당히 큰 어떤 parameter $B$를 하나 잡자. 각 정점 $v \in V(H)$마다 $G$에 $ |V_v| = B^{y_v} $ 크기의 정점 부분집합 $V_v$를 하나 만든다. 그다음 모든 $e = uv \in E(H)$에 대해, $V_u$와 $V_v$의 모든 정점을 연결해 complete bipartite graph로 만든다.

그러면 이 construction에 의해, $G$의 간선 개수는 다음과 같다. 간선 $e = uv \in E(H)$ 하나가 $G$에 만드는 간선은

$$ |V_u||V_v| = O(B^{y_u+y_v}) \le O(B) $$

이다. 마지막 부등식은 dual constraint $y_u + y_v \le 1$ 때문이다. $H$의 간선 개수는 어떤 고정된 상수이므로, $G$의 전체 간선 수는

$$ |E(G)| = |E(H)| \cdot O(B) = O(B). $$

그런데 사실 $|E(G)| = \Omega(B)$이기도 하다. 왜냐면 LP dual의 optimal solution에서 어떤 간선 하나는 반드시 tight해야 하기 때문이다. 즉, 만약 모든 간선 $uv$에 대해

$$ y_u + y_v < 1 $$

이 strict하게 성립한다면, 모든 정점의 weight를 아주 조금씩 동시에 올려도 모든 constraint가 여전히 유지되는데, 그러면 objective $\sum_v y_v$가 더 커지므로 optimality에 모순이다. 따라서 dual의 optimal solution $y$는 항상 어떤 간선 $uv$가 존재하여 실제로 $ y_u + y_v = 1 $을 만족하고, 그 간선 $uv \in E(H)$에 의해서 $G$에는 $B^{y_u + y_v} = B$개의 간선이 생긴다. 그러므로, $ |E(G)| = \Theta(B) $가 성립한다.

이제 embedding의 개수를 세자. 각 정점 $v \in V(H)$마다 corresponding part $V_v$에서 정점 하나를 고르자. part들은 서로 disjoint하므로 이렇게 고른 정점들은 자동으로 모두 다르다. 그리고 $uv \in E(H)$이면 construction상 $V_u$와 $V_v$ 사이가 complete bipartite로 연결되어 있으므로, 이렇게 고른 정점들은 정확히 $H$의 embedding 하나를 이룬다.

따라서

$$ \operatorname{Emb}(H, G_B) \ge \prod_{v \in V(H)} |V_v| = \prod_{v \in V(H)} \lfloor B^{y_v} \rfloor = \Omega\left(B^{\sum_v y_v}\right) $$

이고, strong duality에 의해 $\sum_v y_v = \rho^*(H)$이므로

$$ \operatorname{Emb}(H, G_B) = \Omega(B^{\rho^*(H)}). $$

한편 $|E(G_B)| = \Theta(B)$이니, $B \asymp m$로 두면

$$ \operatorname{Emb}(H, G_B) = \Omega(m^{\rho^*(H)}). $$

Reference

[FK98] E. Friedgut, J. Kahn, On the number of copies of one hypergraph in another, Israel J. Math. 105 (1998), 251-256.