Expander

Expander とは, 何のことを指すのかよく分からない。 グラフのある頂点の集合とその補集合が, 何本の辺で結ばれているかを測る量を指すこともあるようだし, ある条件をみたす有限グラフの列を family of expanders ということもあるようである。正確には \(\beta >0\) を定めて \(\beta \)-expander graph というべきなのだろうか。

Survey として, Hoory と Linial と Wigderson の [HLW06] があるが, 123ページもあることから分かるように, 様々な分野と関係あるようである。トポロジー関係では, この survey での §11 と §13, つまり Cayley graph と距離空間の Hilbert space への埋め込みだろうか。

Tao の ここから download できる講義録は Lie 型の有限群の Cayley graph としてできる expander についてまとめたものである。

Dotterrer と Kahle [DK] によると, 最初のまともな expander の例は, Margulis の [Mar88] や Lubotzky と Phillips と Sarnak の [LPS88] で構成されたもののようである。

Tessera の [Tes] によると, 距離空間の Hilbert space への coarse embedding への obstruction が expander であることを指摘したのは, Gromov [Gro03] らしい。Baum-Connes conjecture との関係については, Hoory と Linial の survey では最後に簡単に触れられていて, Valette の [Val03] が参照されている。

Willett と Yu [WY12a; WY12b] によると, Gromov が存在を示した群は, Gromov monster group と呼ばれているようである。 その解説として, Arzhantseva と Delzant の “Examples of random groups” という論文がある。 Arzhantseva の website から download できる。

• Gromov monster group

Blok らの [BHV12] によると, 群論での重要な結果としては, 有限単純群の生成元を適当に取るとその Cayley graph が expander になるというもの [KLN06; BGT11] がある。

Gromov と Guth [GG] によると, random graph は本質的には expander であることに気がついたのは, Kolmogorov と Barzdin [Kol93] らしい。

Dotterrer と Kahle [DK] によると, expander の高次元版, つまり hypergraph への拡張も考えられているようである。 Kahle らのもの前には, Lubotzky, Samuels, Vishne の Ramanujan complex [LSV05b; LSV05a] や Fox, Gromov, Lafforgue, Naor, Pach の [Fox+] の Euclid空間に埋め込んだときの “overlap property” を用いたものがある。 Kalai の blog によると, random complex の homology に関係した定義もあるらしい。このページに最新の情報が載りそうである。

References

[BGT11]

Emmanuel Breuillard, Ben Green, and Terence Tao. “Suzuki groups as expanders”. In: Groups Geom. Dyn. 5.2 (2011), pp. 281–299. arXiv: 1005.0782. url: http://dx.doi.org/10.4171/GGD/128.

[BHV12]

Rieuwert J. Blok, Corneliu G. Hoffman, and Alina Vdovina. “Expander graphs from Curtis-Tits groups”. In: J. Combin. Theory Ser. A 119.3 (2012), pp. 521–525. arXiv: 1009.0667. url: http://dx.doi.org/10.1016/j.jcta.2011.10.007.

[DK]

Dominic Dotterrer and Matthew Kahle. Coboundary expanders. arXiv: 1012.5316.

[Fox+]

Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and Janos Pach. Overlap properties of geometric expanders. arXiv: 1005.1392.

[GG]

Misha Gromov and Larry Guth. Generalizations of the Kolmogorov-Barzdin embedding estimates. arXiv: 1103.3423.

[Gro03]

M. Gromov. “Random walk in random groups”. In: Geom. Funct. Anal. 13.1 (2003), pp. 73–146. url: http://dx.doi.org/10.1007/s000390300002.

[HLW06]

Shlomo Hoory, Nathan Linial, and Avi Wigderson. “Expander graphs and their applications”. In: Bull. Amer. Math. Soc. (N.S.) 43.4 (2006), 439–561 (electronic). url: http://dx.doi.org/10.1090/S0273-0979-06-01126-8.

[KLN06]

Martin Kassabov, Alexander Lubotzky, and Nikolay Nikolov. “Finite simple groups as expanders”. In: Proc. Natl. Acad. Sci. USA 103.16 (2006), pp. 6116–6119. arXiv: math/0510562. url: http://dx.doi.org/10.1073/pnas.0510337103.

[Kol93]

A. N. Kolmogorov. Selected works of A. N. Kolmogorov. Vol. III. Vol. 27. Mathematics and its Applications (Soviet Series). Information theory and the theory of algorithms, With a biography of Kolmogorov by N. N. Bogolyubov, B. V. Gnedenko and S. L. Sobolev, With commentaries by R. L. Dobrushin, A. Kh. Shen\('\), V. M. Tikhomirov, Ya. M. Barzdin, Ya. G. Sinaı̆, V. A. Uspenski [V. A. Uspenskiı̆] and A. L. Semyonov, Edited by A. N. Shiryayev [A. N. Shiryaev], Translated from the 1987 Russian original by A. B. Sossinsky [A. B. Sosinskiı̆]. Dordrecht: Kluwer Academic Publishers Group, 1993, pp. xxvi+275. isbn: 90-277-2798-8.

[LPS88]

A. Lubotzky, R. Phillips, and P. Sarnak. “Ramanujan graphs”. In: Combinatorica 8.3 (1988), pp. 261–277. url: http://dx.doi.org/10.1007/BF02126799.

[LSV05a]

Alexander Lubotzky, Beth Samuels, and Uzi Vishne. “Explicit constructions of Ramanujan complexes of type \(Ã_{d}\)”. In: European J. Combin. 26.6 (2005), pp. 965–993. arXiv: math/0406217. url: http://dx.doi.org/10.1016/j.ejc.2004.06.007.

[LSV05b]

Alexander Lubotzky, Beth Samuels, and Uzi Vishne. “Ramanujan complexes of type \(Ã_{d}\)”. In: Israel J. Math. 149 (2005). Probability in mathematics, pp. 267–299. arXiv: math/0406208. url: http://dx.doi.org/10.1007/BF02772543.

[Mar88]

G. A. Margulis. “Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators”. In: Problemy Peredachi Informatsii 24.1 (1988), pp. 51–60.

[Tes]

Romain Tessera. Coarse embeddings into a Hilbert space, Haagerup Property and Poincare inequalities. arXiv: 0802.2541.

[Val03]

Alain Valette. “On the Baum-Connes assembly map for discrete groups”. In: Proper group actions and the Baum-Connes conjecture. Adv. Courses Math. CRM Barcelona. With an appendix by Dan Kucerovsky. Birkhäuser, Basel, 2003, pp. 79–124.

[WY12a]

Rufus Willett and Guoliang Yu. “Higher index theory for certain expanders and Gromov monster groups, I”. In: Adv. Math. 229.3 (2012), pp. 1380–1416. arXiv: 1012.4150. url: http://dx.doi.org/10.1016/j.aim.2011.10.024.

[WY12b]

Rufus Willett and Guoliang Yu. “Higher index theory for certain expanders and Gromov monster groups, II”. In: Adv. Math. 229.3 (2012), pp. 1762–1803. arXiv: 1012.4151. url: http://dx.doi.org/10.1016/j.aim.2011.12.016.