You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

关于改进有限图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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.23 13:37:32