The Helly number of Hamming balls and related problems
The Helly number of Hamming balls and related problems
-
Zhihan Jin, ETH Zurich
Fine Hall 224
We prove the following variant of Helly's classical theorem for Hamming balls with a bounded radius. For n>t and any (finite or infinite) set X, if in a family of Hamming balls of radius t in X^n, every subfamily of at most 2^{t+1} balls has a common point, so do all members of the family. This is tight for all |X|>1 and all n>t. The proof of the main result is based on a novel variant of the so-called dimension argument, which allows one to prove upper-bounds that do not depend on the dimension of the ambient space.This is joint work with Noga Alon and Benny Sudakov.