无三角形与线性无 Berge-C4 超图中的随机独立集是什么？

两类超图，两种包含概率保证

论文回答的是一个分布问题，而不是规模问题。它不只问独立集必须有多大，而是问能否用一个随机独立集，为每个顶点给出被包含概率的指定下界。答案取决于超图满足哪些局部约束。

在无三角形情形下，该保证适用于每个不含三角形的 (r+1)-一致超图，论文明确不假设线性性。对正顶点权函数 w，顶点 v 的加权度定义为 d_w(v) = Σ_{e ∋ v} (Π_{u ∈ e\{v}} w(u)/w(v))^(1/r)。定理 1.1 给出独立集上的一个分布，使 v 的包含概率至少为 (1 − e^(−a(v)))(1 + Λ_a(v)/log a(v))，其中 a: V → (0,1) 为任意活动向量；推论 1.3 将其转化为所述界 P(v ∈ I) ≥ F_r(d_w(v))，其中当 x → +∞ 时 F_r(x) = (r/(r+1))·(r(r+1))^(−1/r)·(log x / x)^(1/r) 相差 o_r(1) 因子。

在线性无 Berge-C4 情形下，定理 1.2 给出另一种形式。对每个整数 r ≥ 1 和每个 ε ∈ (0,1)，存在 δ = δ(r,ε) > 0，使得对 V 上的每个全序和每个活动向量 a: V → (0,1)，存在独立集上的分布 D，满足对所有 v 同时有 P_{I∼D}(v ∈ I) ≥ (1 − ε)·min{a(v), δ·e^(−Γ_a(v))}。推论 1.4 将其转化为一致陈述：对每个充分大的阈值 D，存在一个随机独立集，使每个满足 d_w(v) ≥ D 的顶点都有 P(v ∈ I) ≥ (1 − ε)·(log d_w(v)/(r·d_w(v)))^(1/r)。

这两个保证并不是同一陈述在不同尺度下的版本。无三角形界是逐顶点的，以 d_w(v) 表示，并带有常数前因子 r/(r+1)·(r(r+1))^(−1/r)。无 Berge-C4 界则在阈值 D 之上一致成立，首项常数为 1，但只适用于加权度超过 D 的顶点，并且要求线性性以及不含 Berge C4。

加权度才是合适的局部参数

结果是对正顶点权函数 w 陈述的，而不只是对无权度 d_G(v)。加权度 d_w(v) = Σ_{e ∋ v} (Π_{u ∈ e\{v}} w(u)/w(v))^(1/r) 在 w ≡ 1 时退化为 d_G(v)，因此无权情形是特例，而不是另一条独立定理。

这一点重要，因为包含概率保证是局部的。加权度大的顶点被承诺更大的包含概率，而且这一承诺是逐顶点给出的，并非只在顶点集上平均成立。论文将推论 1.3 描述为带常数因子损失的局部 Shearer 界的超图版本，推论 1.4 则是线性无 Berge-C4 超图对应的局部陈述。

加权度也控制着分数色数的推论。对 d-退化无三角形 (r+1)-一致超图，推论 1.5 给出 χ_f(G) ≤ (r+1)/r · (r(r+1))^(1/r) · (d/log d)^(1/r)，相差 o_r(1)。对 d-退化线性无 Berge-C4 (r+1)-一致超图，推论 1.6 给出 χ_f(G) ≤ (1 + o_r(1))·(r·d/log d)^(1/r)。这里的 d 是退化度，不是最大度，结论针对分数染色，而非普通染色。

同一个有序过程产出两个随机集

两个定理都通过分析同一个有序随机选取过程来证明，该过程由 Martinsson 和 Steiner 推广到超图。顶点按固定全序 v_1 ≺ ⋯ ≺ v_n 处理。在第 i 步，当前顶点 v_i 以概率 q_i = p(a_{i−1}(v_i)) 被选中，其中 p 是选取函数，a_{i−1}(v_i) 是 v_i 的演化质量。

若 v_i 被选中，它加入独立集，任何受此选择影响的未来顶点的质量被置零。若 v_i 未被选中，受影响的未来质量改为除以 1 − q_i。这种补偿使每个未来质量的条件期望保持不变，因此 E[a_i(v_j) | F_{i−1}] = a_{i−1}(v_j)，E[a_i(v_j)] = a(v_j)。该过程总是输出独立集，因为当处理某条边的 neck 时，若选中它，head 的质量已被置零，而 p(0) = 0 使 head 之后无法被选中。

两个定理的区别在于 p 的选取。定理 1.1 使用 p(t) = 1 − e^(−t) 以及固定目标的修正。在图的情形只需追踪目标的一个较早邻居的质量；在超图情形还必须记录某条 backward 边的其他较早顶点是否已被选中，这一信息被编码在一个辅助乘积中。good order 条件保证外部步骤至多影响该乘积的一个因子。

定理 1.2 使用截断选取函数 p_ρ(t) = min{t, ρ} 以及一个二阶矩论证。截断使顶点权上的补偿因子得到一致控制，同时保持每个顶点权的一阶矩。为界定二阶矩，证明追踪与 backward 边相关的乘积，并在其子集上迭代单步界。线性性和无 Berge-C4 保证多个相关因子可能相互作用的步骤足够稀疏，从而使累积损失保持有界。

good order 与 Berge 条件控制干扰

证明依赖顶点序上的一个结构条件。给定序 ≺，边 e 的 head m(e) 是其最大顶点，neck m*(e) 是第二大顶点。若对任意边 f 和任意不在 f 中的顶点 x，满足 x ≺ v 且 E(x,v) ≠ ∅ 的顶点 v ∈ f 至多一个，其中 E(x,v) = {e ∈ E : m*(e) = x, m(e) = v}，则称该序为 good。在 good order 中，固定边之外的一个顶点至多影响该边的一个较晚顶点。无三角形超图的任意序都是 good，这正是定理 1.1 不需要线性性假设的原因。

