Fugu-MT 論文翻訳(概要): A Spectral Proof of the Hypergraph Moore Bound

論文の概要: A Spectral Proof of the Hypergraph Moore Bound

arxiv url: http://arxiv.org/abs/2607.26028v1
Date: Tue, 28 Jul 2026 17:38:31 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-29 20:50:42.951465
Title: A Spectral Proof of the Hypergraph Moore Bound
Title（参考訳）: ハイパーグラフムーア境界のスペクトル証明
Abstract要約: ハイパーグラフムーア境界に関するファイゲの2008年の予想を証明する。すべての$kge3$と$1leellle n$に対して、$n$ vertices 上の任意の $k$-uniform hypergraph は、$C,nk/2/ellk/2-1$ hyperedges は、最大$A,elllog(en/ell)$で偶数被覆を含む。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: k$-uniform hypergraph の空でない部分群は、すべての頂点がそのハイパーエッジの偶数にあるときに \emph{even cover} である。すべての$k\ge3$ とすべての $1\le\ell\le n$ に対して、$C\,n^{k/2}/\ell^{k/2-1}/\ell^{k/2-1}$ の頂点上の任意の $k$-uniform ハイパーグラフは、最大$A\,\ell\log(en/\ell)$ の偶数被覆を含む。筆者らの証明は,木口行列のスペクトル境界の急激な独立性に基づくものである。

関連論文リスト

The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文参考訳（メタデータ） (2026-08-03T17:57:01Z)
Almost all graphs are vertex-minor universal [0.0]
均一にランダムなグラフ $Gsim Mathrmvm(k)$ が、高い確率で $(sqrt n)$-vertex-minor Universal であることを証明する。これは量子通信ネットワークに直接的な意味を持つ。
論文参考訳（メタデータ） (2026-02-06T20:59:33Z)
Detecting Arbitrary Planted Subgraphs in Random Graphs [7.320365821066746]
本稿では,ErdHos-R'enyi乱数グラフ$mathcalG(n, q_n)$における仮設植木部分グラフ$Gamma = Gamma_n$の検出について検討する。エッジ確率が$p_n$と$q_n$が固定された高密度な状態では、Gamma$を検出するための情報理論および計算しきい値が強く特徴付けられる。
論文参考訳（メタデータ） (2025-03-24T18:54:43Z)
Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文参考訳（メタデータ） (2024-02-23T12:22:03Z)
Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文参考訳（メタデータ） (2023-04-17T10:38:08Z)
Monogamy of entanglement between cones [43.57338639836868]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文参考訳（メタデータ） (2022-06-23T16:23:59Z)
Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
論文参考訳（メタデータ） (2022-04-09T16:45:22Z)
Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文参考訳（メタデータ） (2021-10-02T07:41:17Z)
Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文参考訳（メタデータ） (2021-03-10T07:33:03Z)
Phase Squeezing of Quantum Hypergraph States [0.0]
量子ハイパーグラフ状態は、$|Grangle = frac1sqrt2dsum_n = 02d - 1 (-1)f(n) |n rungle$で定義される。これらの状態は第4相でのみ圧縮され、非古典性に対するアガルワル・タラ基準を満たすことが確認される。
論文参考訳（メタデータ） (2020-08-31T18:31:13Z)
Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。我々はCIFARに関する実験結果を示し,その理論を検証した。
論文参考訳（メタデータ） (2020-02-08T22:02:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。