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不平等现象（ER不平等）更强的主张。换句话说，基于Thomassen（1989）对随机图的膨胀常数的评估，我们证明，对于几乎所有的自动形态，对不对称数（AN）的边缘的添加和去除是必要的，以转换为具有较高概率的图形。从这个结果和对特殊自身形态的考虑，我们期望渐近良性定理会有所改善（以声称随机图满足高概率的形式）。此外，我们继续考虑构建无法“排名”的比赛的问题（1965年），并表明此示例是一个双重常规比赛（DRT），并且我们使用Cayley图的想法构建了大量的非同质DRT。 DRT是一个示例的候选人，几乎可以实现AN比赛版本的ER不平等的平等标志。考虑记者（2017）提出的渐近良性定理的一种改进也很重要。就图表而言，先前对Erdos-Spencer（1974）进行了一项研究，该研究使用“局部变换”形成一个渐近的符号示例，以实现渐近的符号示例，而这个想法似乎对比赛有效。我们还考虑了锦标赛版本中A的扩展（请参阅记者的上述论文），并且还根据示例结构讨论了实现上限方程相应的相应平等标志的可能性。此外，作为上述方法的应用，他还参与了有关传感矩阵结构问题的国际协作研究。

项目成果

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