Combinatorics: Kim Minki (Technion) "The fractional Helly properties for families of non-empty sets"

Speaker: Kim Minki, Technion
Title: The fractional Helly properties for families of non-empty sets
Abstract:
Let $F$ be a (possibly infinite) family of non-empty sets.
The Helly number of $F$ is defined as the greatest integer $m = h(F)$ for which there exists a finite subfamily $F'$ of cardinality $m$ such that every proper subfamily of $F'$ is intersecing and $F'$ itself is not intersecting.
For example, Helly's theorem asserts that the family of all convex sets in $d$-dimensional Euclidean space has Helly number $d+1$.
The family $F$ is said to satisfy the fractional Helly property for $k$-tuples if there exists a function $\beta$ such that: for every finite subfamily $F'$ if size at least $k$, if at least $\alpha$ fraction of the $k$-tuples are intersecting then some $F'$ contains an intersecting subfamily of size at least $\beta(\alpha)|F'|$.
For instance, the fractional Helly theorem implies that the family of all convex in $d$-dimensional Euclidean space satisfies the fractional Helly property for $(d+1)$-tuples.
It has been a fundamental question to find sufficient condition on set-systems to guarantee the fractional Helly properties.
In this talk, I will present some results about this question.

Date: 

Mon, 08/04/2019 - 11:00 to 13:00

Location: 

CS B-500, Safra campus