文献

J-GLOBAL ID：202202218672728924   整理番号：22A0433908

ランダム摂動高密度グラフにおける小さなレインボークリーク【JST・京大機械翻訳】

Small rainbow cliques in randomly perturbed dense graphs

著者 (4件)： Aigner-Horev Elad (Department of Computer Science, Ariel University, Ariel 40700, Israel) ,  Danon Oran (Department of Computer Science, Ariel University, Ariel 40700, Israel) ,  Hefetz Dan (Department of Computer Science, Ariel University, Ariel 40700, Israel) ,  Letzter Shoham (Department of Mathematics, University College London, Gower Street, London, WC1E 6BT, UK)
資料名： European Journal of Combinatorics  (European Journal of Combinatorics)
巻： 101  ページ： Null  発行年： 2022年 
JST資料番号： A1229A  ISSN： 0195-6698  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 2つのグラフGとHに対して,Gがそのエッジのあらゆる適切な彩色がHの rainbowコピーを生じる性質を持つならば,G→rbwHを書き込む。著者らは,Gが少なくともd>0のエッジ密度を有するn-頂点グラフであり,dがnと無関係である,Gがn-頂点グラフである,ランダム摂動高密度グラフにおけるそのようないわゆる反Ramsey特性のための閾値を研究した。コンパニオン論文において,著者らは,特性G∪G(n,p)→rbwKlの閾値が,l≧9のとき,n-1/m2(Kl/2)であることを立証した。より小さなlでは,閾値は,より不規則に挙動し,4≦l≦7では,それらは,大きなクリークの閾値を捉える前述の美的形式から,下方に逸脱する。特に,l∈{4,5,7}の閾値は,それぞれn-5/4,n-1,およびn-7/15であることを示した。l≡6,8}に対して,指数における(1+o(1))因子までの閾値を決定し,それらはそれぞれn-(2/3+o(1))およびn-(2/5+o(1))であった。l=3では,閾値はn-2;これは,著者らのコンパニオン論文における奇数サイクルについてのより一般的な結果に従う。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 奇数 ,  *摂動

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

タイトルに関連する用語 (5件)： 摂動 ,  高密度 ,  グラフ ,  レインボー ,  クリーク