Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 288 - Probability Seminar

Frank Lin

University of Texas at Austin

Sofic entropy via random hypergraph 2-colorings

Abstract:

In random constraint satisfaction problems, first and second moment methods are used to yield upper and lower bounds for the threshold of edge density for existence of solutions. In random hypergraph 2-coloring, Achlioptas and Moore obtain a lower bound using a standard second moment method based on the Paley-Zygmund inequality. Coja-Oghlan and Zdeborova later use an enhanced second moment method involving the Hamming geometry of the set of colorings to improve the lower bound up to a so-called condensation transition. We adapt their methods and setup to a subshift of finite type over a sofic group and show results analogous to the aforementioned, exploiting the combination of phenomena that occur at densities between the standard and enhanced second moment thresholds to conclude that there exists an interesting example of a topological dynamical system having two different positive sofic entropies relative to two different sofic approximations. This is joint work with Dylan Airey and Lewis Bowen.

Host: Brandon Seward

October 3, 2019

11:00 AM

AP&M 6402

****************************