Expansion Of Product Replacement Graphs

Alexander Gamburd and Igor Pak
Combinatorica
Issue Volume 26, Number 4 / August, 2006
Pages 411-429
http://dx.doi.org/10.1007/s00493-006-0023-0

エクスパンダに関する論文．
エクスパンダに関する日本語の解説は『数理科学』2006年9月号の垂井さんの記事を参照．
エクスパンダの構成法はいろいろ知られているが群のCayleyグラフを用いる方法がある．
Cayleyグラフは群とその生成系をもとにして作られるが，Cayleyグラフがエクスパンダであるという性質が生成系の選択に依存しない群そのものの性質なのかどうか明らかではない．
この論文ではエクスパンダの辺伸張 (辺拡大，edge expansion) とproduct replacement graphと呼ばれるものの辺伸張の関係を調べている．
この論文の定理の帰結の1つとして，例えば，射影特殊線型群PSL(2,p) (pは素数) を考えたとき，
PSL(2,p)の要素数4の任意の生成系を考えたときのCayleyグラフがエクスパンダであるならば，PSL(2,p)のproduct replacement graphもエクスパンダであることを示している．