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

随机图不对称性Erdo"s-Renyi理论的推广与细化

• 批准号: 18J11282
• 负责人: 佐竹 翔平
• 金额: $ 0.96万
• 依托单位: Kobe University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-25 至 2020-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18J11282/
• 关键词: Asymmetry number; Cayleyグラフ; Erdos-Renyi不等式; エクスパンダー; 漸近最良性定理; 二重正則トーナメント; ランダムグラフ; エクスパンダーグラフ

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

A study on the theory of symmetry and symmetry in the past year has been carried out. In the previous year, the author obtained the theorem of asymptotic most benign from Erdos-Renyi inequality (ER inequality). That is, Thomassen (1989) adds the lower bound of asymmetry number (AN) to the upper bound of the number (AN), except where necessary. The result of this paper is that the improvement of asymptotically most benign theorem is expected. Erdos-Moon (1965): A case study of the composition of a doubly regular DRT (DRT) is presented. DRT Report (2017): The Equal Sign of ER Inequality The author (2017) shows an improvement of the asymptotically most benign theorem. Erdos-Spencer (1974) made a preliminary study on the application of the "local shape" of the equal sign achievement example candidate. A discussion on the possibility of reaching the upper bound equation and the composition example. In addition, the above mentioned methods and methods are used to solve the problem of the formation of the ranks and international joint research.

项目成果

Cayley graphs constructed from the field trace

从现场轨迹构建的凯莱图

• 发表时间: 2019
• 作者: Shohei Satake;Masanori Sawa;Masakazu Jimbo;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平
• 通讯作者: 佐竹翔平

Erdo"s-Re'nyi theory for asymmetric digraphs

非对称有向图的 Erdo"s-Renyi 理论

• 发表时间: 2018
• 期刊: SUT Journal of Mathematics
• 作者: Shohei Satake;Masanori Sawa;Masakazu Jimbo
• 通讯作者: Masakazu Jimbo

ランダムグラフがもつ性質について

关于随机图的性质

• 发表时间: 2018
• 作者: 佐竹翔平;吉田和輝;Frederick Kin Hing Phoa;澤正憲;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平
• 通讯作者: 佐竹翔平

A remark on t-e.c. graphs, pseudo-random graphs and expander graphs

关于 t-e.c. 的评论

• 发表时间: 2018
• 作者: 佐竹翔平;吉田和輝;澤正憲;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平
• 通讯作者: 佐竹翔平

On pseudo-randomness of digraphs and ranking tournaments

关于有向图和排名锦标赛的伪随机性

• 发表时间: 2019
• 作者: Shohei Satake;Masanori Sawa;Masakazu Jimbo;佐竹翔平;佐竹翔平;佐竹翔平
• 通讯作者: 佐竹翔平