# Combinatorics Seminar

When: Sunday, May 12, 10am

Where: Schreiber 309

Speaker: Wojciech Samotij, Cambridge and Tel Aviv U.

Title: Typical structure of graph homomorphisms

## Abstract:

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.

redesigned by barak soreq