構造を持つランダムグラフの構造

Aug 18 2020

背景
^{[これをスキップして、すぐに定義に進むことができます。]}

（ランダム）グラフまたはネットワークの重要な機能は次のとおりです。

度分布 $p(d)$ （指数法則、ポアソン法則、またはべき法則）
平均度 $\bar{d}$
平均クラスタリング係数 $\bar{C}$
平均距離 $L$ と直径 $D$

頻繁に発揮するために必要とされている、ランダムに生成されたグラフスモールワールド性、すなわち$L\propto \log N$ そして $\bar{C}$「小さくない」です。これらの条件の少なくとも1つに対処するいくつかのランダムグラフモデルがあります。

ワット-Strogatzモデル（基礎となる正則環格子付き）
Barabasiアルバートモデル（好ましいアタッチメント付）
構成モデル（与えられた程度の配列と、RESP。ディストリビューション）
ニューマンモデル（組み込む群集構造）

Watts-StrogatzモデルとBarabasi-AlbertモデルはErdős–Rényiモデルの修正版であり、Newmanモデルは構成モデルの特定の一般化ですが、これらすべてのモデルの中で最高です。（参考依頼）

ワッツ-Strogatzのとニューマンの両方のモデルを一般化、私はそれをランダムグラフを調査したいのですが、「近いERグラフに無作為化構造の間を補間し、[いくつかの任意の定期的なグラフ]」（からの引用ウィキペディア）。

このために、私は手元にたくさんの正則グラフを持っていたいです。

体系的に象徴され、列挙され、
それらのシンボル（すなわち、それらの隣接行列）から簡単に生成され、そして
おそらく小さな世界の特徴のための閉じた形の表現 $L$ そして $\bar{C}$

私が考えている正則グラフは、例によって最も簡単に説明できます。

定義

頂点構成を頂点を表すグラフとします。 $\nu$ すぐ隣の人と $\nu_0,\nu_2,\dots,\nu_{d-1}$ 連続するネイバーの各ペア間の（任意の長さの）最短パス $\nu_i, \nu_{i+1}$。頂点構成は、記号で体系化できます$(n_1.n_2.\dots.n_k)^m$ それは、それを伝えます $\nu$ 学位を持っている $d = m \cdot k$ に囲まれています $m$-の周期列 $n_i$-それぞれの顔。最短サイクル。（これは、グラフ理論の言語でのジオメトリの頂点構成の標準的な定義に他なりません。）

例：

$(4)^4$

頂点は特定の頂点構成を持っていると言われます $\Gamma$ その近隣と近隣間の1つの最短経路が同型である場合 $\Gamma$。グラフは特定の頂点構成を持っていると言われます$\Gamma$ すべての頂点が頂点構成になっている場合 $\Gamma$。頂点構成は、それを含むグラフがある場合に実現可能であると言われます。

ここで、すべての頂点が同じ頂点構成を持つ有限グラフについて考えてみます。

質問

すべての頂点構成ですか $\Gamma$多かれ少なかれ任意のサイズのグラフで実現可能ですか？これを証明または反証する方法は？
^{これは、球の周期的タイリング（つまり正多面体）を定義しないすべての頂点構成（ジオメトリの意味で）がユークリッド平面または双曲平面の周期的タイリングを定義するかどうかという問題と関係があります。}

実現不可能な頂点構成がある場合：特定の頂点構成が実現可能かどうかを確認するにはどうすればよいですか？

与えられた頂点構成でグラフを作成します $\Gamma$ 頂点推移的である必要がありますか？

同じ頂点構成を持つ2つの頂点推移グラフの（等しい）数の頂点は、それらが同型であることを保証しないため、どの一般的な手段でそれらの「形状」を定義できるので、2つの等しく定義されたグラフは同型でなければなりませんか？（例については、以下を参照してください。）

与えられた実現可能な頂点構成と「形状」の隣接行列を生成する体系的な方法はありますか？

「形状」とは、ドルビリンとシュルテが論文「単型タイリングの局所定理」で「近隣複合体（コロナ）」と呼んでいるものを意味します。

例

頂点構成を検討する $(4)^4$ そして数字で定義される「形」 $(4, 6)$

形状の反対側の頂点をリンクする場合、すべての頂点は同じ頂点構成になります $(4)^4$さらに、結果のグラフは頂点推移的です。

直径を見つける $D = 5$、クラスタリング係数 $\bar{C} = 0$、および平均距離 $L =\frac{1}{23}(4\times 1 + 7 \times 2 + 7 \times 3 + 4 \times 4 + 1 \times 5) \approx 2.61$ 閉じたまたは再帰的な明示的な式を見つけるために（ $(n,m)$）実行可能のようです。

「形」について

私たちが見つけたのと同じ頂点構成と頂点の数で $D = 5$ と平均距離 $L =\frac{1}{23}(4\times 1 + 6 \times 2 + 6 \times 3 + 5 \times 4 + 2 \times 5) \approx 2.78$

