Page 185 - 《软件学报》2026年第4期

1626 软件学报 2026 年第 37 卷第 4 期

1
● 坏集合: 如果 λ ⩾ ( ) , 则 S 是坏的.
2 ∆ G[S ] +2
通过这个定义, 我们可以定义以下两个集合:

{ ( ) } { ( ) }
V V
G ≜ S ∈ | S 是好的 , B ≜ S ∈ | S 是坏的 .
ℓ ℓ
我们断言对于好和坏的集合有以下结果.
引理 11. 对于 G 和 B, 以下结果成立.
● 对于任何 S ∈ G t , max (S ) ⩽ 2ℓ.
rel
● 对于任何 S ∈ B t , max (S ) ⩽ ℓ 140/δ .
rel
引理 11 的证明被推迟至第 4.3 节. 我们现在使用引理 11 来证明公式 (12), 有:

[ max ] 140/δ
E S t rel (S) ⩽ Pr S [S ∈ G]·2ℓ +Pr S [S ∈ B]·ℓ (13)
 
V
 
其中,   中均匀随机抽样的. 为了证明公式 I = (G = (V,E),λ) ∈ F(δ) 表示原
 
S 是从
ℓ
  (12), 需要界定 S ∈ B 的概率. 令
12000
始的硬核实例; ∆ G 表示图 G 的最大度数. 在引理 8 的假设下, 有 ∆ G ⩾ ·logn ⩾ 12000. 注意到 λ ⩽ (1−δ)λ c (∆ G )
δ
4 1 1
⩽ . 很容易验证如果 λ⩾ ( ), 那么必然有 ∆ G[S ] ⩾ ∆ G. 对于每个顶点 v ∈ V, 定义随机变量 D v =|{S ∩Γ G (v)}|,
∆ G −2 2 ∆ G[S ] +2 16
其中 Γ G (v) 是图 G 中顶点 v 的邻域, 而 D v 计算了被随机集合 S 选择的顶点 v 的邻居数量. 我们有:

[ ] [ ] [ ]
1 ∆ G ∑ ∆ G
Pr S [S ∈ B] = Pr S λ ⩾ ( ) ⩽ Pr S ∆ G[S ] ⩾ ⩽ Pr S D v ⩾ .
2 ∆ G[S] +1 16 16
v∈V
⌊ n ⌋ 12000
ℓ = E S [D v ] ⩽ ℓ∆ G ⩽ 1 ∆ G ∆ G ⩾ ·logn, 所以根据引理 3, 有:
因为 , 所以 . 又因为
32e n 2e 16 δ

∑
Pr S [S ∈ B] = 2 −∆ G /16 ⩽ n −300/δ (14)
v∈V
⌊ n ⌋
结合公式 (13)、公式 ℓ = , 我们可以证明公式 (12) 如下:
32e
(14) 和
[ ] −300/δ 140/δ
E t max (S) ⩽ 2ℓ +n ·ℓ ⩽ 3n.
rel
这就证明了引理 10.
4.3 好情况和坏情况的弛豫时间 (引理 11 的证明)
 
V
回忆在第 4.1 节开始时固定的硬核模型实例 I = (G = (V,E),λ). 固定一个集合 S ∈  . 我们使用 σ ∈ Ω V\S 表示
 
 
ℓ
 
在公式 (11) 中达到最大值的配置, 即:

(
σ
)
(
t max (S ) = max t rel P ρ ) = t rel P .
rel
S
S
ρ∈Ω V\S
(
)
σ
我们将界定弛豫时间 t rel P , 将集合 S 划分为两部分:
S


A ≜ {v ∈ S | ∀u ∈ Γ G (v)\S,σ u = 0}
 .


B ≜ {v ∈ S | ∃u ∈ Γ G (v)\S,σ u = 1}
σ
其中, Γ G (v) 是原始图 G 中节点 v 的邻域. 很容易看出, 在条件分布 µ 中, τ = 0 ∈ {0,1} 是 B B 上唯一可行的配置. 如
S
(
σ
果 |A| = 0, 那么 µ 的支撑集只有一个状态. 根据公式 (1) 中的定义, t rel P σ ) = 0, 引理 11 是显然成立的. 现在假设
S S
σ
S
|A| > 0. 考虑分布 µ σ⊎τ . 让 P σ⊎τ 表示条件分布 µ σ⊎τ 上的 Glauber dynamics. 虽然 P 的状态空间是 {0,1} , 但 B 上的配
A
A
A
S
σ A σ σ⊎τ 的懒惰版本. 形式上, 在
置始终固定为 τ = 0. 我们可以将 P 视为状态空间 {0,1} 上的马尔可夫链. 因此, P 是 P
S S A
|B| |A|
σ
σ
每一步中, 以 的概率, P 保持在当前状态; 以 的概率, P 以与链 P σ⊎τ 相同的方式演变. 以下关系容易验证:
|S | |S |
S S A
( )
( σ ) |A| ( σ⊎τ ) |A|
λ 2 P S = ·λ 2 P A + 1− .
|S | |S |
σ σ⊎τ ( σ ) ( σ⊎τ )
注意到 P 和 P 都是不可约的, 因此 λ 2 P , λ 2 P < 1. 我们有:
S A S A