n個の頂点のいくつかの小さな固定d（3や4など）のd-regularエキスパンダーグラフを作成する必要があります。
内容これを実際に行う最も簡単な方法は何ですか？ a.a.sであることが証明されているランダムなd-正則グラフを作成します。エキスパンダー？
また、エキスパンダーであるマーギュリス構造とラマヌジャングラフ、およびジグザグ積を使用した構造についても読みました。ウィキペディアには、すばらしいが非常に短い概要が記載されています。 http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 しかし、実際にはどの方法を選択しますか？
私にとって、これらのメソッドはすべて実装が非常に複雑で、特に理解するのが非常に複雑で、おそらく非常に具体的であるように思われます。 「おそらく順列などに基づいて、d-regularエキスパンダーグラフのシーケンスを実際に生成するためのより簡単な方法はありませんか？
d-regular 2部エキスパンダーグラフを作成する方が簡単かもしれませんか？
別の質問もあります：悪いd-regularエキスパンダーのファミリーはどうですか？そのような概念は意味がありますか？可能な限り悪いd-regularグラフ（もちろん接続されている）のファミリーを構築できますか？エキスパンダーの意味は？
よろしくお願いします。
コメント
- リストしたものよりも簡単な明示的な構造があります、しかし、ランダムグラフはトリックを実行し、より良いパラメータを持つ必要があります。
- 構造の名前や参照を与えることができますか？より良いパラメータとは、より良い（エッジ）拡張を意味すると思いますか？
- Andr áは私が考えていた例を示しましたが、一般に、ランダムグラフは（ほとんどの場合）明示的な構成よりも優れています。エッジ拡張が大きいだけでなく、とyアルゴリズムに役立つ他の同様のプロパティは、おそらくランダムグラフによって自動的に満たされます。
- わかりました。次数3の場合、Andr áの例またはランダムグラフ私のアプリケーションには十分なようです。特にランダムグラフに関しては、エキスパンダーではない3-regグラフファミリーを構築することは興味深いでしょう。しかし、これはおそらく非常に難しいか、不可能ですか？
- $ K_4 $ sの和集合を取ります。接続されたグラフが必要な場合は、各$ K_4 $から1つのエッジを削除し（ダイアモンドグラフと呼ばれるグラフを形成）、それらを1サイクルで接続します。
回答
自己ループのあるグラフを気にしないのであれば、「最も簡単な」エクスパンダーファミリーはおそらくこれであり、3レギュラーのエクスパンダーを提供します。
いくつかの素数$ p $から始めて、$ 0 $から$ p-1 $までの番号が付けられた頂点を作成します。すべての頂点$ u \ ne 0 $について、$ u $を$ u-1 $と$ u + 1 $に接続します。 、modulo $ p $。また、$ u $を一意の頂点$ v $に接続して、$ uv \ equiv 1 \ mod p $となるようにします。
例として、ファミリの7頂点グラフは次のようになります。頂点がサイクルの周りに順番に番号付けされた7サイクル、$ 6 $、$ 0 $、および$ 1 $に自己ループがあり、最後に$ 3 $と$ 5 $、および$ 2 $と$ 4 $を結合するコードがあります。
詳細な説明と参照については、 https://mathoverflow.net/questions/124708/an-expander-graph を参照してください。 “で検索すると、より詳細なポインタがたくさんあります。 CSThのエキスパンダー」 eory 、 Math.SE 、および MO 。
Yuval Filmusが指摘しているように、ランダムな構成は一般により良い結果をもたらす可能性がありますが、もちろんエキスパンダーを生成しない場合があります（特に小さなグラフの場合）。
コメント
- コメントありがとうございます。以前に他のサイトでエキスパンダーを検索しましたが、MOでは検索していませんでしたが、実際にはもっと多くの結果があるようです。
回答
ランダムな正則グラフが与えられると、エキスパンダーwhpです（以下にリンクされているMATLABコードのドキュメントに記載されているリファレンスに従ってください）、私はかつて次のものを使用しました：