文献

J-GLOBAL ID：202002279411723682   整理番号：20A2215343

平方証明の和なしの簡単なグラフ密度不等式【JST・京大機械翻訳】

Simple Graph Density Inequalities with No Sum of Squares Proofs

著者 (4件)： Blekherman Grigoriy (School of Mathematics, Georgia Institute of Technology, Atlanta, GA, USA) ,  Raymond Annie (Department of Mathematics and Statistics Lederle Graduate Research Tower, 1623D University of Massachusetts Amherst, Amherst, MA, USA) ,  Singh Mohit (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA) ,  Thomas Rekha R. (Department of Mathematics, University of Washington, Seattle, WA, USA)
資料名： Combinatorica  (Combinatorica)
巻： 40  号： 4  ページ： 455-471  発行年： 2020年 
JST資料番号： A1051A  ISSN： 0209-9683  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： グラフ密度間の不等式を確立することは,極値結合器における中心追跡である。グラフ密度表現の非負性を証明する標準ツールは,それを平方和として書き込むことである。本論文では,グラフ密度表現が二乗和であることができない簡単な条件を同定した。この結果を用いて,Blakley-Roy不等式は,経路長が奇数であるとき,平方証明書の和を持たないことを証明した。また,同じBlakley-Roy不等式は,平方和の乗算器を用いて,二乗の和によって保証できないことを示した。これらの結果はLovaszによって提起された2つの疑問に答えた。著者らの主なツールは,Sidorenkoの推測された不等式の最小開放ケースが平方和によって保証できないことを示すために再び使用される。最後に,この設定は,RazborovとLovasz-Szegedyによる既存のフレームワークと等価であり,従って,これらの設定に留まることを示した。Copyright Janos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *不等式 ,  乗算器 ,  結合器 ,  奇数
準シソーラス用語： 証明書 ,  平方和 , 【Automatic Indexing@JST】

著者キーワード (3件)： 05C35 ,  90C22 ,  90C35

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 証明 ,  グラフ ,  密度 ,  不等式