When: Sunday, May 12, 10am
Where: Schreiber 309
Speaker: Wojciech Samotij, Cambridge and Tel Aviv U.
Title: Typical structure of graph homomorphisms
A graph homomorphism from a graph G to a graph H is a mapping of V(G) to V(H) that maps edges of G to edges of H. Counting and describing the typical structure of homomorphisms between graphs have many interesting aspects and a surprising number of applications. Numerous models in statistical mechanics and questions in extremal graph theory can be phrased in these terms.
In this talk, we will focus our attention on the case when H is some (small) fixed graph, which can be thought of as a generalization of graph coloring. For many natural classes of graphs, one observes the following phenomenon: A typical homomorphism from every G in the class to H is very rigid, exhibiting strong spatial correlations. We will discuss some examples of this phenomenon that occur in the case when G is a regular graph with strong expansion properties.
No prior knowledge of graph homomorphisms or expander graphs will be assumed. Joint work with Ron Peled and Amir Yehudayoff.
