東北大学 大学院情報科学研究科
純粋・応用数学研究センター

組合せ論セミナー

第60回 2014年12月5日 14:00〜15:30

見村 万佐人(東北大学)「Verifiable expanders and metric Kazhdan constants」

For epsilon>0, we say a connected graph Gamma is an epsilon-verifiable expander if there exsits an R such that any (finite) connected graph Lambda which has the same ball of radius R satisfies that lambda_1(Lambda) is at least epsilon. Here lambda_1 is the first positive Laplace eigenvalue of the grpah. Also, "having the same R-ball" means that for any vertex y in Lambda, there exists a vertex x in Gamma such that R-ball centered at y (in Lambda) is isomorphic to that at x (in Gamma) as rooted graphs.

We show that any Cayley graph of a group with "Kazhdan's property (T)", for instance SL(n,Z) for n>2, is an epsilon-verifiable expander for certain, mathematically decsribed in terms of the group system, epsilon. To show this, we introduce a notion of "metric Kazhdan constant" for a pair of a finitely generated group and its finite generateing set.