作者： Bence Csonka, Gábor Simonyi
提交日期： 2023年12月14日
主题分类： 组合数学 (math.CO); 信息论 (cs.IT)
MSC 分类： 05C76, 94A24, 05C15, 05C50
摘要：
本文研究了著名的 Mycielski 构造对图的香农容量及其最突出的上界之一——（互补）Lovász θ 数的影响。我们证明，如果一个图（作为噪声信道的可区分图）的香农容量可由某个有限幂次达到，那么它的 Mycielskian 图具有严格大于原图的香农容量。对于互补 Lovász θ 函数，我们证明了其在图的 Mycielskian 上的值完全由其在原图上的值决定，这一现象与 Larsen、Propp 和 Ullman 在分数色数中发现的情况类似。我们还考虑了将我们的结果推广到有向图的 Sperner 容量和广义 Mycielski 构造的可能性。文中也讨论了与 Zuiddam 所称的图的渐近谱的可能联系。
其他信息： 论文共 28 页加附录，包含一张图。