BGU SEMINAR IN ERGODIC THEORY AND PROBABILITY
 
SPEAKER:
Ron Peled, Tel Aviv University
 
DATE AND TIME:
May 22, 2012, 10:40
 
PLACE:
Alon building (building 37), room 201, BGU campus.
PLEASE NOTE CHANGE OF LOCATION!!!
 
TITLE:
Graph homomorphisms on expander graphs
 
ABSTRACT:
A graph homomorphism from a graph G to a graph H is a mapping which
preserves edges. By choosing various H, this class includes many
well-studied models such as proper colorings, independent sets and
Lipschitz functions on G. We show that if G is a regular bipartite
expander graph with good expansion, then typical graph homomorphisms on G
are very rigid, exhibiting strong spatial correlations. For example, in a
typical proper coloring of G each of the partite classes will be colored
with only half of the colors, with few exceptions (fewer than would occur
deterministically).
I will also discuss a related conjecture about graph homomorphisms on Z^d.
 
No prior knowledge of graph homomorphisms or expander graphs will be
assumed. Joint work with Wojciech Samotij and Amir Yehudayoff.
 
---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Barak Weiss   <barakw@cs.bgu.ac.il>