28 I. Convex Sets at Large
7. The Euler Characteristic
Helly’s Theorem tells us something special about how convex sets may intersect.
Here we introduce another powerful tool to study intersection properties of convex
sets.
(7.1) Definition. Let A
Rd
be a subset. The indicator function [A] of A is the
function [A] :
Rd
−→ R such that
[A](x) =
1 if x A,
0 if x / A.
PROBLEM.
1◦.
Prove that [A] · [B] = [A B].
(7.2) Lemma (Inclusion-Exclusion Formula). Let A1,... , Am Rd be sets.
Then
[A1 . . . Am] = 1 (1 [A1]) · (1 [A2]) · · · (1 [Am])
=
m
k=1
(−1)k−1
1≤i1i2...ik≤m
[Ai1 . . . Aik ].
In particular,
[A1 A2] = [A1] + [A2] [A1 A2].
Proof. Let us choose an x Rd. Then
[A1 . . . Am](x) =
1 if x A1 . . . Am,
0 if x / A1 . . . Am.
On the other hand,
1 [Ai](x) =
1 if x / Ai,
0 if x
Ai.
Therefore,
(
1 [A1](x)
)
· · ·
(
1 [Am](x)
)
=
1 if x / Ai for all i,
0 if x Ai for some i.
Hence [A1 . . . Am] = 1 (1 [A1]) · (1 [A2]) · · · (1 [Am]). Expanding the
product, we complete the proof.
PROBLEM.
1◦.
Researchers at a research institute speak French, Russian, and English.
Among them, 20 people speak French, 15 speak Russian, and 10 speak English.
Also, 8 people speak French and Russian, 5 people speak Russian and English and
7 speak French and English. Two people speak French, Russian and English. How
many people work at the institute?
We are going to develop a technique which can be viewed as a combinatorial
calculus of convex sets. First, we define the class of functions we will be dealing
with.
Previous Page Next Page