ユニバーサルグラフ

数学において、ユニバーサルグラフは、すべての 有限（または最大で可算）グラフを誘導サブグラフとして含む無限グラフです。このタイプのユニバーサルグラフは、リチャード・ラドー^[1]^[2]によって最初に構築され、現在ではラドーグラフまたはランダムグラフと呼ばれています。より最近の研究^[3]^[4]は、グラフファミリ $F$ のユニバーサルグラフ、つまりFに属する無限グラフで、 $F$ 内のすべての有限グラフを含むものに焦点を合わせています。たとえば、ヘンソングラフは、 $i-$ クリークフリーグラフに対してこの意味でユニバーサルです。

グラフの族 $Fのユニバーサルグラフは、$ $F$ 内のすべてのグラフを含む有限グラフのシーケンスのメンバーを指すこともできます。たとえば、すべての有限木は十分に大きなハイパーキューブグラフのサブグラフであるため^[5] 、ハイパーキューブは木のユニバーサルグラフであると言えます。ただし、これはそのようなグラフの最小値ではありません。 $n$ 頂点の木には、 $n$ 個の頂点と $O(n log n)$ 個のエッジのみを持つユニバーサルグラフが存在し、これが最適であることがわかっています。^[6]平面セパレータ定理に基づく構成を使用して、 $n$ 頂点平面グラフには $O (n 3/2)$ 個のエッジを持つユニバーサルグラフがあり、次数が制限された平面グラフには $O(n log n)$ 個のエッジを持つユニバーサルグラフがあることを示すことができます。^[7]^[8]^[9] $n 1+ o (1) 個$ の頂点を持つ平面グラフのユニバーサルグラフを構築することもできます。^[10] サムナーの予想によれば、トーナメントは多木に対して普遍的であり、2n−2個の頂点を持つすべてのトーナメントには $n 個$ $の頂点を$ $持つ$ すべての多木がサブグラフとして含まれるという。^[11]

グラフ族 $Fには、$ $n頂点グラフを$ 誘導サブグラフとして含む多項式サイズのユニバーサルグラフが存在するが、これは、頂点を $O$ $(log$ $n$ $)$ ビットのビット文字列でラベル付けできる隣接ラベル付けスキームが存在する場合に限ります。このスキームでは、アルゴリズムは 2 つの頂点がラベルを調べることで隣接しているかどうかを判断できます。このタイプのユニバーサルグラフが存在する場合、 $F$ 内の任意のグラフの頂点は、ユニバーサルグラフ内の対応する頂点の ID でラベル付けでき、逆に、ラベル付けスキームが存在する場合、すべての可能なラベルの頂点を持つユニバーサルグラフを構築できます。^[12]

古い数学用語では、「ユニバーサルグラフ」という語句が完全グラフを表すために使用されることがありました。

ユニバーサルグラフの概念は、平均利得ゲームを解くために採用され、使用されてきた。^[13]

参考文献

^ R. ラドー(1964)。「普遍的なグラフと普遍的な関数」。アクタ算術。9 (4): 331–340。土井: 10.4064/aa-9-4-331-340。MR 0172268。
^ Rado, R. (1967). 「ユニバーサルグラフ」.グラフ理論セミナー. Holt, Rinehart, Winston. pp. 83–85. MR 0214507.
^ Goldstern, Martin; Kojman, Menachem (1996). 「ユニバーサル矢印フリーグラフ」. Acta Mathematica Hungarica . 1973 (4): 319–326. arXiv : math.LO/9409206 . doi : 10.1007/BF00052907 . MR 1428038.
^ Cherlin, Greg; Shelah, Saharon ; Shi, Niandong (1999). 「禁止サブグラフと代数的閉包を持つユニバーサルグラフ」.応用数学の進歩. 22 (4): 454–491. arXiv : math.LO/9809202 . doi :10.1006/aama.1998.0641. MR 1683298. S2CID 17529604.
^ Wu, AY (1985). 「ツリーネットワークのハイパーキューブへの埋め込み」.並列分散コンピューティングジャーナル. 2 (3): 238–249. doi :10.1016/0743-7315(85)90026-7.
^ Chung, FRK ; Graham, RL (1983). 「全域木のユニバーサルグラフについて」(PDF) .ロンドン数学会誌. 27 (2): 203–211. CiteSeerX 10.1.1.108.3415 . doi :10.1112/jlms/s2-27.2.203. MR 0692525. 。
^ Babai, L. ; Chung, FRK ; Erdős, P. ; Graham, RL ; Spencer, JH (1982). 「すべてのスパースグラフを含むグラフについて」。Rosa, Alexander、Sabidussi, Gert、Turgeon, Jean (編)。組合せ論の理論と実践: Anton Kotzig の 60 歳の誕生日を記念した論文集(PDF)。Annals of Discrete Mathematics。第 12 巻。pp. 21–26。MR 0806964。
^ Bhatt, Sandeep N.; Chung, Fan RK ; Leighton, FT ; Rosenberg, Arnold L. (1989). 「制限次数木と平面グラフのユニバーサルグラフ」. SIAM Journal on Discrete Mathematics . 2 (2): 145–155. doi :10.1137/0402014. MR 0990447.
^ Chung, Fan RK (1990)。「セパレータ定理とその応用」。Korte , Bernhard、Lovász, László、Prömel, Hans Jürgen、他編。パス、フロー、および VLSI レイアウト。アルゴリズムと組み合わせ論。第 9 巻。Springer-Verlag。pp. 17–34。ISBN 978-0-387-52685-0. MR 1083375。
^ ドゥイモヴィッチ、ヴィダ;ルイス、エスペレット。ジョレット、グエナエル。ガヴォイユ、シリル。ミチェク、ピョートル。モーリン、パット (2021)、「平面グラフの隣接ラベル付け (およびその先)」、Journal of the ACM、68 (6): 1–33、arXiv : 2003.04280、doi :10.1145/3477542
^ Sumner の Universal Tournament Conjecture、Douglas B. West、2010 年 9 月 17 日閲覧。
^ Kannan, Sampath; Naor, Moni ; Rudich, Steven (1992)、「グラフの暗黙的表現」、SIAM Journal on Discrete Mathematics、5 (4): 596–603、doi :10.1137/0405049、MR 1186827。
^ Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). 「分離オートマトン内でのユニバーサルツリーの成長: パリティゲームの準多項式下限」。第30回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録。pp. 2333–2349。arXiv : 1807.10546。doi : 10.1137 / 1.9781611975482.142。ISBN 978-1-61197-548-2. S2CID 51865783。

