Computer Science/Discrete Mathematics Seminar II | |

Topic: | Rigidity of 3-Colorings of the d-Dimensional Discrete Torus |

Speaker: | Ohad Feldheim |

Affiliation: | Tel Aviv University |

Date: | Tuesday, October 18 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/d-dimen |

We prove that a uniformly chosen proper coloring of Z_{2n}^d with 3 colors has a very rigid structure when the dimension d is sufficiently high. The coloring takes one color on almost all of either the even or the odd sub-lattice. In particular, one color appears on nearly half of the lattice sites. This model is the zero temperature case of the 3-states anti-ferromagnetic Potts model, which has been studied extensively in statistical mechanics. The proof involves results about graph homomorphisms and various combinatorial methods, and follows a topological intuition. (Joint work with Ron Peled.)