TY - GEN

T1 - A simple and sharper proof of the hypergraph Moore bound

AU - Hsieh, Jun Ting

AU - Kothari, Pravesh K.

AU - Mohanty, Sidhanth

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - The hypergraph Moore bound 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, a bound tight up to the leading constant was proven in a classical work of Alon, Hoory and Linial [3]. For hypergraphs of uniformity k > 2, an appropriate generalization was conjectured by Feige [14]. The conjecture was settled up to an additional log4k+1 n factor in the size in a recent work of Guruswami, Kothari and Manohar [16]. 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 trick that allows us to drop several involved steps in [16]'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 [3] with no loss (the proof in [16] loses a log3 n factor), and loses only a single logarithmic factor for all k > 2-uniform hypergraphs. As in [16], 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.

AB - The hypergraph Moore bound 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, a bound tight up to the leading constant was proven in a classical work of Alon, Hoory and Linial [3]. For hypergraphs of uniformity k > 2, an appropriate generalization was conjectured by Feige [14]. The conjecture was settled up to an additional log4k+1 n factor in the size in a recent work of Guruswami, Kothari and Manohar [16]. 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 trick that allows us to drop several involved steps in [16]'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 [3] with no loss (the proof in [16] loses a log3 n factor), and loses only a single logarithmic factor for all k > 2-uniform hypergraphs. As in [16], 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.

UR - http://www.scopus.com/inward/record.url?scp=85163078340&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163078340&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85163078340

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2324

EP - 2344

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Y2 - 22 January 2023 through 25 January 2023

ER -