What is the minimum cardinality for a set intersecting each member of a configurations of pairwise intersecting disks of the same radius?

569 Views Asked by At

Consider, in the euclidean plane, some configuration of (closed) disks of the same radius such that each pair of disks has a non-empty intersection.

What is the minimum of the cardinalities of subsets (of points) of the plane that intersect every disk (for a generic configuration of the above form)?

Of course for some specific configuration it could be $1$, or if each $3$ out of $4$ intersect, I believe the answer is $13$, but I need an answer for such a configuration in general.

2

There are 2 best solutions below

6
On BEST ANSWER

The answer is 3. It's proved on page 144 of Danzer, Grunbaum, and Klee, Helly's Theorem and its relatives, Proc. Sympos. Pure Math. 7 (1963) 101-180, and cited in Chakerian and Stein, Some intersection properties of convex bodies, Proc. Amer. Math. Soc. 18 (1967) 109-112.

Here's how it's stated in Chakerian and Stein: let $h(K)$ be the least cardinal $r$ such that whenever $F$ is any family of pairwise intersecting translates of $K$, there exist $r$ points such that each member of $F$ contains at least one of them. ...if $C$ is a circular disk, then $h(C)=3$.

I think both papers are freely available on the web.

1
On

I get the following series:

$$1, \ \ \ n=1 \\ 3, \ \ \ n=2 \\ 7, \ \ \ n=3 \\ 13, \ \ \ n=4 \\ 21, \ \ \ n=5 \\ 31, \ \ \ n=6 \\ $$

On examining, the generating function is $\boxed {n^2 -n+1}$


For showing this, you'll need principle of inclusion-exclusion.