「形」について

私たちが見つけた頂点の数はほぼ同じです $D = 4$ と平均距離 $L =\frac{1}{24}(4\times 1 + 8 \times 2 + 8 \times 3 + 4 \times 4 ) \approx 2.5$。

クラスター係数が必要な場合 $\bar{C} = 1/2$ 頂点構成から始めることができます $(3.n)^m$、例えば $(3.4)^2$：

残念ながら、この構成は、平面ではなく球を並べて表示するため、適格ではありません（立方八面体が発生します）。だからあなたは選択する必要があります$(3.4)^3$少なくとも。頂点構成で有限グラフにできるサイズの素敵な「形状」を描くため$(3.4)^m$、 $m > 2$、双曲幾何学が必要です。私が推測するように、隣接行列を見つけることはさらに困難です（質問5を参照）。また、直径$D$ と平均距離 $L$ （閉じた式として）。

または、半分にエッジを追加することもできます $n\cdot m$ $4$-のサイクル（ランダムに選択） $(4)^4$ グラフ-したがって、直径が減少します $D$ と平均距離 $L$。

回答

3 M.Winter Aug 18 2020 at 20:12

次の頂点構成には表記があります $(3.4.4.4)^1$ 質問1（任意のサイズのグラフの存在）と質問3（頂点推移性）の反例を提供する必要があります。

この構成を実現するグラフは有限であり、それらはすべて最大24個の頂点で有限です。それらのうちの正確に2つは平面であり、斜方立方八面体のエッジグラフ（左）と密接に関連する疑似斜方立方八面体のエッジグラフ（右）です。最初のものだけが頂点推移的です。

他のすべてのグラフは、頂点を識別することによってこれらから取得できます。たとえば、左のグラフで対蹠頂点を特定すると、「射影多面体」が得られます。

この図では明確ではないため、右の画像で頂点構成を強調表示しました。

これらはすべてこの構成のグラフだと思います。私は間違っているかもしれませんが、24を超える頂点を持つそのようなグラフは確かにありません。

より一般的には、からのローカル定理に興味があるかもしれません

ドルビリンとシュルテによる「単型タイリングの局所定理」

これは、特定のローカル制限がグローバル対称性を意味する場合の問題に関係しています。通常、これは一意性と頂点推移性を提供しますが、トポロジが「単連結」である場合にのみ適用されます（つまり、球のタイリング、ユークリッド/双曲平面には適用されますが、トーラスには適用されません。グラフは一意ではありません$(4)^4$）。

セクション3（定理3.1の下）の冒頭で、彼らは構成が $(3.5.5.5)^1$無限グラフとして実現できますが、頂点推移グラフとしては実現できません。私はこの主張を突き止めようとしましたが、文字通り何千ものタイルが含まれている本「タイルとパターン」のみを参照しており、目的のタイルを見つけることができませんでした。

最後に、次の構成 $(3.4.5)^1$ まったく実現可能であってはなりません：

これを確認するには、グラフに「三角形の面」が含まれている必要があることに注意してください（構成に含まれているため）。その三角形の3つのエッジのそれぞれは、四角形または五角形のいずれかで共有されます。Wlogは、2つのエッジがクワッドレンジで共有されていることを前提としています。ただし、これら2つのエッジは頂点を共有しているため、この頂点をタイプにすることはできません。$(3.4.5)^1$。

一般に、実現可能な構成と実現不可能な構成を区別するのは非常に難しいようです。経験則として、前の例と同様に、変な顔が問題を引き起こすようです。したがって、たとえば構成$(\mathbf 5.8.10)^1$ 2つの異なる種類の面を囲む五角形の面があり、頂点で繰り返される面タイプがないため、同じ理由で存在することもできません。

あなたが（コメントで）あなたが主に興味を持っていると述べているので $(3.n)^m$ （仮定 $n\ge 3$、 $m\ge 2$）：

この構成は常に存在し、一意で頂点推移的です（「グラフが平面である」と解釈できる「単連結トポロジー」を想定）。

それは唯一の有限です $(3.3)^2$（八面体）、$(3.4)^2$（立方八面体）と$(3.5)^2$（二十十二面体）。あなたはそれを「平面」と見なすことができます$\smash{(3.3)^3}$（三角タイリング）と$\smash{(3.6)^2}$（三六角目）、および他のすべての場合は双曲線。

一意性と対称性は、基本的に、前述のローカル定理（および関連する拡張定理）の結果です。しかし、簡単に言えば、そのような頂点構成でグラフを作成しようとし、任意の頂点から開始してから、他の頂点の周囲の頂点構成を完了しようとすると、これは独自の方法でのみ実行できます。（実際には、紙で試してみてください）。（おそらく無限に多くの）ステップのいずれかを選択しないため、結果は一意になります。