多項式限界によるハイパーグラフ除去【JST・京大機械翻訳】

Gishboliner Lior; Shapira Asaf

プレプリント

J-GLOBAL ID：202202211450938802 整理番号：22P0290179

多項式限界によるハイパーグラフ除去【JST・京大機械翻訳】

Hypergraph removal with polynomial bounds

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年02月15日プレプリントサーバーでの情報更新日： 2022年02月15日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

固定k-均一超グラフFを与えられた場合,F-除去補助定理は,少数のエッジの除去によってFフリーのF-フリーをF-フリーにする。残念なことに,一般Fに対しては,含まれる定数は,インクリメンタルな高速成長Ackermann型関数によって与えられる。したがって,Fが多項式限界で除去補助定理を証明できるのは自然である。そのような限界が得られる1つの自明なケースは,Fがk-パートトであるときである。Alonは,k=2(すなわちグラフを扱う場合)の場合,二部グラフだけが多項式除去補助定理を持つことを証明した。Kohyakawa,NagleおよびR”odolは,Alonの結果がすべてのk>2に拡張できる,すなわち,ハイパーグラフ除去補助定理が多項式限界を持つ唯一のkグラフFは,Fがk-pariteであるとき,自明なケースである。本論文では,この予想を証明した。【JST・京大機械翻訳】

, , , ,
, , 【Automatic Indexing@JST】

グラフ理論基礎

, ,

前のページに戻る