Date: Fri, 30 Aug 1996 18:47:39 -0400 (EDT)
From: Jim Propp
Subject: proof of Euler-Poincare formula
Beifang Chen has told me of a rather slick proof of the V-E+F-...=1-(-1)^d
formula for convex polyhedra, and I'm wondering if any of you have seen
anything like it before.
One starts by defining "Euler integration" (a notion due to Schanuel
and subsequently explored by Rota, Chen, Klain, and others). The Euler
integral of a function f:R-->R (assumed to be piecewise-constant with
finitely many discontinuities) is the sum of
f(x) - (f(x+)+f(x-))/2,
where the sum is over the finitely many discontinuities of f, f(x+) =
lim_{t -> x+} f(t), and f(x-) = lim_{t -> x-} f(t).
One can then define multi-dimensional Euler integration for a natural
class of functions R^n-->R. (To be specific, the functions f that
we consider are linear combinations of indicator functions of
polyhedral sets in R^n, where a polyhedral set is one that can
be written in terms of closed half-spaces via union, intersection,
and complementation.) Euler integration is *additive*: the Euler
integral of f+g equals the sum of the Euler integrals of f and g.
Next we define the Euler measure of a polyhedral set as the Euler
integral of its indicator function. It is easy to show by
induction that the Euler measure of a closed bounded convex
polyhedron is always 1 (independent of dimension), while the
Euler measure of a d-dimensional relative-open bounded convex
polyhedron is (-1)^d.
Finally, appealing to the additivity of the Euler integral, we
observe that the Euler measure of the boundary of a closed
bounded convex polyhedron can be written in two ways: summing
the contributions of its relative-open faces (V-E+F-...) or
taking the difference between the Euler measures of the
closed polyhedron and its interior (1-(-1)^d).
Beifang Chen thinks that Rota and Schanuel must have known
all about the proof, but isn't totally sure. I'm wondering
if the proof might have an independent lineage.
Does the approach ring any bells?
Jim Propp
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
From: Bill Dubuque
Date: Tue, 3 Sep 1996 03:11:12 -0400
Cc: math-fun@cs.arizona.edu
Subject: Re: proof of Euler-Poincare formula
:Date: Mon, 2 Sep 1996 18:48:06 -0400 (EDT)
:From: Jim Propp
:
:I've just learned that the proof of Euler-Poincare that I posted last
:week was due to Hadwiger and streamlined by Rota.
Following are some interesting entry points into recent related
literature. For further deeper work see recent papers of the first
reviewer, Peter McMullen, who is a leading expert on such topics.
-Bill
96c:52024 Hilton, Peter; Pedersen, Jean. Euler's theorem for polyhedra:
a topologist and geometer respond. Comment to:
"A new look at Euler's theorem for polyhedra" [Amer. Math. Monthly 101
(1994), no. 2, 109--128; MR 95c:52032] by B. Grunbaum and G. C. Shephard.
With a response by Grunbaum and Shephard. Amer. Math. Monthly 101 (1994),
no. 10, 959--962. (Reviewer: P. McMullen) 52B70 (52B05)
94h:52006 Przes\l awski, Krzysztof. Linear algebra of convex sets and
the Euler characteristic. Linear and Multilinear Algebra 31 (1992),
no. 1-4, 153--191. 52A20
83h:52010 Sallee, G. Thomas. Euler's relation and where it led.
Convexity and related combinatorial geometry (Norman, Okla., 1980),
pp. 45--55, Lecture Notes in Pure and Appl. Math., 76, Dekker, New York,
1982. (Reviewer: Hiroaki Terao) 52A25 (52A37)
------------------------------------------------------------------------------
96c:52024 52B70 52B05
Hilton, Peter (1-SUNY2); Pedersen, Jean (1-STCL)
Euler's theorem for polyhedra: a topologist and geometer respond. Comment to:
"A new look at Euler's theorem for polyhedra" [Amer. Math. Monthly 101
(1994), no. 2, 109--128; MR 95c:52032] by B. Grunbaum and G. C. Shephard.
(English) With a response by Grunbaum and Shephard. Amer. Math. Monthly 101
(1994), no. 10, 959--962.
------------------------------------------------------------------------------
In writing this review, I have the uneasy feeling of straying into a
minefield, and possibly emulating the United Nations in being under fire from
both sides in a war not of my making. The criticisms of Hilton and Pedersen
directed towards the original article by Grunbaum and Shephard mentioned in
the title are rooted in topology. However, the article is really concerned
with geometry (and perhaps combinatorics); I hope that I can make the subtle
distinction clear.
Or course, no one any longer seriously believes that the formula $v-e+f=2$ is
one which should be satisfied by every polyhedron; this is one Aunt Sally
(among others, particularly in the historical discussion) put up by the
original authors as an easy target to be shot down. But it does raise an
important question---what is to be counted as a face? From a purely
combinatorial point of view (and I do not mean topological), there is no
reason for a face to be a cell; there is no a priori justification for
excluding an annulus, for example. The present authors' statement "We claim
that a polyhedron is made of cells $\ldots$" sounds rather dogmatic; perhaps
its first three words should have read "In our opinion".
Of course, Euler's formula then breaks down, but it generally will in any
case. The problem is thus to devise appropriate ways of repairing it. In the
context of (non-convex) regular polytopes, Schlafli would not accept those
which failed to satisfy Euler's formula, such as the great dodecahedron
$\{5,\tfrac 52\}$ of genus 4, and so refused to discover the regular
4-polytopes which use it or its dual as a component. The correction to the
formula here involves numbers called "densities" [see H. S. M. Coxeter,
Regular polytopes, third edition, Dover, New York, 1973; MR 51 #6554].
However, this way round the problem is very special. It is generally agreed
that one wants a formula which is "topologically invariant", whatever that
might mean (and I do not intend this to be taken disparagingly). But such a
formula does not have to be reached solely by relatively high-powered
topological methods. So while the expression of the Euler characteristic as
the alternating sum of Betti numbers is the most general possible, for
geometric objects such as finite unions of convex polytopes (or even compact
convex sets), H. Hadwiger and his successors (beginning with Hadwiger
[J. Reine Angew. Math. 194 (1955), 101--110; MR 17, 402a]) have shown how
to get away with more elementary techniques. Here, I feel that the original
authors missed a trick. The proof of Euler's theorem for convex polytopes
given by Grunbaum [Convex polytopes, Interscience, New York, 1967; MR 37
#2085] can be interpreted as a Morse-theoretic argument (and so rather
topological), and is perhaps closer to those of Hadwiger than he and
Shephard suggest; it is thus also dual to the shelling proof validated by
H. Bruggesser and P. Mani [Math. Scand. 29 (1971), 197--205 (1972); MR 48
#7286]. Nevertheless, I sympathize with the present authors' feeling that
the attitude in the original article to Betti numbers was somewhat
dismissive---was it really necessary to refer to them in quotation marks, and
additionally label them "so-called"?
I hope that I have succeeded here in remaining relatively neutral between the
contestants. To make clear that I wish to sit on the fence, let me sum up what
I have said. The topological approach to the Euler characteristic is deep,
powerful and very general. Nevertheless, when the context does not demand such
heavy machinery, it is nice to be able to avoid its use.
Reviewed by P. McMullen
------------------------------------------------------------------------------
94h:52006 52A20
Przes\l awski, Krzysztof (PL-ZLG-IM)
Linear algebra of convex sets and the Euler characteristic. (English. English
summary) Linear and Multilinear Algebra 31 (1992), no. 1-4, 153--191.
------------------------------------------------------------------------------
Introduction: "In 1955 Hadwiger introduced the Euler characteristic $\chi$
on the finite unions of convex bodies of $n$-dimensional Euclidean vector
space using entirely elementary construction. Since then $\chi$ and various
extensions of $\chi$ have played an important part in combinatorial geometry
and in general problems of enumeration (see an excellent survey by P. McMullen
and R. Schneider [in Convexity and its applications, 170--247, Birkhauser,
Basel, 1983; MR 85e:52001] for the first topic and G.-C. Rota's
classical papers [Z. Wahrsch. Verw. Gebiete 2 (1964), 340--368; MR 30
#4688; in Studies in pure mathematics (presented to Richard Rado), 221--233,
Academic Press, London, 1971; MR 44 #126] for the second one). It was also
Hadwiger who observed in 1960 that $\chi$ can be extended to a linear
functional on the vector space consisting of the characteristic functions of
convex bodies. It appeared that a great part of the so-called valuation theory
can be reconstructed on the basis of linear algebra. This approach has been
developed by Groemer in a series of papers.
"The aim of these investigations is to show that surprisingly many operations
over convex sets can be linearized and they yield various interesting linear
and multilinear mappings. Moreover, some extensions or new expressions for
many already known results are given. For example, the Euler characteristic is
defined here for a broader class of sets than has been done so far. The paper
has two characteristic features: first, relatively open convex sets and closed
convex sets are considered here jointly; second, all results are formulated in
the language of normed spaces."
------------------------------------------------------------------------------
83h:52010 52A25 52A37
Sallee, G. Thomas
Euler's relation and where it led. (English) Convexity and related
combinatorial geometry (Norman, Okla., 1980), pp. 45--55,
Lecture Notes in Pure and Appl. Math., 76,
Dekker, New York, 1982.
------------------------------------------------------------------------------
Let P{sup}d denote the class of all convex polytopes in E{sup}d, d-dimensional
Euclidean space. If P{in}P{sup}d, the Euler relation is {sum}
{sub}(i=0){sup}d( - 1){sup}if{sub}i(P)=1, where f{sub}i(P) denotes the number
of i-dimensional faces of P. Let V be a vector space. For phi {in}Map(P
{sup}d, V) define phi {sup}{in}Map(P{sup}d, V) by phi {sup}(P)={sum}( - 1)
{sup}(dimF) phi (F) (the sum is taken over all nonempty faces of P{in}P
{sup}d). Then the Euler relation is nothing but 1=1{sup} for the constant
function 1{in}Map(P{sup}d, R). One says that phi satisfies the Euler-type
relation if phi = epsilon phi {sup} (epsilon ={plmin}1). A valuation psi
{in}Map(P{sup}d, V) is a map satisfying the equality psi (P{cup}Q)+ psi (P
{cap}Q)= psi (P)+ psi (Q) whenever P{cup}Q is convex. First the author reviews
important results concerning the connection between the Euler-type relation
and the valuation by the author [Canad. J. Math. 20 (1968), 1412 - 1424; MR
38 #605] and by P. McMullen [Proc. London Math. Soc. (3) 35 (1977), no. 1,
113 - 135; MR 56 #6548]. Next he proposes the possibilities of proving
many corollaries of the Euler-type relation by using the notion of an
incidence algebra, due to G.-C. Rota. For example, the equality (phi {sup})
{sup}= phi is proved as a corollary of the Euler relation through the
language of incidence algebra. Finally he poses several unsolved problems and
comments on the valuations and the Euler relation. (For the entire collection
see MR 83b:52002.)
Reviewed by Hiroaki Terao