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の拡張(報告者の上記論文参照)を考え, 対応する上界式の等号達成の可能性についても, 構成例をもとに議論した.さらに, 上記で用いた手法の応用として, センシング行列の構成問題などの国際共同研究にも従事した.

延续前一年，我们对图不对称理论进行了延伸研究，首先，根据前一年观察到的图不对称性与扩展图的研究密切相关，我们提出了Erdos-Renyi不等式（We）。获得了比原始渐近最佳定理更强的论据（ER不等式），即基于Thomassen（1989）对随机图展开常数的评估，在随机图中，以高概率，我们证明，对于几乎任何自同构，为了将其转换为具有该自同构的图，需要添加或删除超过不对称数（AN）下界的数中的边。这个结果和例外的考虑。继续考虑问题的自同构，一个例子是双重常规锦标赛（DRT），其中使用凯莱图的思想构建大量非同构DRT，这是一个几乎实现这一点的候选示例，这在考虑时也很重要。演讲者（2017）提出的渐近最佳定理的一种改进在实际图的情况下， Erdos-Spencer (1974) 之前有一项研究，通过将“局部变形”应用于平等成就示例的候选者来构造渐近平等成就示例，并且考虑到锦标赛的扩展，这种想法似乎对锦标赛也有效。 AN 的版本（参见上面作者的论文），我们还讨论了使用配置示例实现相应上界公式相等的可能性，他还参与了传感矩阵构建问题的国际联合研究。

项目成果

Cayley graphs constructed from the field trace

从现场轨迹构建的凯莱图

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

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

关于 t-e.c. 的评论

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

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;澤正憲;佐竹翔平;佐竹翔平;佐竹翔平;佐竹翔平
• 通讯作者: 佐竹翔平

New Ramanujan graphs from Galois rings

伽罗瓦环的新拉马努金图

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