純対 III  多項式サイズの反完全対を持たないスパースグラフ【JST・京大機械翻訳】

Chudnovsky Maria; Fox Jacob; Scott Alex; Seymour Paul; Spirkl Sophie

文献

J-GLOBAL ID：202002230948659163 整理番号：20A2230734

純対 III 多項式サイズの反完全対を持たないスパースグラフ【JST・京大機械翻訳】

Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=20A2230734&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A2230734&from=J-GLOBAL&jstjournalNo=C0773B") }}

著者 (5件)： , , , ,
資料名：
巻： 95 号： 3 ページ： 315-340 発行年： 2020年
JST資料番号： C0773B ISSN： 0364-9024 CODEN： JGTHD 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

グラフは,[数式:原文を参照]に対して誘導サブグラフ同形でないならば,[数式:原文を参照]フリーであり,|G|は,[数式:原文を参照]の頂点の数を示す。Conlon,Sudakovおよび第2著者の予想は,あらゆるグラフ[数式:原文を参照]に対して,|G|を有するあらゆる[数式:原文を参照]フリーグラフ[数式:原文を参照]において,少なくとも[数式:原文を参照]および[数式:原文を参照],完全または反完全の2つの互いに素な頂点が存在するような[数式:原文を参照]が存在する。これは,あらゆるグラフ[数式:原文を参照]に対して,いくつかの頂点が少なくとも[数式:原文を参照]で,または,少なくとも[数式:原文を参照]と[数式:原文を参照]の2つの互いに素な集合があり,少なくとも[数式:原文を参照]と[数式:原文を参照]の2つの互いに素な集合があるような,”スパース線形予測”は,[数式:原文を参照]が存在している。”sparse linear sulation”は,[数式:原文を参照]が存在する,というのは,それぞれ,互いに完全なものがある,という点である.。”sparse linear superation”は,それぞれ,少なくとも[数式:原文を参照]で,または,少なくとも[数式:原文を参照]と[数式:原文を参照]の2つの互いに素な集合がある,という点である。スパース線形予測に対する多くの部分結果を証明した。特に,筆者らは大きなクラスのグラフ[数式:原文を参照]に対して保持し,全てのグラフ[数式:原文を参照]に対して,そのように,何がも保持することを証明した。より厳密には,[数式:原文を参照]が三角形フリーで,[数式:原文を参照]が安定セットに分割され,そして,ほとんどの1つで最大値のグラフを誘発するセットに,[数式:原文を参照]が「ほとんど二者」である。(これは,少なくとも1回,あらゆるエッジを分割することによって他のグラフから生じるすべてのグラフを含む),著者らの主な結果は,すべてのほぼ二者グラフ[数式:原文を参照]に対して,スパース線形予測が成立する。([数式:原文を参照]が三角形[数式:原文を参照]である場合)。また,すべてのグラフ[数式:原文を参照]に対して,[数式:原文を参照]頂点を持つあらゆる[数式:原文を参照]フリーグラフ[数式:原文を参照]において,いくつかの頂点が少なくとも[数式:原文を参照]の度合を持つか,または,[数式:原文を参照]と頂点の2つの互いに素な集合[数式:原文を参照]が存在するようなスパース線形予測に関するいくつかの変化も証明する。Copyright 2020 Wiley Publishing Japan K.K. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

, ,
, 【Automatic Indexing@JST】

著者キーワード (2件)： ,

グラフ理論基礎

前のページに戻る