The ultimate independence ratio of a graph $G$ is defined as $\mathscr{I}(G) = \lim_{k\rightarrow\infty } \frac{α(G^{\Box k})}{|V(G)|^k},$ where $α(G^{\Box k})$ is the independence number of the Cartesian product of $k$ copies of $G$. For all graphs $G$, Hahn, Hell, and Poljak (1995) proved that $\frac{1}{Ï(G)} \leq \mathscr{I}(G) \leq \frac{1}{Ï(G)}$ where $Ï(G)$ is the chromatic number, and $Ï(G)$ is the clique number of $G$. So all graphs $G$ with $Ï(G) = Ï(G)$ satisfy $\mathscr{I}(G) = \frac{1}{Ï(G)} = \frac{1}{Ï(G)}$. A construction of Zhu demonstrates that there exists a graph $G$ with $\frac{1}{Ï(G)} < \mathscr{I}(G) < \frac{1}{Ï(G)}$, so neither equality holds in general. In response, Hahn, Hell, and Poljak conjectured that all wheel graphs $W_n$ satisfy $\mathscr{I}(W_n) = \frac{1}{Ï(W_n)}$.
For even wheels $W_{2t}$ this follows from the fact $Ï(W_{2t}) = Ï(W_{2t}) = 3$. Odd wheels of length at least $5$ present a more challenging case, since $Ï(W_{2t+1}) = 4$ and $Ï(W_{2t+1}) = 3$. First, we prove that odd wheels of length at least $7$ satisfy $\mathscr{I}(W_{2t+1})\leq \frac{4t^2+6t}{3(2t+2)^2}<\frac{1}{3}$, which provides the best upper bound for large odd wheels. Next, we prove that $\mathscr{I}(W_5) \leq \frac{1019}{3888}$, improving an upper bound of Hahn, Hell, and Poljak that $\mathscr{I}(W_5) \leq \frac{11}{41}$. Our proofs combine counting arguments, recursive bounds on $α(W^{\Box k}_{2t+1})$, and computer-assisted calculation in the $W_5$ case.
论文ID : 2511.18747标题 : Improved Bounds for the Ultimate Independence Ratio of Odd Wheels作者 : Alexander Clow, Hitesh Kumar, Shivaramakrishna Pragada (Simon Fraser University)分类 : math.CO (组合数学), math.OC (优化与控制)发表时间 : 2025年11月24日提交至arXiv论文链接 : https://arxiv.org/abs/2511.18747 本文研究图的极限独立比（ultimate independence ratio）问题。对于图 G G G I ( G ) = lim k → ∞ α ( G □ k ) ∣ V ( G ) ∣ k \mathscr{I}(G) = \lim_{k\rightarrow\infty} \frac{\alpha(G^{\Box k})}{|V(G)|^k} I ( G ) = lim k → ∞ ∣ V ( G ) ∣ k α ( G □ k ) α ( G □ k ) \alpha(G^{\Box k}) α ( G □ k ) k k k G G G 1 χ ( G ) ≤ I ( G ) ≤ 1 ω ( G ) \frac{1}{\chi(G)} \leq \mathscr{I}(G) \leq \frac{1}{\omega(G)} χ ( G ) 1 ≤ I ( G ) ≤ ω ( G ) 1 W n W_n W n I ( W n ) = 1 χ ( W n ) \mathscr{I}(W_n) = \frac{1}{\chi(W_n)} I ( W n ) = χ ( W n ) 1 t ≥ 3 t \geq 3 t ≥ 3 I ( W 2 t + 1 ) ≤ 4 t 2 + 6 t 3 ( 2 t + 2 ) 2 < 1 3 \mathscr{I}(W_{2t+1}) \leq \frac{4t^2+6t}{3(2t+2)^2} < \frac{1}{3} I ( W 2 t + 1 ) ≤ 3 ( 2 t + 2 ) 2 4 t 2 + 6 t < 3 1 I ( W 5 ) ≤ 1019 3888 ≈ 0.262 \mathscr{I}(W_5) \leq \frac{1019}{3888} \approx 0.262 I ( W 5 ) ≤ 3888 1019 ≈ 0.262 11 41 ≈ 0.268 \frac{11}{41} \approx 0.268 41 11 ≈ 0.268
极限独立比的定义与意义 ：极限独立比刻画了图的笛卡尔积幂中最大独立集的渐近行为 与Shannon容量、图同态理论密切相关 Hell, Yu 和 Zhou (1994) 证明了序列 { i ( G □ k ) } \{i(G^{\Box k})\} { i ( G □ k )} 基本理论界 ：Hahn, Hell 和 Poljak 证明：1 χ ( G ) ≤ I ( G ) ≤ 1 χ f ( G ) ≤ 1 ω ( G ) \frac{1}{\chi(G)} \leq \mathscr{I}(G) \leq \frac{1}{\chi_f(G)} \leq \frac{1}{\omega(G)} χ ( G ) 1 ≤ I ( G ) ≤ χ f ( G ) 1 ≤ ω ( G ) 1 对于弱完美图（χ = ω \chi = \omega χ = ω Zhu (1996) 构造了满足 1 χ ( G ) < I ( G ) < 1 χ f ( G ) \frac{1}{\chi(G)} < \mathscr{I}(G) < \frac{1}{\chi_f(G)} χ ( G ) 1 < I ( G ) < χ f ( G ) 1 轮图的特殊性 ：偶轮 W 2 t W_{2t} W 2 t χ ( W 2 t ) = ω ( W 2 t ) = 3 \chi(W_{2t}) = \omega(W_{2t}) = 3 χ ( W 2 t ) = ω ( W 2 t ) = 3 I ( W 2 t ) = 1 3 \mathscr{I}(W_{2t}) = \frac{1}{3} I ( W 2 t ) = 3 1 奇轮 W 2 t + 1 W_{2t+1} W 2 t + 1 χ ( W 2 t + 1 ) = 4 \chi(W_{2t+1}) = 4 χ ( W 2 t + 1 ) = 4 ω ( W 2 t + 1 ) = 3 \omega(W_{2t+1}) = 3 ω ( W 2 t + 1 ) = 3 1 4 ≤ I ( W 2 t + 1 ) ≤ 1 3 \frac{1}{4} \leq \mathscr{I}(W_{2t+1}) \leq \frac{1}{3} 4 1 ≤ I ( W 2 t + 1 ) ≤ 3 1 核心猜想 （Conjecture 1.2）：I ( W 2 t + 1 ) = 1 4 \mathscr{I}(W_{2t+1}) = \frac{1}{4} I ( W 2 t + 1 ) = 4 1 30年未解决的公开问题 ：Hahn 在2024年加拿大数学会冬季会议上重提此问题最小未知案例 ：5-轮 W 5 W_5 W 5 理论重要性 ：可能为一般图的极限独立比理论提供洞察计算挑战 ：用已知方法估计 I ( W 2 t + 1 ) \mathscr{I}(W_{2t+1}) I ( W 2 t + 1 ) 本文的主要贡献包括：
提出新的一般上界方法 （Theorem 1.3）：对于包含 k k k G G G I ( G ) ≤ α ( G □ ℓ □ K k ) k ∣ V ( G ) ∣ ℓ \mathscr{I}(G) \leq \frac{\alpha(G^{\Box \ell} \Box K_k)}{k|V(G)|^\ell} I ( G ) ≤ k ∣ V ( G ) ∣ ℓ α ( G □ ℓ □ K k ) 推广了Hahn, Hell 和 Poljak关于顶点传递图的结果 改进大奇轮的上界 （Theorem 1.5）：对所有 t ≥ 3 t \geq 3 t ≥ 3 I ( W 2 t + 1 ) ≤ 4 t 2 + 6 t 3 ( 2 t + 2 ) 2 \mathscr{I}(W_{2t+1}) \leq \frac{4t^2+6t}{3(2t+2)^2} I ( W 2 t + 1 ) ≤ 3 ( 2 t + 2 ) 2 4 t 2 + 6 t 这是首个对大奇轮的非平凡理论上界（无需计算机辅助） 精确计算关键值 （Theorem 1.6）：通过计算机辅助证明 α ( W 5 □ 3 □ K 3 ) = 170 \alpha(W_5^{\Box 3} \Box K_3) = 170 α ( W 5 □ 3 □ K 3 ) = 170 结合结构性论证和整数规划 改进5-轮的上界 （Theorem 1.7）：证明 I ( W 5 ) ≤ 1019 3888 \mathscr{I}(W_5) \leq \frac{1019}{3888} I ( W 5 ) ≤ 3888 1019 这是30年来对该界的首次改进 提供计算框架 ：开发了结合理论分析和计算验证的系统方法 所有代码公开可复现 核心任务 ：为奇轮图 W 2 t + 1 W_{2t+1} W 2 t + 1 I ( W 2 t + 1 ) \mathscr{I}(W_{2t+1}) I ( W 2 t + 1 )
技术挑战 ：
直接计算 α ( G □ k ) \alpha(G^{\Box k}) α ( G □ k ) k k k 需要结合理论估计和有限计算 奇轮的色数与团数不等，标准方法失效 本文采用三层递进的方法：
核心思想 ：利用图中的团结构来改进上界。
定理陈述 ：设 G G G k k k ℓ ≥ 1 \ell \geq 1 ℓ ≥ 1 I ( G ) ≤ α ( G □ ℓ □ K k ) k ∣ V ( G ) ∣ ℓ \mathscr{I}(G) \leq \frac{\alpha(G^{\Box \ell} \Box K_k)}{k|V(G)|^\ell} I ( G ) ≤ k ∣ V ( G ) ∣ ℓ α ( G □ ℓ □ K k )
且
I ( G ) = lim ℓ → ∞ α ( G □ ℓ □ K k ) k ∣ V ( G ) ∣ ℓ \mathscr{I}(G) = \lim_{\ell \to \infty} \frac{\alpha(G^{\Box \ell} \Box K_k)}{k|V(G)|^\ell} I ( G ) = lim ℓ → ∞ k ∣ V ( G ) ∣ ℓ α ( G □ ℓ □ K k )
证明技术 ：
递推关系 ：对于 G □ ( p + 1 ) G^{\Box (p+1)} G □ ( p + 1 ) I I I α ( G □ ( p + 1 ) ) ≤ α ( G □ p □ K k ) + ( n − k ) α ( G □ p ) \alpha(G^{\Box (p+1)}) \leq \alpha(G^{\Box p} \Box K_k) + (n-k)\alpha(G^{\Box p}) α ( G □ ( p + 1 ) ) ≤ α ( G □ p □ K k ) + ( n − k ) α ( G □ p ) 极限分析 ：
i ( G □ ( p + 1 ) ) ≤ α ( G □ ℓ □ K k ) n ℓ + 1 ∑ i = 0 p − ℓ ( n − k n ) i + ( n − k ) p − ℓ + 1 α ( G □ ℓ ) n p + 1 i(G^{\Box (p+1)}) \leq \frac{\alpha(G^{\Box \ell} \Box K_k)}{n^{\ell+1}} \sum_{i=0}^{p-\ell} \left(\frac{n-k}{n}\right)^i + \frac{(n-k)^{p-\ell+1}\alpha(G^{\Box \ell})}{n^{p+1}} i ( G □ ( p + 1 ) ) ≤ n ℓ + 1 α ( G □ ℓ □ K k ) ∑ i = 0 p − ℓ ( n n − k ) i + n p + 1 ( n − k ) p − ℓ + 1 α ( G □ ℓ ) 几何级数求和 ：当 p → ∞ p \to \infty p → ∞ α ( G □ ℓ □ K k ) k n ℓ \frac{\alpha(G^{\Box \ell} \Box K_k)}{kn^\ell} k n ℓ α ( G □ ℓ □ K k ) 应用到奇轮 （Corollary 1.4）：由于 W 2 t + 1 W_{2t+1} W 2 t + 1 K 3 K_3 K 3 k = 3 k=3 k = 3 I ( W 2 t + 1 ) ≤ α ( W 2 t + 1 □ ℓ □ K 3 ) 3 ( 2 t + 2 ) ℓ \mathscr{I}(W_{2t+1}) \leq \frac{\alpha(W_{2t+1}^{\Box \ell} \Box K_3)}{3(2t+2)^\ell} I ( W 2 t + 1 ) ≤ 3 ( 2 t + 2 ) ℓ α ( W 2 t + 1 □ ℓ □ K 3 )
关键引理 （Lemma 4.2）：设 I I I W 2 t + 1 □ 2 W_{2t+1}^{\Box 2} W 2 t + 1 □ 2 I ∗ I_* I ∗ ∣ I ∗ ∖ { ( w ∗ , w ∗ ) } ∣ = k |I_* \setminus \{(w_*, w_*)\}| = k ∣ I ∗ ∖ {( w ∗ , w ∗ )} ∣ = k ∣ I ∣ ≤ t ( 2 t + 1 ) + 1 + ( 1 − t ) k |I| \leq t(2t+1) + 1 + (1-t)k ∣ I ∣ ≤ t ( 2 t + 1 ) + 1 + ( 1 − t ) k
精确值 （Proposition 4.3）：
α ( W 2 t + 1 □ 2 ) = ( 2 t + 1 ) t + 1 \alpha(W_{2t+1}^{\Box 2}) = (2t+1)t + 1 α ( W 2 t + 1 □ 2 ) = ( 2 t + 1 ) t + 1
证明思路 ：
构造性下界：显式构造大小为 ( 2 t + 1 ) t + 1 (2t+1)t+1 ( 2 t + 1 ) t + 1 上界证明：使用Lemma 4.2，若 ∣ I ∣ > ( 2 t + 1 ) t + 1 |I| > (2t+1)t+1 ∣ I ∣ > ( 2 t + 1 ) t + 1 k ≥ 2 k \geq 2 k ≥ 2 估计三元积 ：对 W 2 t + 1 □ 2 □ K 3 W_{2t+1}^{\Box 2} \Box K_3 W 2 t + 1 □ 2 □ K 3 S i S_i S i K 3 K_3 K 3 i i i α ( W 2 t + 1 □ 2 □ K 3 ) ≤ 4 t 2 + 6 t \alpha(W_{2t+1}^{\Box 2} \Box K_3) \leq 4t^2 + 6t α ( W 2 t + 1 □ 2 □ K 3 ) ≤ 4 t 2 + 6 t
这直接导致 Theorem 1.5 。
整数规划公式 ：
标准独立集IP：
max ∑ v ∈ V ( G ) x v s.t. B ( G ) T x ≤ 1 , x ∈ { 0 , 1 } ∣ V ( G ) ∣ \max \sum_{v \in V(G)} x_v \quad \text{s.t.} \quad B(G)^T x \leq \mathbf{1}, \quad x \in \{0,1\}^{|V(G)|} max ∑ v ∈ V ( G ) x v s.t. B ( G ) T x ≤ 1 , x ∈ { 0 , 1 } ∣ V ( G ) ∣
笛卡尔积的改进公式 （Program 7）：
对 G □ H G \Box H G □ H x v x_v x v v ∈ V ( H ) v \in V(H) v ∈ V ( H ) max ∑ v ∈ V ( H ) 1 T x v \max \sum_{v \in V(H)} \mathbf{1}^T x_v max ∑ v ∈ V ( H ) 1 T x v s.t. B ( G ) T x v ≤ 1 ∀ v ∈ V ( H ) \text{s.t.} \quad B(G)^T x_v \leq \mathbf{1} \quad \forall v \in V(H) s.t. B ( G ) T x v ≤ 1 ∀ v ∈ V ( H ) x u + x v ≤ 1 ∀ u v ∈ E ( H ) x_u + x_v \leq \mathbf{1} \quad \forall uv \in E(H) x u + x v ≤ 1 ∀ uv ∈ E ( H )
优势 ：可以方便地添加结构约束（如 1 T x v ≥ k \mathbf{1}^T x_v \geq k 1 T x v ≥ k
分支定界策略 （Lemma 6.2-6.4）：
对 W 5 □ 3 W_5^{\Box 3} W 5 □ 3
设 I i I_i I i i i i 按 ∣ I ∗ ∣ , ∣ I 0 ∣ , … , ∣ I 4 ∣ |I_*|, |I_0|, \ldots, |I_4| ∣ I ∗ ∣ , ∣ I 0 ∣ , … , ∣ I 4 ∣ 在每个节点用IP验证可行性 关键计算结果 ：
Lemma 6.2(v)：若 ∣ I ∣ = 58 |I| = 58 ∣ I ∣ = 58 W 5 □ 3 W_5^{\Box 3} W 5 □ 3 i ∈ { ( 9 , 11 , 9 , 11 , 9 , 9 ) , ( 8 , 11 , 9 , 10 , 10 , 10 ) } \mathbf{i} \in \{(9,11,9,11,9,9), (8,11,9,10,10,10)\} i ∈ {( 9 , 11 , 9 , 11 , 9 , 9 ) , ( 8 , 11 , 9 , 10 , 10 , 10 )} Lemma 6.4：排除了 W 5 □ 3 □ K 3 W_5^{\Box 3} \Box K_3 W 5 □ 3 □ K 3 理论创新 ：Theorem 1.3 提供了利用团结构的新方法，不依赖于顶点传递性 极限等式 I ( G ) = lim ℓ → ∞ α ( G □ ℓ □ K k ) k ∣ V ( G ) ∣ ℓ \mathscr{I}(G) = \lim_{\ell \to \infty} \frac{\alpha(G^{\Box \ell} \Box K_k)}{k|V(G)|^\ell} I ( G ) = lim ℓ → ∞ k ∣ V ( G ) ∣ ℓ α ( G □ ℓ □ K k ) 结构洞察 ：Lemma 4.2 建立了独立集大小与中心顶点使用量的精确关系 识别了 W 2 t + 1 □ 2 □ K 3 W_{2t+1}^{\Box 2} \Box K_3 W 2 t + 1 □ 2 □ K 3 计算方法论 ：将理论界与有限计算有机结合 分支定界 + IP的混合策略有效处理了指数级搜索空间 利用自同构群简化分数色数计算（Theorem 5.1） 可复现性 ：所有计算步骤都有对应的代码文件链接 提供了详细的验证路径 独立数计算 ：α ( W 5 □ 2 ) = 11 \alpha(W_5^{\Box 2}) = 11 α ( W 5 □ 2 ) = 11 α ( W 5 □ 3 ) = 58 \alpha(W_5^{\Box 3}) = 58 α ( W 5 □ 3 ) = 58 α ( W 5 □ 2 □ K 3 ) = 29 \alpha(W_5^{\Box 2} \Box K_3) = 29 α ( W 5 □ 2 □ K 3 ) = 29 α ( W 5 □ 3 □ K 3 ) = 170 \alpha(W_5^{\Box 3} \Box K_3) = 170 α ( W 5 □ 3 □ K 3 ) = 170 分数色数计算 ：使用线性规划计算 χ f ( W 2 t + 1 □ 2 ) \chi_f(W_{2t+1}^{\Box 2}) χ f ( W 2 t + 1 □ 2 ) 通过极大独立集的轨道简化约束数量 上界验证 ：α ( W 5 □ 4 ) ≤ 343 \alpha(W_5^{\Box 4}) \leq 343 α ( W 5 □ 4 ) ≤ 343 α ( W 5 □ 4 □ K 3 ) ≤ 1019 \alpha(W_5^{\Box 4} \Box K_3) \leq 1019 α ( W 5 □ 4 □ K 3 ) ≤ 1019 分支定界树 ：
例如Lemma 6.2(v)的验证涉及9个叶节点 每个叶节点对应一个独立的IP实例 所有不可行情况都有对应的代码文件验证 案例分析 ：
对称性利用：通过 W 2 t + 1 W_{2t+1} W 2 t + 1 结构剪枝：利用 α ( W 2 t + 1 □ 2 □ K 3 ) = 29 \alpha(W_{2t+1}^{\Box 2} \Box K_3) = 29 α ( W 2 t + 1 □ 2 □ K 3 ) = 29 2 t + 1 2t+1 2 t + 1 α ( W 2 t + 1 □ 3 ) \alpha(W_{2t+1}^{\Box 3}) α ( W 2 t + 1 □ 3 ) α ( W 2 t + 1 □ 2 □ K 3 ) \alpha(W_{2t+1}^{\Box 2} \Box K_3) α ( W 2 t + 1 □ 2 □ K 3 ) I ( W 2 t + 1 ) ≤ \mathscr{I}(W_{2t+1}) \leq I ( W 2 t + 1 ) ≤ 原有界 5 58 29 1019/3888 ≈ 0.262 11/41 ≈ 0.268 7 156 54 9/32 = 0.281 t/(3t+1) ≈ 0.304 9 336 87 29/100 = 0.29 0.310 11 620 128 8/27 ≈ 0.296 0.314 13 1032 177 59/196 ≈ 0.301 0.317
关键观察 ：
所有新界都显著优于原有界 t 3 t + 1 \frac{t}{3t+1} 3 t + 1 t 对 t ≥ 3 t \geq 3 t ≥ 3 4 t 2 + 6 t 3 ( 2 t + 2 ) 2 \frac{4t^2+6t}{3(2t+2)^2} 3 ( 2 t + 2 ) 2 4 t 2 + 6 t 1 3 \frac{1}{3} 3 1 与猜想值 1 4 \frac{1}{4} 4 1 核心结果 ：α ( W 5 □ 3 □ K 3 ) = 170 \alpha(W_5^{\Box 3} \Box K_3) = 170 α ( W 5 □ 3 □ K 3 ) = 170
证明结构 ：
下界 ：Figure 4 展示了显式的170大小独立集上界 ：通过Lemma 6.2-6.5系统排除了大小≥171的可能性关键引理验证 ：
Lemma 6.2：5个断言，涉及约15个IP实例 Lemma 6.3：处理大小57的情况，6个案例 Lemma 6.4：处理大小170-171的边界情况，约15个IP实例 Lemma 6.5：最终综合，确认只有两种可能的大小分布 Theorem 6.6 ：α ( W 5 □ 4 ) ≤ 343 \alpha(W_5^{\Box 4}) \leq 343 α ( W 5 □ 4 ) ≤ 343
证明思路 ：
假设 ∣ I ∣ = 344 |I| = 344 ∣ I ∣ = 344 利用 α ( W 5 □ 3 □ K 3 ) = 170 \alpha(W_5^{\Box 3} \Box K_3) = 170 α ( W 5 □ 3 □ K 3 ) = 170 推导出矛盾：需要 ∣ I ∗ ∣ = 54 |I_*| = 54 ∣ I ∗ ∣ = 54 ∣ I i ∣ = 58 |I_i| = 58 ∣ I i ∣ = 58 但这要求某些层满足不可能的大小组合（Lemma 6.4） Theorem 6.7 ：α ( W 5 □ 4 □ K 3 ) ≤ 1019 \alpha(W_5^{\Box 4} \Box K_3) \leq 1019 α ( W 5 □ 4 □ K 3 ) ≤ 1019
证明思路 ：
假设 ∣ S ∣ = 1020 |S| = 1020 ∣ S ∣ = 1020 利用Lemma 6.5，每层必须是特定的大小分布 通过鸽巢原理，至少存在一个坐标使得两个不同的 K 3 K_3 K 3 导致总和 ≤ 1019 \leq 1019 ≤ 1019 最终上界 ：
I ( W 5 ) ≤ 1019 3888 ≈ 0.26217 \mathscr{I}(W_5) \leq \frac{1019}{3888} \approx 0.26217 I ( W 5 ) ≤ 3888 1019 ≈ 0.26217
这比1995年的界 11 41 ≈ 0.26829 \frac{11}{41} \approx 0.26829 41 11 ≈ 0.26829 2.3% 。
方法 （Section 5.2）：
通过LP计算 1 χ f ( G ) \frac{1}{\chi_f(G)} χ f ( G ) 1 min z s.t. ∑ v x v = 1 , ∑ v ∈ I x v ≤ z ∀ I ∈ I max ( G ) \min z \quad \text{s.t.} \quad \sum_v x_v = 1, \quad \sum_{v \in I} x_v \leq z \quad \forall I \in \mathcal{I}_{\max}(G) min z s.t. ∑ v x v = 1 , ∑ v ∈ I x v ≤ z ∀ I ∈ I m a x ( G )
自同构群简化 （Theorem 5.1）：
存在最优解在顶点轨道上是常数，因此只需考虑极大独立集的轮廓（profile）。
W₅²的轮廓 （来自7 ）：
( 1 , 0 , 10 ) , ( 0 , 2 , 8 ) , ( 0 , 3 , 6 ) , ( 0 , 4 , 5 ) (1, 0, 10), (0, 2, 8), (0, 3, 6), (0, 4, 5) ( 1 , 0 , 10 ) , ( 0 , 2 , 8 ) , ( 0 , 3 , 6 ) , ( 0 , 4 , 5 ) ( p 1 , p 2 , p 3 ) (p_1, p_2, p_3) ( p 1 , p 2 , p 3 ) T 1 , T 2 , T 3 T_1, T_2, T_3 T 1 , T 2 , T 3
计算结果 ：
χ f ( W 7 □ 2 ) = 39 11 \chi_f(W_7^{\Box 2}) = \frac{39}{11} χ f ( W 7 □ 2 ) = 11 39 χ f ( W 9 □ 2 ) = 127 37 \chi_f(W_9^{\Box 2}) = \frac{127}{37} χ f ( W 9 □ 2 ) = 37 127 χ f ( W 5 □ 3 ) = 722 189 \chi_f(W_5^{\Box 3}) = \frac{722}{189} χ f ( W 5 □ 3 ) = 189 722 观察到的模式 （Conjecture 7.3）：
χ f ( W 2 t + 1 □ 2 ) = 6 t 2 + 7 t + 3 2 t 2 + t + 1 \chi_f(W_{2t+1}^{\Box 2}) = \frac{6t^2 + 7t + 3}{2t^2 + t + 1} χ f ( W 2 t + 1 □ 2 ) = 2 t 2 + t + 1 6 t 2 + 7 t + 3
这将给出 I ( W 2 t + 1 ) ≥ 2 t 2 + t + 1 6 t 2 + 7 t + 3 \mathscr{I}(W_{2t+1}) \geq \frac{2t^2+t+1}{6t^2+7t+3} I ( W 2 t + 1 ) ≥ 6 t 2 + 7 t + 3 2 t 2 + t + 1 1 3 \frac{1}{3} 3 1
Appendix A ：展示了 W 2 t + 1 □ 2 □ K 3 W_{2t+1}^{\Box 2} \Box K_3 W 2 t + 1 □ 2 □ K 3 W 2 t + 1 □ 2 W_{2t+1}^{\Box 2} W 2 t + 1 □ 2
Figure 5：W 5 □ 2 □ K 3 W_5^{\Box 2} \Box K_3 W 5 □ 2 □ K 3 Figure 6：W 7 □ 2 □ K 3 W_7^{\Box 2} \Box K_3 W 7 □ 2 □ K 3 Figure 7：W 9 □ 2 □ K 3 W_9^{\Box 2} \Box K_3 W 9 □ 2 □ K 3 Figure 8：W 11 □ 2 □ K 3 W_{11}^{\Box 2} \Box K_3 W 11 □ 2 □ K 3 结构观察 （Conjecture 7.1）：
α ( W 2 t + 1 □ 2 □ K 3 ) = ( 2 t + 2 ) α ( W 2 t + 1 ) − ( t − 1 ) = 4 t 2 + 5 t + 3 \alpha(W_{2t+1}^{\Box 2} \Box K_3) = (2t+2)\alpha(W_{2t+1}) - (t-1) = 4t^2 + 5t + 3 α ( W 2 t + 1 □ 2 □ K 3 ) = ( 2 t + 2 ) α ( W 2 t + 1 ) − ( t − 1 ) = 4 t 2 + 5 t + 3
即最大3-可着色子图的阶为 4 t 2 + 5 t + 3 4t^2 + 5t + 3 4 t 2 + 5 t + 3
奠基工作 ：Hell, Yu, Zhou (1994)：形式化定义，证明极限存在性 Hahn, Hell, Poljak (1995)：建立基本界 1 χ ≤ I ≤ 1 ω \frac{1}{\chi} \leq \mathscr{I} \leq \frac{1}{\omega} χ 1 ≤ I ≤ ω 1 一般界的紧性 ：Zhu (1996)：构造了 1 χ < I < 1 χ f \frac{1}{\chi} < \mathscr{I} < \frac{1}{\chi_f} χ 1 < I < χ f 1 引入星色数（star chromatic number）给出新界 相关极限问题 ：Shannon容量：lim k → ∞ α ( G ⊠ k ) k \lim_{k \to \infty} \sqrt[k]{\alpha(G^{\boxtimes k})} lim k → ∞ k α ( G ⊠ k ) 分类独立比（Albert et al. 2001） 张量图幂（Alon & Lubetzky 2007） 色数与团数 ：偶轮：χ = ω = 3 \chi = \omega = 3 χ = ω = 3 奇轮：χ = 4 \chi = 4 χ = 4 ω = 3 \omega = 3 ω = 3 分数色数 ：χ f ( W 2 t + 1 ) = 3 + 1 t \chi_f(W_{2t+1}) = 3 + \frac{1}{t} χ f ( W 2 t + 1 ) = 3 + t 1 χ f ( C 2 t + 1 ) = 2 + 1 t \chi_f(C_{2t+1}) = 2 + \frac{1}{t} χ f ( C 2 t + 1 ) = 2 + t 1 笛卡尔积的独立数 ：Proposition 2.1：α ( G □ H ) ≤ min { ∣ V ( G ) ∣ α ( H ) , ∣ V ( H ) ∣ α ( G ) } \alpha(G \Box H) \leq \min\{|V(G)|\alpha(H), |V(H)|\alpha(G)\} α ( G □ H ) ≤ min { ∣ V ( G ) ∣ α ( H ) , ∣ V ( H ) ∣ α ( G )} 整数规划 ：标准独立集IP（Program 6） 笛卡尔积的改进公式（Program 7） 分数色数计算 ：LP公式（Program 8） 对称性利用（Theorem 5.1） 图同态 ：Theorem 1.1：若存在同态 G → H G \to H G → H I ( H ) ≤ I ( G ) \mathscr{I}(H) \leq \mathscr{I}(G) I ( H ) ≤ I ( G ) 这给出了基本界的证明 理论贡献 ：提出了利用团结构的新上界方法（Theorem 1.3） 对所有 t ≥ 3 t \geq 3 t ≥ 3 4 t 2 + 6 t 3 ( 2 t + 2 ) 2 \frac{4t^2+6t}{3(2t+2)^2} 3 ( 2 t + 2 ) 2 4 t 2 + 6 t 计算突破 ：精确确定 α ( W 5 □ 3 □ K 3 ) = 170 \alpha(W_5^{\Box 3} \Box K_3) = 170 α ( W 5 □ 3 □ K 3 ) = 170 改进了5-轮的30年未改进的上界 方法论 ：展示了理论分析与计算验证的有效结合 提供了完整的可复现框架 与猜想的差距 ：新界 1019 3888 ≈ 0.262 \frac{1019}{3888} \approx 0.262 3888 1019 ≈ 0.262 1 4 = 0.25 \frac{1}{4} = 0.25 4 1 = 0.25 大奇轮的界 4 t 2 + 6 t 3 ( 2 t + 2 ) 2 \frac{4t^2+6t}{3(2t+2)^2} 3 ( 2 t + 2 ) 2 4 t 2 + 6 t 1 3 \frac{1}{3} 3 1 1 4 \frac{1}{4} 4 1 计算限制 ：无法直接计算 α ( W 5 □ 4 ) \alpha(W_5^{\Box 4}) α ( W 5 □ 4 ) 更高阶的计算（如 χ f ( W 7 □ 3 ) \chi_f(W_7^{\Box 3}) χ f ( W 7 □ 3 ) 理论工具 ：Lemma 4.2的界可能不够紧 需要更深入的结构理解 一般化 ：方法高度依赖于轮图的特殊结构 对其他非完美图的适用性未知 作者在Section 7提出了多个猜想：
Conjecture 7.1 （结构猜想）：
α ( W 2 t + 1 □ 2 □ K 3 ) = 4 t 2 + 5 t + 3 \alpha(W_{2t+1}^{\Box 2} \Box K_3) = 4t^2 + 5t + 3 α ( W 2 t + 1 □ 2 □ K 3 ) = 4 t 2 + 5 t + 3 I ( W 2 t + 1 ) ≤ 4 t 2 + 5 t + 3 3 ( 2 t + 2 ) 2 \mathscr{I}(W_{2t+1}) \leq \frac{4t^2+5t+3}{3(2t+2)^2} I ( W 2 t + 1 ) ≤ 3 ( 2 t + 2 ) 2 4 t 2 + 5 t + 3 Conjecture 7.2 ：α ( W 5 □ 4 ) = 338 \alpha(W_5^{\Box 4}) = 338 α ( W 5 □ 4 ) = 338 I ( W 5 ) \mathscr{I}(W_5) I ( W 5 ) Conjecture 7.3 （分数色数模式）：
χ f ( W 2 t + 1 □ 2 ) = 6 t 2 + 7 t + 3 2 t 2 + t + 1 \chi_f(W_{2t+1}^{\Box 2}) = \frac{6t^2 + 7t + 3}{2t^2 + t + 1} χ f ( W 2 t + 1 □ 2 ) = 2 t 2 + t + 1 6 t 2 + 7 t + 3 I ( W 2 t + 1 ) ≥ 2 t 2 + t + 1 6 t 2 + 7 t + 3 \mathscr{I}(W_{2t+1}) \geq \frac{2t^2+t+1}{6t^2+7t+3} I ( W 2 t + 1 ) ≥ 6 t 2 + 7 t + 3 2 t 2 + t + 1 Conjecture 7.4 （方法优势）：
对所有 t ≥ 3 t \geq 3 t ≥ 3 ℓ ≥ 1 \ell \geq 1 ℓ ≥ 1 α ( W 2 t + 1 □ ℓ □ K 3 ) 3 ( 2 t + 2 ) ℓ < 1 χ f ( W 2 t + 1 □ ℓ ) \frac{\alpha(W_{2t+1}^{\Box \ell} \Box K_3)}{3(2t+2)^\ell} < \frac{1}{\chi_f(W_{2t+1}^{\Box \ell})} 3 ( 2 t + 2 ) ℓ α ( W 2 t + 1 □ ℓ □ K 3 ) < χ f ( W 2 t + 1 □ ℓ ) 1 Conjecture 7.5 （一般化）：
对 χ > ω \chi > \omega χ > ω G G G H H H χ ( H ) ≤ ω ( G ) \chi(H) \leq \omega(G) χ ( H ) ≤ ω ( G ) c c c χ f ( G ) < c ⋅ ω ( G ) ∣ V ( G ) ∣ ∣ V ( H ) ∣ \chi_f(G) < c \cdot \frac{\omega(G)|V(G)|}{|V(H)|} χ f ( G ) < c ⋅ ∣ V ( H ) ∣ ω ( G ) ∣ V ( G ) ∣ 理论创新性 ：Theorem 1.3提供了新的理论工具，不依赖于特殊的图类假设 极限等式建立了计算途径 Lemma 4.2揭示了奇轮笛卡尔积的深层结构 方法严谨性 ：理论证明清晰完整 计算部分有完整的验证路径 每个计算断言都有对应的代码文件 实际突破 ：30年来首次改进 I ( W 5 ) \mathscr{I}(W_5) I ( W 5 ) 对所有大奇轮给出了统一的理论界 可复现性 ：代码完全开源 详细的计算框架说明（Section 5） 可视化辅助理解（Appendix A） 写作质量 ：结构清晰，逻辑严密 适当的背景介绍 技术细节与直观解释平衡良好 与猜想的距离 ：新界仍不足以证明或证伪Conjecture 1.2 理论界的渐近行为（趋向1/3）与猜想值（1/4）不匹配 计算瓶颈 ：依赖于个人电脑的计算能力 无法处理更高阶的情况（如 W 5 □ 5 W_5^{\Box 5} W 5 □ 5 分数色数的计算对大图极其困难 理论工具的局限 ：Lemma 4.2的界可能不够紧（差距约 t t t 没有给出 α ( W 2 t + 1 □ 2 □ K 3 ) \alpha(W_{2t+1}^{\Box 2} \Box K_3) α ( W 2 t + 1 □ 2 □ K 3 ) 一般化不足 ：方法高度定制于轮图 对其他 χ > ω \chi > \omega χ > ω 下界工作 ：对领域的贡献 ：重新激活了一个30年的公开问题 提供了新的理论工具（Theorem 1.3） 可能启发其他非完美图的研究 实用价值 ：计算框架可用于其他图的极限独立比研究 整数规划方法具有一般性 理论意义 ：揭示了团结构在极限独立比中的作用 连接了独立数、色数和分数色数 开放性 ：直接应用 ：图同态理论中的不可同态性证明 网络编码中的Shannon容量相关问题 方法论借鉴 ：结合理论界和有限计算的混合方法 分支定界 + IP的策略 利用对称性简化计算 推广方向 ：其他临界图的极限独立比 其他图积（如强积、字典积）的类似问题 Hahn, Hell, Poljak (1995) ：奠基性论文，建立基本理论框架Zhu (1996) ：证明一般界的紧性Hell, Yu, Zhou (1994) ：极限独立比的形式化定义Scheinerman & Ullman (2011) ：分数图论教材Hammack et al. (2011) ：图积手册本文在奇轮图的极限独立比这一30年未解决问题上取得了实质性进展。通过创新的理论工具（Theorem 1.3）、深入的结构分析（Lemma 4.2）和系统的计算验证，作者改进了所有奇轮的上界，特别是将5-轮的界从0.268改进到0.262。虽然与猜想值0.25仍有距离，但这是该领域的重要一步。论文方法严谨，可复现性强，为后续研究提供了坚实基础。主要挑战在于如何进一步缩小理论界与猜想值的差距，这可能需要对奇轮笛卡尔积的独立集结构有更深刻的理解。
