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.