When: Sunday, March 30, 10am

Where: Schreiber 309

Speaker: Oren Becker, Hebrew University

Title: Families of Cayley graphs which are unique-neighbor expanders

For a graph G=(V,E) and a subset X of its vertices, a unique neighbor of X is a vertex of V\X adjacent to exactly one vertex in X. A family of graphs is a family of unique-neighbor expanders if there are positive constants t and s, such that for each graph G=(V,E) in the family, every subset X of at most t|V| vertices has at least s|X| unique neighbors. We show that such families arise as Cayley graphs of semidirect products of PSL(2,F_{q^n}) with the cyclic group of order 8.

redesigned by barak soreq