Typical graph homomorphisms on bipartite 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. Specifically, in typical realizations, a maximal bipartite subgraph of H is chosen and the homomorphism sends almost all vertices of G into this subgraph. 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).
No prior knowledge of graph homomorphisms or expander graphs will be assumed. Joint work with Wojciech Samotij and Amir Yehudayoff.