A family of sets (subsets of of size ) is intersecting if every pair of sets in have a common element. If then every pair of sets intersect, so can be as large as . If then the Erdős–Ko–Rado theorem states that , which (up to relabelling of the ground set) is attained only by the …
Tag: sets
Random Structures and Algorithms 2017
A partial, chronologically ordered, list of talks I attended at RSA in Gniezno, Poland. Under construction until the set of things I can remember equals the set of things I’ve written about. Shagnik Das A family of subsets of that shatters a -set has at least elements. How many -sets can we shatter with a …
Partition regularity and other combinatorial problems
This is the imaginative title of my PhD thesis. It contains four unrelated pieces of work. (I was warned off using this phrasing in the thesis itself, where the chapters are instead described as “self-contained”.) The first and most substantial concerns partition regularity. It is a coherent presentation of all of the material from Partition …