University of Cambridge > > Isaac Newton Institute Seminar Series > Local graph coloring

Local graph coloring

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Random Geometry

Co-authors: Oded Schramm (), David B Wilson ()

How can we color the vertices of a graph by a local rule based on i.i.d. vertex labels? More precisely, suppose that the color of vertex v is determined by examining the labels within a finite (but perhaps random and unbounded) distance R of v, with the same rule applied at each vertex. (The coloring is then said to be a finitary factor of the i.i.d. labels). Focusing on Z^d, we investigate what can be said about the random variable R if the coloring is required to be proper, i.e. if adjacent vertices must have different colors. Depending on the dimension and the number of colors, the optimal tail decay is either a power law, or a tower of exponentials. I will briefly discuss generalizations to shifts of finite type and finitely dependent processes.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity