关于改进有限图Cheeger常数上下界的技术问询
关于改进有限图Cheeger常数上下界的技术问询
大家好,我目前在研究一个包含17个顶点、55条边的简单连通有限图$\Gamma$,目标是计算它的Cheeger常数。先明确一下有限图Cheeger常数的定义:
$$h(\Gamma) = \min\left{\frac{#\partial X}{# X},\bigg\vert, X \subseteq V(\Gamma), 0 < # X \leq \frac{1}{2}#V(\Gamma)\right}$$
下面是我已经完成的探索工作:
- 考虑含2个顶点的集合$X$,得到上界 $h(\Gamma) \leq 7/2$
- 分析3-团和3个顶点的独立集,将上界改进到 $h(\Gamma) \leq 10/3$
- 已经验证过,任何独立集都无法突破$10/3$这个上界
- 同样,4-团也不能进一步优化这个上界
- 考虑一个近似4-团的集合$X$,把上界更新到了 $h(\Gamma) \leq 3$
现在我想请教大家:有没有什么方法或者不等式可以帮我进一步改进$h(\Gamma) \leq 3$这个上界,或者给出$h(\Gamma)$的下界?我已经计算了这个图的很多其他不变量,比如团数、独立数、支配数等,这些都可以用来辅助计算。
备注:内容来源于stack exchange,提问作者Joseph Harrison
相关产品推荐
相关产品推荐

