.png){kind=icon}
返回
Bisection width, discrepancy, and eigenvalues of hypergraphs
.png){kind=icon}
OA
AI
DOI：10.1016/j.jctb.2025.11.003.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
阿隆1993年的一项著名结果指出，任何n个顶点的d-正则图（其中d=O(n^{1/9})）都有一个边数不超过(dn)^{(2)}( (1)^{(2)}-Ω((1)(\sqrt{d})))的二分，并且这是最优的。最近，这一结果被R & auml;ty、Sudakov和Tomon大幅扩展。我们基于后者的思想，采用受半定规划启发的方法证明了超图的一个变体：每个n个顶点的r-均匀d-正则超图（其中d << n^{1/2}）都有一个大小不超过(dn)^{(r)}( 1-(1) (2r-1)-(c)(\sqrt{d}) )的二分，其中c = c(r) > 0。这一界在精确的c值范围内是最优的。此外，可以通过多项式时间的随机算法找到一个达到此界的二分。最小二分与偏差密切相关。我们还证明了超图及其所谓的正偏差的精确界，扩展了Bollob & aacute;s和Scott的结果。此外，我们讨论了关于Alon-Boppana类型界的影响。我们证明，如果H是一个r-均匀d-正则超图，则与邻接张量根相关的第二大特征值λ^{(2)}的某些概念满足λ^{(2)} ≥ Ω_{r}(\sqrt{d})，改进了Li和Mohar的结果。(c) 2025 作者。由Elsevier Inc.出版。这是一篇开放获取文章，遵循CC BY许可（http:// creativecommons.org/licenses/by/4.0/）。
Keyword:
Discrepancy
Bisection width
Eigenvalue
Alon-Boppana theorem
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
J
IF:
1.2
论文数:
48
被引数:
0
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容