Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Mittagsseminar Talk Information

Date and Time: Tuesday, May 28, 2019, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Vincent Tassion

Sharpness of the phase transition via randomized algorithms

We consider Bernoulli percolation on the hypercubic lattice Zd in dimension d at least two. Independently of the other edges, each edge is declared to be open with probability p and closed with probability 1-p. This models undergoes a phase transition at a critical parameter pc above which an infinite open connected component appears. A fundamental theorem (Menshikov 1987, Aizenman-Barsky 1987) states that the connection probabilities decays exponentially fast in the subcritical regime p < pc (this implies in particular that the biggest open connected component in the box of size n has typical size of order log n). In this talk, we provide a new proof of exponential decay for the connection probabilities of subcritical Bernoulli percolation, based on randomized algorithms and the OSSS inequality (a tool from theoritical computer science). This proof does not rely on the domain Markov property or the BK inequality. In particular, it extends to FK percolation and continuum percolation models such as Boolean and Voronoi percolation in arbitrary dimension. This provides the first proof of sharpness of the phase transition for these models. This talk is based on a joint work with Hugo Duminil-Copin and Aran Raoufi.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login