A simple and sharper proof of the hypergraph Moore bound
A simple and sharper proof of the hypergraph Moore bound
复制标题
超图摩尔界的简单而清晰的证明
DOI：
10.48550/arxiv.2207.10850
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Sidhanth Mohanty
中科院分区：
文献类型：
--
作者：
Jun;Pravesh Kothari;Sidhanth Mohanty
超图的摩尔界是一个优雅的陈述，它描述了围长（最小圈或偶覆盖（所有度都是偶的子超图）中超边的数量）和尺寸（超图中超边的数量）之间的极端权衡。对于图（即，$2$-一致超图），Alon、Hoory和Linial的经典著作[AHL 02]中证明了与主导常数紧密相关的界。对于一致性k>2的超图，Feige [Fei 08]给出了一个适当的推广.该猜想解决了一个额外的$\log^{4k+1} n$因子的大小在最近的工作Guruswami，Kothari和Manohar [GKM 21]。他们的论证依赖于短偶覆盖的存在性与某个随机符号菊池矩阵的谱之间的联系。他们的分析，特别是对于奇数k的情况，是非常复杂的。在这项工作中，我们提出了一个大大简化和更短的超图摩尔界的证明。我们的关键思想是使用一个新的重新加权的菊池矩阵和边缘删除步骤，使我们能够在[GKM 21]的分析中删除几个相关的步骤，例如菊池矩阵的行的组合桶和使用Schudy-Sviridenko多项式浓度。我们更简单的证明也获得了更严格的参数：特别地，该论证给出了[AHL 02]的经典摩尔界的新证明，没有损失（[GKM 21]中的证明损失了$\log^3 n$因子），并且对于所有$k>2$-一致超图只损失了一个对数因子。在[GKM 21]中，我们的想法自然地扩展到产生一个更简单的证明，充分权衡强烈反驳光滑的约束满足问题的情况下，类似的改进参数。
The hypergraph Moore bound is an elegant statement that characterizes the extremal trade-off between the girth - the number of hyperedges in the smallest cycle or even cover (a subhypergraph with all degrees even) and size - the number of hyperedges in a hypergraph. For graphs (i.e., $2$-uniform hypergraphs), a bound tight up to the leading constant was proven in a classical work of Alon, Hoory and Linial [AHL02]. For hypergraphs of uniformity $k>2$, an appropriate generalization was conjectured by Feige [Fei08]. The conjecture was settled up to an additional $\log^{4k+1} n$ factor in the size in a recent work of Guruswami, Kothari and Manohar [GKM21]. Their argument relies on a connection between the existence of short even covers and the spectrum of a certain randomly signed Kikuchi matrix. Their analysis, especially for the case of odd $k$, is significantly complicated. In this work, we present a substantially simpler and shorter proof of the hypergraph Moore bound. Our key idea is the use of a new reweighted Kikuchi matrix and an edge deletion step that allows us to drop several involved steps in [GKM21]'s analysis such as combinatorial bucketing of rows of the Kikuchi matrix and the use of the Schudy-Sviridenko polynomial concentration. Our simpler proof also obtains tighter parameters: in particular, the argument gives a new proof of the classical Moore bound of [AHL02] with no loss (the proof in [GKM21] loses a $\log^3 n$ factor), and loses only a single logarithmic factor for all $k>2$-uniform hypergraphs. As in [GKM21], our ideas naturally extend to yield a simpler proof of the full trade-off for strongly refuting smoothed instances of constraint satisfaction problems with similarly improved parameters.
DOI：
10.1137/1.9781611975482.140
发表时间：
2018-04
期刊：
ArXiv
影响因子：
--
作者：
Y. Deshpande;A. Montanari;R. O'Donnell;T. Schramm;S. Sen
通讯作者：
Y. Deshpande;A. Montanari;R. O'Donnell;T. Schramm;S. Sen
局部算法求解半定程序的效果如何？
DOI：
10.1145/3055399.3055451
发表时间：
2017
期刊：
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Fan, Zhou;Montanari, Andrea
通讯作者：
Montanari, Andrea