Related papers: A Spectral Proof of the Hypergraph Moore Bound

A Spectral Proof of the Hypergraph Moore Bound

URL: http://arxiv.org/abs/2607.26028v1
Date: Tue, 28 Jul 2026 17:38:31 GMT
Title: A Spectral Proof of the Hypergraph Moore Bound
Abstract summary: We prove Feige's 2008 conjecture on the hypergraph Moore bound.<n>For every $kge3$ and every $1leellle n$, any $k$-uniform hypergraph on $n$ vertices with more than $C,nk/2/ellk/2-1$ hyperedges contains an even cover of size at most $A,elllog(en/ell)$.
Score: 46.26532142699448
License: http://creativecommons.org/licenses/by/4.0/
Abstract: A nonempty subfamily of a $k$-uniform hypergraph is an \emph{even cover} if every vertex lies in an even number of its hyperedges; for $k=2$ these are edge-disjoint unions of cycles, so the minimum size of an even cover is the natural hypergraph analogue of girth. We prove Feige's 2008 conjecture on the hypergraph Moore bound: there are absolute constants $A$ and $C$ (independent of $k$) such that for every $k\ge3$ and every $1\le\ell\le n$, any $k$-uniform hypergraph on $n$ vertices with more than $C\,n^{k/2}/\ell^{k/2-1}$ hyperedges contains an even cover of size at most $A\,\ell\log(en/\ell)$. Our proof is based on sharp spectral bounds for Kikuchi matrices, which we expect to be of independent interest; we apply them to the refutation of random constraint satisfaction problems in a companion paper.

Related papers

The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
arXiv Detail & Related papers (2026-08-03T17:57:01Z)
Almost all graphs are vertex-minor universal [0.0]
We prove that the uniformly random graph $Gsim mathrmvm(k)$ is $(sqrt n)$-vertex-minor universal with high probability.<n>This has direct implications for quantum communications networks.
arXiv Detail & Related papers (2026-02-06T20:59:33Z)
Detecting Arbitrary Planted Subgraphs in Random Graphs [7.320365821066746]
We investigate the detection of an empharbitrary planted subgraph $Gamma = Gamma_n$ in an ErdHos-R'enyi random graph $mathcalG(n, q_n)$.<n>In the dense regime, where the edge probabilities $p_n$ and $q_n$ are fixed, we tightly characterize the information-theoretic and computational thresholds for detecting $Gamma$.
arXiv Detail & Related papers (2025-03-24T18:54:43Z)
Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
arXiv Detail & Related papers (2024-02-23T12:22:03Z)
Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z)
Monogamy of entanglement between cones [43.57338639836868]
We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones.<n>Our proof makes use of a new characterization of products of simplices up to affine equivalence.
arXiv Detail & Related papers (2022-06-23T16:23:59Z)
Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
This topic is an important direction in the modern statistical theory of kernel-based methods.<n>We discuss a number of consequences of our bounds and show that they are substantially tighter than bounds for general kernels.
arXiv Detail & Related papers (2022-04-09T16:45:22Z)
Random Subgraph Detection Using Queries [29.192695995340653]
The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
arXiv Detail & Related papers (2021-10-02T07:41:17Z)
Linear Bandits on Uniformly Convex Sets [88.3673525964507]
Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
arXiv Detail & Related papers (2021-03-10T07:33:03Z)
Phase Squeezing of Quantum Hypergraph States [0.0]
A quantum hypergraph state is defined by $|Grangle = frac1sqrt2dsum_n = 02d - 1 (-1)f(n) |n rangle$. We establish that these states are squeezed in the phase quadrature only and satisfy the Agarwal-Tara criterion for non-classicality.
arXiv Detail & Related papers (2020-08-31T18:31:13Z)
Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
arXiv Detail & Related papers (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.