News on Fractional Helly, Colorful Helly, and Radon

My 1983 Ph D thesis was on Helly-type theorems which is an exciting part of discrete geometry and, in the last two decades, I have had an ongoing research project with Roy Meshulam on topological Helly-type theorems. The subject found new connections with structural graph theory and Gyárfás-type problems, and also with high-dimensional expanders.  We already devoted quite a few posts directly and indirectly to Helly-type theorems.

In this post I would like to report on two recent related breakthroughs, one by Andreas Holmsen and Dong-Gyu Lee, and the other by Andreas Holmsen. These developments are related to problems that are described in Problems for Imre Bárány’s birthday, and to my earlier 2004 Oberwolfach report “Expectations from commutative algebra“. While at it I will mention some earlier important papers by Pauline Sarrabezolles, by Shay Moran and Amir Yehudayoff, and by Boris Bukh.

Helly theorem, colorful Helly, and the Fractional Helly Theorem.

You can find the statements of Helly theorem, Radon theorem, and the colorful Caratheodory theorem in this post.  The colorful Helly theorem was first observed by Lovasz. The fractional Helly theorem was first proved by Katchalski and Liu.

The colorful Helly theorem: Let {\cal K}_1, {\cal K}_2, \dots, {\cal K}_{d+1} be d+1 nonempty families of convex sets in \mathbb R^d. If for every choice of a transversal – one set from every family – there is a point in common to all the chosen sets then for one of the families, there is a point in common to all sets in the family.

[Sorry, I got it wrong first, thanks to Shakhar Smorodinsky for alerting me.]

The fractional Helly theorem: For every \alpha >0 there is \beta >0 such that if K_1,K_2,\dots, K_n are n convex sets in \mathbb R^d and at least \alpha fraction of (d+1)-tuples of the sets have a point in common then a fraction of at least \beta of the sets have a point in common.

I should mention that these theorems do not follow combinatorially from Helly’s theorem itself. They manifest deep properties of hypergraphs coming from geometry, and it is an important question to give general abstract properties, combinatorial or topological leading to such properties.

The result of Holmsen and Lee asserts roughly that the fractional Helly property follows combinatorially from Radon’s theorem! Holmsen’s result asserts that  the fractional Helly property follows combinatorially from the colorful Helly theorem!

Andreas Holmsen Dong-Gyu Lee: Fractional Helly from Radon

Radon numbers and the fractional Helly theorem

Authors: Andreas Holmsen Dong-Gyu Lee

Abstract: A basic measure of the combinatorial complexity of a convexity space is its Radon number. In this paper we show a fractional Helly theorem for convexity spaces with a bounded Radon number, answering a question of Kalai. As a consequence we also get a weak epsilon-net theorem for convexity spaces with a bounded Radon number. This answers a question of Bukh and extends a recent result of Moran and Yehudayoff.

Andreas Holmsen: Fractional Helly follows from colorful Helly

Large cliques in hypergraphs with forbidden substructures

Author: Andreas F. Holmsen

Abstract: A result due to Gyárfás, Hubenko, and Solymosi (answering a question of Erdös) states that if a graph G on n vertices does not contain K_{2,2} as an induced subgraph yet has at least c{{n} \choose {2}} edges, then G has a complete subgraph on at least c^2/10n vertices. In this paper we suggest a “higher-dimensional” analogue of the notion of an induced K_{2,2} which allows us to generalize their result to k-uniform hypergraphs. Our result also has an interesting consequence in discrete geometry. In particular, it implies that the fractional Helly theorem can be derived as a purely combinatorial consequence of the colorful Helly theorem.

 

Let me mention that Gyárfás’ type problems in graph theory and a little on the connection with fractional Helly were mentioned in the post When a few colors suffice. On this front major advances has happened in a series of recent papers and I will discuss them at a later post. (But, for now see, Alex Scott and Paul Seymour’s A survey of χ-boundedness, and Proof of the Kalai-Meshulam conjecture by Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl.)

Pauline Sarrabezolles: The number of tranversals in the colorful Helly theorem

