| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2019-03-18 11:45 ［招待講演］The Diameter of Dense Random Regular Graphs ○清水伸高（東大/理研）  COMP2018-48 |
|
| 抄録 | （和） | 自然数$n,d$に対して$n$頂点$d$正則グラフ全体の中で最小直径をもつ グラフを考える. この問題はグラフ理論において深く研究されており, Moore boundを用いると$n$頂点$d$正則グラフのとりうる直径の下界 $D_0(n,d)$が導出され, $ntoinfty$のとき$D_0(n,d)=(1-o(1))log_{d-1}n$ が分かる. 本研究では, $n$頂点$d$正則グラフ全体の集合から一様ランダムに選んだ グラフ$G_{n,d}$が持つ直径$mathrm{diam}(G_{n,d})$の$ntoinfty$における 漸近的な分布を考える. 次数$dgeq 3$が$n$に依存しない定数である場合, 漸近的に確率$1$で $mathrm{diam}(G_{n,d})-D_0(n,d)=O(loglog n)$となることが知られている [Bollob'as and de la Vega, 1982]. 本研究では定数$alphain(0,1),beta>0$に対して$d=(beta+o(1))n^alpha$となるとき, 漸近的に確率$1$で$mathrm{diam}(G_{n,d})=lflooralpha^{-1}rfloor+1$となることを示す. この結果により, $alpha^{-1}$が整数かつ$beta<1$ならば, 漸近的に$mathrm{diam}(G_{n,d})=D_0(n,d)+1$ が成り立ち, $alpha^{-1}$が非整数もしくは$beta<1$ならば漸近的に$mathrm{diam}(G_{n,d})=D_0(n,d)$が 成り立つことが分かる. |
| （英） | For fixed $n$ and $d$, we consider a graph with minimum diameter among all $d$-regular graphs on $n$ vertices. This problem is well-explored in graph theory and the Moore bound implies a lower bound $D_0(n,d)$ on the diameter of any $d$-regular graph of order $n$. Actually, the diameter $mathrm{diam}(G_{n,d})$ of a random $d$-regular graph $G_{n,d}$ on $n$ vertices is known to be asymptotically near-optimal as $ntoinfty$: Bollob'as and de la Vega (1982) proved that $mathrm{diam}(G_{n,d})=(1+o(1))D_0(n,d)=(1+o(1))log_{d-1}n$ holds w.h.p. (with high probability) for fixed $dgeq 3$, whereas there exists a gap $mathrm{diam}(G_{n,d})-D_0(n,d)=Omega(log log n)$. In this work, we investigate the gap $mathrm{diam}(G_{n,d})-D_0(n,d)$ for $d=(beta+o(1))n^{alpha}$ where $alphain(0,1)$ and $beta>0$ are arbitrary constants. We prove that $mathrm{diam}(G_{n,d})=lfloor alpha^{-1} rfloor+1$ holds w.h.p. for such $d$. Our result implies that the gap is $1$ if $alpha^{-1}$ is an integer and $dgeq n^alpha$, and is $0$ otherwise. One can easily obtain that $mathrm{diam}(G_{n,d})leq lflooralpha^{-1}rfloor+1$ holds w.h.p. by using the embedding theorem due to Dudek et al.~(2017). Our critical contribution is to show that $mathrm{diam}(G_{n,d})geq lflooralpha^{-1}rfloor+1$ holds w.h.p. by the analysis of the distances of fixed vertex pairs. |
|
| キーワード | （和） | ランダム正則グラフ / 直径 / / / / / / |
| （英） | Random regular glaph / Diameter / / / / / / | |
| 文献情報 | 信学技報, vol. 118, no. 517, COMP2018-48, pp. 41-41, 2019年3月. | |
| 資料番号 | COMP2018-48 | |
| 発行日 | 2019-03-11 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2018-48 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2019-03-18 - 2019-03-18 |
| 開催地（和） | 東京大学 |
| 開催地（英） | The University of Tokyo |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2019-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | The Diameter of Dense Random Regular Graphs |
| サブタイトル（和） | |
| タイトル（英） | The Diameter of Dense Random Regular Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ランダム正則グラフ / Random regular glaph |
| キーワード(2)（和/英） | 直径 / Diameter |
| キーワード(3)（和/英） | / |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 清水 伸高 / Nobutaka Shimizu / シミズ ノブタカ |
| 第1著者 所属（和/英） | 東京大学/理化学研究所 (略称： 東大/理研) The University of Tokyo/RIKEN (略称： Univ. Tokyo/RIKEN AIP) |
| 講演者 | 第1著者 |
| 発表日時 | 2019-03-18 11:45:00 |
| 発表時間 | 60分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2018-48 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.517 |
| ページ範囲 | p.41 |
| ページ数 | 1 |
| 発行日 | 2019-03-11 (COMP) |
[研究会発表申込システムのトップページに戻る]