From: Paul Beame (beame@cs.washington.edu)
Date: Mon Feb 23 2004 - 17:42:26 PST
After Irit Dinur's talk at 2:30 on Wednesday in CSE 203,
Ehud Friedgut will talk at 4:00 in Padelford C-401 in the Combinatorics
Seminar.
Ehud Friedgut of Hebrew University of Jerusalem.
His title is:
Using entropy to estimate the number of
Hamiltonian cycles in a tournament.
Abstract:
Szele, in 1943, in what is often considered the first application of the
probabilistic method proved that there exist tournaments on n vertices
that have at least (n-1)!2^{-n} Hamiltonian paths. (Modern statement of
his proof: take a random tournament.) Noga Alon, some 50 years
later matched this by an upper bound that differs by a multiplicative
constant of n^{3/2} (short description of his proof: use Bregman's
bound on permanents of 0-1 matrices.)
In this talk we'll show how to improve this to n^{1.22....}.
Though the result itself seems slightly dull, the methods involved are
(hopefully) of interest - using information theoretic arguments
to bound the size of a family of combinatorial objects.
Joint work with Jeff kahn.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Mon Feb 23 2004 - 17:42:39 PST