How many tranversals can we guarantee in colorful Carathéodory? This is a very interesting problem on its own, and may be also related to Sierksma’s conjecture on the number of Tverberg’s partitions that we mentioned in this recent post (and in this old one).

The colourful simplicial depth conjecture (2014)

Pauline Sarrabezolles

Abstract:
Given d+1 sets of points, or colours, S_1,\dots ,S_{d+1} in \mathbb R ^d, a colourful simplex is a set T\subset \cup _{i=1}^{d+1}S_i such that |T∩Si|≤1, for all i∈{1,…,d+1}. The colourful Carathéodory theorem states that, if 0 is in the convex hull of each S_i, then there exists a colourful simplex T containing 0 in its convex hull. Deza, Huang, Stephen, and Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597–604 (2006)) conjectured that, when |S_i|=d+1 for all i∈{1,…,d+1}, there are always at least d^2+1 colourful simplices containing 0 in their convex hulls. We prove this conjecture via a combinatorial approach.

On weak ε-nets and the Radon number (2017)

Shay Moran, Amir Yehudayoff

Abstract: We show that the Radon number characterizes the existence of weak nets in separable convexity spaces (an abstraction of the euclidean notion of convexity). The construction of weak nets when the Radon number is finite is based on Helly’s property and on metric properties of VC classes. The lower bound on the size of weak nets when the Radon number is large relies on the chromatic number of the Kneser graph. As an application, we prove a boosting-type result for weak ϵ-nets.

Boris Bukh: Beyond nerves, the abstract setting for the disproof of the partition conjecture

We already mentioned Boris Bukh’s beautiful counter example to Eckhoff’s partition conjecture in the 2010 paper Radon partitions in convexity spaces.  Let me mention a general object used by Boris which is of much independent interest.

Let A=\{a_1,a_2,\dots, a_n\} be a set of points in \mathbb R^d. For S \subset [n] let A_S=conv \{a_i: i \in S\}, and let N be the nerve of all the sets A_S: S \subset [n]. N is a simplicial complex whose vertices are indexed by all non empty subsets of [n]. The abstract setting we have here is that of a simplicial complex, whose vertices are indexed by all subsets of [n] and such that a collection of vertices which represent a family of subsets with non empty intersection must be a face of the complex.

Advertisements
This entry was posted in Combinatorics, Convexity and tagged , , , , , , , , , , . Bookmark the permalink.

2 Responses to News on Fractional Helly, Colorful Helly, and Radon

  1. Gil Kalai says:

    This time also, WordPress automatically chose good earlier relevant posts. The post on Colorful Caratheodory Revisited https://gilkalai.wordpress.com/2009/03/15/colorful-caratheodory-revisited/ discuss a strengthening of colorful Caratheodory. Translated to a Helly-type theorem it should say the following:

    Theorem 1(I think): Let {\cal K}_1, {\cal K}_2, \dots, {\cal K}_{d+1} be d+1 nonempty families of convex sets in \mathbb R^d. If for every choice of a transversal – one set from every family – there is a point in common to all the chosen sets, then for some pair of the families, there is a point in common to all sets in these two families.

    Another strengthening of colorful Helly which follows from the original proof by Lovasz, (and requires just d-collapsibility) is

    Theorem 2: Let {\cal K}_1, {\cal K}_2, \dots, {\cal K}_{d+1} be d+1 nonempty families of convex sets in \mathbb R^d. If for every choice of a transversal – one set from every family – there is a point in common to all the chosen sets, then for some such transversal and one family there is a point in common to all sets in either the transversal or the family.

    For both theorems we do not have a proof based on the d-Leray property. Roy Meshulam and me proved the colorful Helly theorem based on the d-Leray property but we did not succeed in extending the proof to apply to the conclusion of the theorem 2. (We referred to it as the L-theorem.)

    • Gil Kalai says:

      One more remark is that one goal Roy and I had was to find a different proof for the fractional Helly property for d-Leray complexes, which, while not giving necessary tight bounds will be easier to extend. The theorem by Holmsen (in addition to the topological colorful Helly of Meshulam and me) gives such a new proof.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s