文献

J-GLOBAL ID：201802242268535969   整理番号：18A0576804

グラフのminor-closedクラスのための論理的極限則【Powered by NICT】

Logical limit laws for minor-closed classes of graphs

著者 (4件)： Heinig Peter (Mathematisches Seminar, Universitaet Hamburg, Hamburg, Germany) ,  Mueller Tobias (Groningen University, Groningen, The Netherlands) ,  Noy Marc (Barcelona Graduate School of Mathematics and Universitat Politecnica de Catalunya, Barcelona, Spain) ,  Taraz Anusch (Hamburg University of Technology, Hamburg, Germany)
資料名： Journal of Combinatorial Theory. Series B  (Journal of Combinatorial Theory. Series B)
巻： 130  ページ： 158-206  発行年： 2018年 
JST資料番号： E0780A  ISSN： 0095-8956  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Gはグラフの追加,minor-closedクラスとする。零一乗則はnの頂点上のG中の全ての連結グラフから一様に無作為に描き出されるランダムなグラフのための単子的第二近似解論理(MSO)であることを証明し,nの頂点上のG中の全てのグラフから一様に無作為に引き出すかどうかMSOにおける収束則が成り立つ。固定表面上に埋込み可能なグラフのクラスに対するこれらの結果の類似体を証明し,一次論理(FO)に注意を限定した。さらに,与えられたFO文が満足される限界確率は表面に依存しない。も確率限界のセットの閉鎖は,少なくとも二個の背反する間隔の有限な和集合が常に存在することを,FOとMSOに対して同じであることを証明した。森林と平面グラフのクラスに対して,確率限界のセットの閉鎖を正確に決定することができた。平面グラフに対して,正確に108間隔,同じ長さの各約5.3910 6から構成されている。最後に,挙動は全く異なる非追加可能な諸クラスの例を解析した。例えば,零一乗則はnの頂点上のランダム毛虫の保持,FOでもしなかった。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 平面グラフ ,  *グラフ
準シソーラス用語： 近似解 ,  連結グラフ , 【Automatic Indexing@JST】

著者キーワード (3件)： ランダムグラフ ,  グラフ小行列式 ,  論理的極限則

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

タイトルに関連する用語 (3件)： グラフ ,  クラス ,  極限