第二种情形用线性性加不含 Berge C4 取代无三角形性。若任意两条不同边至多交于一个顶点，等价于不含长度为二的 Berge 圈，则超图是线性的。长度为 ℓ 的 Berge 圈由不同边 e_1, …, e_ℓ 和不同核心顶点 x_1, …, x_ℓ 组成，满足 {x_i, x_{i+1}} ⊆ e_i，下标模 ℓ。Berge 三角形是长度为三的 Berge 圈。论文的第二个定理允许 Berge 三角形，因此覆盖了 uncrowded 情形所排除的一类超图。

这一区别是两个结果之间的主要适用范围差异。无三角形定理在一个方向上更广，因为它去掉了线性性，但其常数前因子更大。无 Berge-C4 定理的结构假设更窄，但在分数色数界上达到首项常数 1，与 Yu 和 Zhang 以及 Dhawan、Methuku 和 Vo 的最大度列表染色界中的系数一致，而这里的参数是退化度，结论针对分数染色。

退化度界改进了此前的系数

分数色数推论针对 d-退化超图陈述，即存在一个顶点序，使每个顶点至多是 d 条边的最大顶点。对无三角形 (r+1)-一致超图，推论 1.5 给出 χ_f(G) ≤ ((r+1)/r)·(r(r+1))^(1/r) + o_r(1))·(d/log d)^(1/r)。当 r = 1 时，这恢复了 Martinsson 和 Steiner 此前的图界。当 r ≥ 2 时，论文指出它把 Dhawan 定理 1.4 的首项系数改进了 r^(1/r) 倍，并去掉了线性性假设。

对线性无 Berge-C4 的 d-退化 (r+1)-一致超图，推论 1.6 给出 χ_f(G) ≤ (1 + o_r(1))·(r·d/log d)^(1/r)。当 r = 1 时，这恢复了 Allen、Dhawan 和 Noel 的上界。论文还指出，其首项常数与 Yu 和 Zhang 以及 Dhawan、Methuku 和 Vo 的最大度列表染色界一致，但这里的参数是退化度而非最大度，结论是分数染色而非列表染色。

论文的第一个结果解决了 Dhawan 的猜想 5.4，该猜想问的是同样的量级是否对不假设线性性的无三角形一致超图成立。第二个结果在 uncrowded 类上达到了 Dhawan 猜想 5.3 所提出的系数，并把同一边界推广到可能含 Berge 三角形的线性无 Berge-C4 超图。论文中有一条注记记录：Dhawan 工作的第 4 版宣布了即将发表的合作工作，证明 uncrowded 超图所猜想的首项系数退化度界及其局部需求版本；论文指出在写作时该被引版本只包含这一宣布，并说明其自身第二个定理的适用范围不同，因为它允许 Berge 三角形。

阈值与结构假设限定了结论

无三角形包含界对加权度是渐近的：它陈述为 d_w(v) → +∞，并带有依赖 r 的 o_r(1) 项。它不是有限度保证，且常数前因子 r/(r+1)·(r(r+1))^(−1/r) 不等于 1。该界对每个顶点单独成立，但渐近范围是陈述的一部分。

无 Berge-C4 包含界只在阈值之上一致成立。对每个充分大的 D，存在一个随机独立集，对所有满足 d_w(v) ≥ D 的顶点同时成立，当 D → +∞ 时 P(v ∈ I) ≥ (1 − o_r(1))·(log d_w(v)/(r·d_w(v)))^(1/r)。低于 D 的顶点不在此一致陈述覆盖范围内。推论 1.4 的证明在截断值以下把活动设为 1/2，以保持 a ∈ (0,1)^V，并对这些顶点不施加任何边缘要求。

结构假设也是适用范围的一部分。第一个定理要求 good order，而每个无三角形超图都具备，因此它适用于所有无三角形 (r+1)-一致超图，无需线性性。第二个定理要求线性性且不含 Berge C4，但允许 Berge 三角形。两个定理都不是对任意超图陈述的，分数色数推论继承相应的退化度和结构条件。

比较前因子、阈值与结构代价

本文最有用的比较不是抽象地看哪个界更大，而是看读者需要哪种前因子、阈值与结构假设的组合。无三角形结果付出常数前因子 r/(r+1)·(r(r+1))^(−1/r) 和 o_r(1) 项，但不要求线性性，并给出以 d_w(v) 表示的逐顶点界。无 Berge-C4 结果达到首项常数 1，并在阈值 D 之上给出一致保证，但要求线性性和不含 Berge C4，且把低于 D 的顶点排除在一致陈述之外。

对分数色数，同样的权衡体现在系数上。推论 1.5 对 d-退化无三角形超图带有因子 (r+1)/r·(r(r+1))^(1/r)，而推论 1.6 对 d-退化线性无 Berge-C4 超图带有首项常数 1。论文指出，当 r ≥ 2 时，无三角形界把 Dhawan 的系数改进了 r^(1/r) 并去掉了线性性；而无 Berge-C4 界与最大度列表染色系数一致，但使用的是退化度和分数染色。

因此实际解读取决于手头的超图。若超图无三角形但未知是否线性，第一个结果就是适用的，需注意其前因子和 d_w(v) → +∞ 的渐近性。若超图线性且无 Berge-C4，但可能含 Berge 三角形，第二个结果给出更锐利的首项常数，前提是所关注的顶点加权度至少达到阈值 D。论文自身的定位把第二个定理的适用范围与已宣布的 uncrowded 超图工作区分开来，正是因为它允许 Berge 三角形。

本文引用的文献