Generalization and Refinement of Erdo"s-Re'nyi Theory for Asymmetry of Random Graphs

点击翻译按钮获取中文摘要

前年度に引き続きグラフの非対称性の理論の拡張研究を行った. まず, 前年度に得た, グラフの非対称性がエクスパンダーグラフの研究と密接に関わりうるという観察にもとづき, Erdos-Renyi不等式 (ER不等式)のオリジナルの漸近最良性定理より強い主張を得た. 即ち, Thomassen (1989)によるランダムグラフの拡大定数の評価をもとに, ランダムグラフにおいては高確率で, ほとんどすべての自己同型に対して, その自己同型をもつグラフに変形するために, asymmetry number (AN)の下界を超える数の辺の追加, 除去が必要であることを証明した. この結果と例外的な自己同型に対する考察から, (高確率でランダムグラフが満たすという主張の形の)漸近最良性定理の改良が期待される.また, Erdos-Moon (1965)による「ランク付け」できないトーナメントの構成問題を引き続き考察し, その一例が二重正則トーナメント (DRT)であることを示し, 非同型なDRTをCayleyグラフのアイデアを用いて多数構成した. DRTは報告者 (2017)によるトーナメント版のANに対するER不等式の等号をほぼ達成する例の候補である. また, 報告者 (2017)が示した漸近最良性定理の一種の改良を考えるうえでも重要である. 実際グラフの場合において, 等号達成例の候補に「局所変形」を施して漸近的な等号達成例を構成するErdos-Spencer (1974)の先行研究があり, このアイデアはトーナメントに対しても有効と思われる. また, トーナメント版のANの拡張(報告者の上記論文参照)を考え, 対応する上界式の等号達成の可能性についても, 構成例をもとに議論した.さらに, 上記で用いた手法の応用として, センシング行列の構成問題などの国際共同研究にも従事した.