***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Ruben Ascoli (Georgia Tech)

Thursday 8th October, 3:00 in Fine Hall 224.

Title: A reformulation of the discrete convexity conjecture via k-thresholds

In this talk, I will introduce the new notion of the k-threshold of an
increasing family, which generalizes the well-studied threshold function. I will
show that Talagrand's discrete convexity conjecture is equivalent to the
assertion that for some universal integer k, the k-threshold of every increasing
family is at most a universal constant times its expectation threshold.

This talk will focus on graph properties: we can bound the k-threshold of any
increasing graph family in terms of ordinary thresholds of graphs obtained by
decomposing members of the family. We use this to show that the reformulated
conjecture holds for several classical spanning graph containment properties,
such as containment of perfect matchings and Hamiltonian cycles, and more
generally for all graph containment properties whose target graphs have
sufficiently small degeneracy. I'll end the talk with some tantalizing open
problems.

Joint work with Xiaoyu He, Jinyoung Park, and Michel Talagrand.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)