文献

J-GLOBAL ID：202002227385002772   整理番号：20A1865104

スパースグラフにおけるタイプの数について【JST・京大機械翻訳】

On the number of types in sparse graphs

著者 (3件)： Pilipczuk Michal (Institute of Informatics, University of Warsaw, Poland) ,  Siebertz Sebastian (Institute of Informatics, University of Warsaw, Poland) ,  Torunczyk Szymon (Institute of Informatics, University of Warsaw, Poland)
資料名： ACM Proceedings  (ACM Proceedings)
号： LICS ’18  ページ： 799-808  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： NesetriとOssona de Mendez[28,29],およびすべての一次式φ(x,y)によって定義される,どこでも高密度でないグラフLのあらゆるクラスに対して,1つがグラフG∈LとノードAの部分集合を描いたとき,Gにおけるxのいくつかの評価uに対するA|y|の部分集合の数は,あらゆるΔ|0に対してO(|A:G|=φ(u,v)})によって有界である。これは,高密度グラフクラスにおける一次定義可能集合システムのVC密度に関する最適限界を提供した。また,それらの論理的処理に関連する高密度クラスにおける量に関する上限の2つの新しい証明を与えた。第1に,著者らは,どこでも高密度クラスが均一準幅であるという事実の新しい証明を提供し,2つの概念に関連する関数に関する明示的で多項式上の上限を暗示した。第2に,著者らはAdlerとAdler[1]の結果の新しい組合せ証明を与えて,あらゆるどこでも高密度クラスのグラフが安定しているというわけではない。上記の結果の以前の証明とは対照的に,著者らの証明は,完全に,完全で,建設的であり,均一準広幅(マージン)と安定性(膀胱指数)に関連する量に関して,明示的で計算可能な上限を与える。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *多項式 ,  膀胱
準シソーラス用語： 有界 , 【Automatic Indexing@JST】

著者キーワード (6件)： 密なグラフはない ,  ストーンスペース ,  VC密度 ,  一次型 ,  安定性 ,  均一準幅

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

タイトルに関連する用語 (2件)： タイプ ,  数