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: Thursday, May 19, 2016, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Asaf Ferber (Yale University)

Iterated Log Law for various graph parameters

We show that a version of the classical Iterated Log Law of Khinchin, and independently of Kolmogorov from the 1920's, holds for various parameters in the binomial random graph model G(n,p) and in a random 0/1 Bernoulli matrices. In particular, for a constant p, we show that such a law holds for the number of copies of a fixed graph H in G(n,p), we show a similar statement for the number of Hamilton cycles in a random k-uniform hypergraph, provided that k\geq 4. In the graph case (that is, k=2), since the number of Hamilton cycles in G(n,p), denoted by X_n, does not converge to a normal distribution but rather tends to a log-normal distribution (as has been first proved by Janson), we show that a version of the Iterated Log Law holds for \log X_n. Similarly, we show that an Iterated Log Law holds for log of the permanent of a Bernoulli 0/1 matrix. No prior knowledge is required. Joint with Daniel Motealegre and Van Vu.

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