外部リンク

木の普遍グラフに関する「今日の定理」、汎樹木公式

[1] R. ラドー(1964)。「普遍的なグラフと普遍的な関数」。アクタ算術。9 (4): 331–340。土井: 10.4064/aa-9-4-331-340。MR 0172268。

[2] Rado, R. (1967). 「ユニバーサルグラフ」.グラフ理論セミナー. Holt, Rinehart, Winston. pp. 83–85. MR 0214507.

[3] Goldstern, Martin; Kojman, Menachem (1996). 「ユニバーサル矢印フリーグラフ」. Acta Mathematica Hungarica . 1973 (4): 319–326. arXiv : math.LO/9409206 . doi : 10.1007/BF00052907 . MR 1428038.

[4] Cherlin, Greg; Shelah, Saharon ; Shi, Niandong (1999). 「禁止サブグラフと代数的閉包を持つユニバーサルグラフ」.応用数学の進歩. 22 (4): 454–491. arXiv : math.LO/9809202 . doi :10.1006/aama.1998.0641. MR 1683298. S2CID 17529604.

[5] Wu, AY (1985). 「ツリーネットワークのハイパーキューブへの埋め込み」.並列分散コンピューティングジャーナル. 2 (3): 238–249. doi :10.1016/0743-7315(85)90026-7.

[6] Chung, FRK ; Graham, RL (1983). 「全域木のユニバーサルグラフについて」(PDF) .ロンドン数学会誌. 27 (2): 203–211. CiteSeerX 10.1.1.108.3415 . doi :10.1112/jlms/s2-27.2.203. MR 0692525. 。

[7] Babai, L. ; Chung, FRK ; Erdős, P. ; Graham, RL ; Spencer, JH (1982). 「すべてのスパースグラフを含むグラフについて」。Rosa, Alexander、Sabidussi, Gert、Turgeon, Jean (編)。組合せ論の理論と実践: Anton Kotzig の 60 歳の誕生日を記念した論文集(PDF)。Annals of Discrete Mathematics。第 12 巻。pp. 21–26。MR 0806964。

[8] Bhatt, Sandeep N.; Chung, Fan RK ; Leighton, FT ; Rosenberg, Arnold L. (1989). 「制限次数木と平面グラフのユニバーサルグラフ」. SIAM Journal on Discrete Mathematics . 2 (2): 145–155. doi :10.1137/0402014. MR 0990447.

[9] Chung, Fan RK (1990)。「セパレータ定理とその応用」。Korte , Bernhard、Lovász, László、Prömel, Hans Jürgen、他編。パス、フロー、および VLSI レイアウト。アルゴリズムと組み合わせ論。第 9 巻。Springer-Verlag。pp. 17–34。ISBN 978-0-387-52685-0. MR 1083375。

[10] ドゥイモヴィッチ、ヴィダ;ルイス、エスペレット。ジョレット、グエナエル。ガヴォイユ、シリル。ミチェク、ピョートル。モーリン、パット (2021)、「平面グラフの隣接ラベル付け (およびその先)」、Journal of the ACM、68 (6): 1–33、arXiv : 2003.04280、doi :10.1145/3477542

[11] Sumner の Universal Tournament Conjecture、Douglas B. West、2010 年 9 月 17 日閲覧。

[12] Kannan, Sampath; Naor, Moni ; Rudich, Steven (1992)、「グラフの暗黙的表現」、SIAM Journal on Discrete Mathematics、5 (4): 596–603、doi :10.1137/0405049、MR 1186827。

[13] Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). 「分離オートマトン内でのユニバーサルツリーの成長: パリティゲームの準多項式下限」。第30回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録。pp. 2333–2349。arXiv : 1807.10546。doi : 10.1137 / 1.9781611975482.142。ISBN 978-1-61197-548-2. S2CID 51865783。