Ramanujan graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Ramanujan graphs

Authors:	A Lubotzky R Phillips P Sarnak

Institution:	1. Institute of Mathematics and Computer Science, Hebrew University, Jerusalem, Israel 2. Department of Mathematics, Stanford University, 94305, Stanford, California, USA 3. Department of Mathematics, Stanford University, 94305, Stanford, California, USA

Abstract:	A large family of explicitk-regular Cayley graphsX is presented. These graphs satisfy a number of extremal combinatorial properties. For eigenvaluesλ ofX eitherλ=±k or ¦λ¦≦2 √k?1. This property is optimal and leads to the best known explicit expander graphs. The girth ofX is asymptotically ≧4/3 log_k?1 ¦X¦ which gives larger girth than was previously known by explicit or non-explicit constructions.

Keywords:
本文献已被 SpringerLink 等数据库收录！