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>