The University of Michigan Combinatorics Seminar


Abstract 

I am going to describe a general approach to obtain fast and crude
bounds on the cardinality of combinatorially defined sets, such as
perfect matchings in a given graph, trees and forests with special
properties, nondegenerate submatrices of a given matrix, etc.
The idea of the approach is to identify the set of interest with
a subset of a certain metric probability space
(most often, the Boolean cube) and measure the distance from a random
point in the space to the set, hoping that the distance will be
small if and only if the set is large. In many interesting cases the
distance can be computed quite easily by known combinatorial
optimization algorithms. The talk is based on a paper joint with
A. Samorodnitsky.
