2025-11-22T13:01:16.233287

On The Roots of Independence Polynomial: Quantifying The Gap

Prakash, Sharma

The independence polynomial of a graph $G$ is the generating polynomial corresponding to its independent sets of different sizes. More formally, if $a_k(G)$ denotes the number of independent sets of $G$ of size $k$ then \[I(G,z) \as \sum_{k}^{} (-1)^k a_k(G) z^k.\] The study of evaluating $I(G,z)$ has several deep connections to problems in combinatorics, complexity theory and statistical physics. Consequently, the roots of the independence polynomial have been studied in detail. In particular, many works have provided regions in the complex plane that are devoid of any roots of the polynomial. One of the first such results showed a lower bound on the absolute value of the smallest root $Î²(G)$ of the polynomial. Furthermore, when $G$ is connected, Goldwurm and Santini established that $Î²(G)$ is a simple real root of $I(G,z)$ smaller than one. An alternative proof was given by CsikvÃ¡ri. Both proofs do not provide a gap from $Î²(G)$ to the smallest absolute value amongst all the other roots of $I(G,z)$. In this paper, we quantify this gap.

academic

On The Roots of Independence Polynomial: Quantifying The Gap

基本信息

论文ID: 2510.09197
标题: On The Roots of Independence Polynomial: Quantifying The Gap
作者: Om Prakash (The Institute of Mathematical Sciences, HBNI, Chennai, India), Vikram Sharma (The Institute of Mathematical Sciences, HBNI, Chennai, India)
分类: math.CO (Combinatorics), cs.DM (Discrete Mathematics)
发表时间: October 13, 2025 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.09197

摘要

本文研究图的独立多项式的根的分布问题。独立多项式 $I(G,z) := \sum_k (-1)^k a_k(G) z^k$ 是对应于图G不同大小独立集的生成多项式，其中 $a_k(G)$ 表示图G中大小为k的独立集数量。该多项式在组合数学、复杂性理论和统计物理中有重要应用。已知当G连通时， $\beta(G)$ （最小实根）是小于1的简单实根，且其他所有根的绝对值都严格大于 $\beta(G)$ 。本文首次量化了 $\beta(G)$ 与其他根之间的间隙。

研究背景与动机

问题背景：独立多项式的研究在多个领域有重要意义：
- 组合数学中的计数问题
- 复杂性理论中的近似算法设计
- 统计物理中的硬核模型
现有研究的局限性：
- Goldwurm和Santini证明了 $\beta(G)$ 是唯一的最小实根
- Csikvári提供了替代证明
- 但这些证明都是存在性的，无法量化 $\beta(G)$ 与其他根之间的具体间隙
研究动机：
- 量化根之间的间隙对算法设计具有重要意义
- 可能为某些图类设计高效算法提供理论基础
- 填补理论上的空白

核心贡献

主要理论结果：证明了对于n个顶点的连通图G，以原点为中心、半径为 $\beta(G) + (\beta(G)/n)^{O(n)}$ 的圆盘内只包含最小根 $\beta(G)$
技术创新：
- 使用Smale的γ函数研究局部函数行为
- 构造majorant函数来上界复函数的绝对值
- 结合复分析中的单值性半径理论
具体图类的显式下界：为路径图、环图和完全二部图提供了精确的根间隙计算
方法论贡献：提供了一种系统性的方法来量化多项式根之间的分离

方法详解

任务定义

给定连通图G，量化独立多项式 $I(G,z)$ 的最小根 $\beta(G)$ 与其他根之间的最小间隙。

核心技术框架

1. 关键函数定义

对于任意顶点 $u \in V$ ，定义： $f_u(z) := \frac{zI(G \setminus N[u], z)}{I(G \setminus u, z)}$

其中 $N[u]$ 是顶点u的闭邻域。

2. 两步证明策略

第一步：局部单值性

定义 $r_G := \frac{\beta(G) \cdot \text{dia}(G)}{2n}$
证明 $I(G,z)$ 在 $D(\beta(G), r_G/2)$ 内是单射的

第二步：全局根分离

对圆周 $\beta(G)e^{i\theta}$ 上的每个点，构造不包含根的圆盘
使用majorant函数技术处理函数的绝对值

3. Majorant函数构造

对于基础情况 $\frac{z}{(1-z)^{\ell}}$ ，其在 $re^{i\theta}$ 上的majorant函数为： $g_r(\theta) := \frac{r}{(1-r\cos\theta)^{\ell}}$

递归地，对于更复杂的函数： $F_{u,r}(\theta) := \frac{r}{(1-r\cos\theta)^{\ell} \prod_j(1-G_{j,r}(\theta))}$

技术创新点

γ函数的应用：首次将Smale的γ函数应用于独立多项式的根分析
Majorant函数技术：创新性地使用单调递减的majorant函数来控制复函数的行为
几何与代数的结合：将复分析的几何直观与图论的代数结构巧妙结合

实验设置

理论验证

本文主要是理论工作，通过以下方式验证结果：

具体图类计算：
- 路径图 $P_n$
- 环图 $C_n$
- 完全二部图 $K_{n \times n}$
数值验证：
- 星图 $S_3$ 的函数行为分析
- 绘制绝对值函数图像验证理论预测

评价标准

理论界的紧致性
与已知结果的一致性
计算的可行性

路径图 $P_n$ ： $\frac{\alpha}{\beta} = 1 + \Omega\left(\frac{1}{n^2}\right)$
环图 $C_n$ ： $\frac{\alpha}{\beta} = 1 + \frac{2\pi^2}{n^2} + O(n^{-4})$
完全二部图 $K_{n \times n}$ ： $\frac{|\alpha|}{\beta} \approx 9.119 - O\left(\frac{1}{n^2}\right)$