Date:

Mon, 08/04/201911:00-13:00

Location:

CS B-500, Safra campus

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.

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.