TAILIEUCHUNG - Đề tài " Uniform expansion bounds for Cayley graphs of SL2(Fp) "

We prove that Cayley graphs of SL2 (Fp ) are expanders with respect to the projection of any fixed elements in SL(2, Z) generating a non-elementary subgroup, and with respect to generators chosen at random in SL2 (Fp ). 1. Introduction Expanders are highly-connected sparse graphs widely used in computer science, in areas ranging from parallel computation to complexity theory and cryptography; recently they also have found some remarkable applications in pure mathematics; see [5],[10], [15], [20], [21] and references therein. . | Annals of Mathematics Uniform expansion bounds for Cayley graphs of SL2 Fp By Jean Bourgain and Alex Gamburd Annals of Mathematics 167 2008 625 642 Uniform expansion bounds for Cayley graphs of SL2 Fp By Jean Bourgain and Alex Gamburd Abstract We prove that Cayley graphs of SL2 Fp are expanders with respect to the projection of any fixed elements in SL 2 Z generating a non-elementary subgroup and with respect to generators chosen at random in SL2 Fp . 1. Introduction Expanders are highly-connected sparse graphs widely used in computer science in areas ranging from parallel computation to complexity theory and cryptography recently they also have found some remarkable applications in pure mathematics see 5 10 15 20 21 and references therein. Given an undirected d-regular graph G and a subset X of V the expansion of X c X is defined to be the ratio Ỡ X XI where d X fy eỹ distance y X 1g. The expansion coefficient of a graph G is defined as follows c G fc X I XI 110 . A family of d-regular graphs Gn d forms a family of C-expanders if there is a fixed positive constant C such that 1 liminf c Gn d C. nn The adjacency matrix of G A G is the G by G matrix with rows and columns indexed by vertices of G such that the x y entry is 1 if and only if x and y are adjacent and 0 otherwise. By the discrete analogue of Cheeger-Buser inequality proved by Alon and Milman the condition 1 can be rewritten in terms of the second largest eigenvalue of the adjacency matrix A G as follows 2 limsup Ai An d d. The first author was supported in part by NSF Grant DMS-0627882. The second author was supported in part by NSF Grants DMS-0111298 and DMS-0501245. 626 JEAN BOURGAIN AND ALEX GAMBURD Given a finite group G with a symmetric set of generators S the Cayley graph G G S is a graph which has elements of G as vertices and which has an edge from x to y if and only if x ơy for some Ơ 2 S. Let S be a set of elements in SL2 Z . If S the group generated by S is a finite index subgroup of SL2 Z .

• Thạc sĩ - Tiến sĩ - Cao học
• Uniform expansion
• subjects of mathematics
• science reports
• studied mathematics
• natural sciences
• scientific research
• Uniform temperature
• Design of long reinforced concrete structures without expansion joints
• Long reinforced concrete structures
• Expansion joints
• Long RC structures
• Research methods
• Data collection methods
• Understanding scientific research
• Ensuring research validity
• Measurement techniques
• Sampling methods
• Scientific research capacity
• Educational institutions
• Policy and management studies
• Vietnam Academy for Ethnic minorities
• Scientific bases
• earth sciences
• Research
• VNU Journal of Science
• scientific reports
• Action research
• linguistics
• research projects
• Foreign Languages
• cooperative research
• Renewable energy
• Introduction to research
• Scientific investigation
• Scientific investigation research
• Experimental designs
• Measurement of variables
• Reading research
• Conducting and reading research
• Research process
• Research report
• Purpose of research
• Scientific method
• Conducting research
• The effect of university autonomy on training and scientific research
• Vietnam national university of agriculture
• Training and scientific research
• Vascular plant
• Flora
• Yen Tu
• Quang Ninh Research Forest
• statements and documents scientific reports
• medical reports
• medical knowledge
• medical research
• clinical trials
• medical management
• health care
• Methods in behavioral research
• Behavioral research
• Scientific understanding
• Fundamental research issues
• Measurement concepts
• Observational methods
• reading comprehension
• education
• optimal picket
• model creation
• urban expansion
• organizing spatial
• Journal of Science
• Journal of Technology
• Technology Management
• Research quality
• Strategy and policy
• Summary of Doctoral thesis
• Summary of Doctoral thesis in public Management
• State management
• Female scientific research human
• Research human resource development
• Scientific research and teaching
• Defense and security education
• Current situation and solutions
• Security education
• Structural biochemistry
• epigenetics
• MicroRNAs
• Tạp chí khoa học
• Tạp chí Công nghệ
• Quản lý công nghệ
• Human resources
• Science management
• Poliomyelitis vaccine Research
• Non Ri Maprec
• Production center