Title: Entrophy and Extremal Set Theory
Speaker: Bill Cuckler, Rutgers University
Date: Monday, September 29, 2003, 1:10 pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Call a family of graphs all having the same vertex set triangle intersecting if the intersection of the edge set of any two contains a triangle. An example of a triangle intersecting family on n vertices is all graphs that contain a fixed triangle, and 1/8 of the total graphs are in this family. It has been conjectured that this is the largest triangle intersecting family possible on n vertices. The best known upper bound (1/4) on the size of an intersecting family was proved by Chung, Frankl, Graham and Shearer using entropy. Intuitively, the binary entropy measures the average surprise or how much information a random variable encodes. In this talk, I will give some basic facts of entropy and give the proof of this lower bound.