Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Matthew Russell, Rutgers University, russell2 {at} math [dot] rutgers [dot] edu)
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Counting Disjointly-Occurring Events

Speaker: Jake Baron, Rutgers University

Date: Thursday, October 29, 2015 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


In {0,1}^n, events A and B "occur disjointly" if there are "disjoint certificates" of their respective occurrence. The van den Berg-Kesten inequality (BK) says that if A and B are increasing, then P(they occur disjointly) ≤ P(A)P(B). I will present a new (to my knowledge) generalization of BK to a setting with arbitrarily many events, where the quantity of interest is the maximum number that occur disjointly. Time permitting I'll discuss our motivation for this result (though it is interesting in itself), which was to get an exponential upper-tail bound for a class of random variable that often comes up in combinatorial settings.

Joint with Jeff Kahn.

See: http://www.math.rutgers.edu/~russell2/expmath/