A simple and sharper proof of the hypergraph Moore bound

Jun Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages2324-2344
Number of pages21
ISBN (Electronic)9781611977554
StatePublished - 2023
Externally publishedYes
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period1/22/231/25/23

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'A simple and sharper proof of the hypergraph Moore bound'. Together they form a unique fingerprint.

Cite this