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