Is there a topological description of combinatorial Euler characteristic? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T14:10:42Z http://mathoverflow.net/feeds/question/1184 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1184/is-there-a-topological-description-of-combinatorial-euler-characteristic Is there a topological description of combinatorial Euler characteristic? Theo Johnson-Freyd 2009-10-19T07:59:04Z 2009-10-29T14:06:51Z <p>There are a collection of definitions of "combinatorial Euler characteristic", which is different from the "homotopy Euler characteristic". I will describe a few of them and give some references, and then ask how far they can be generalized.</p> <ul> <li><p>A good place to start is <a href="http://en.wikipedia.org/wiki/Hadwiger%27s%5Ftheorem" rel="nofollow">Hadwiger's theorem</a>. Define a "Hadwiger measure" <em>m</em> on <strong>R</strong><sup>n</sup> to be a thing that assigns (possibly negative) real numbers to (nice?) subsets of <strong>R</strong><sup>n</sup> in such a way that the assignment is invariant under rigid transformations (i.e. isometries) and satisfies the "inclusion-exclusion" principle that <em>m</em>(<em>A</em> &cup; <em>B</em>) = <em>m</em>(<em>A</em>) + <em>m</em>(<em>B</em>) - <em>m</em>(<em>A</em> &cap; <em>B</em>); Hadwidger measures are also required to satisfy some analytic properties. Then Hadwidger proves that the space of measures on <strong>R</strong><sup>n</sup> is precisely (<em>n</em>+1)-dimensional, and has a basis <i>m<sub>i</sub></i> with <i>m<sub>i</sub></i>([0,1]<sup>i</sup>) = 1 and <i>m<sub>i</sub></i>(&lambda; <em>A</em>) = &lambda;<sup>i</sup> <i>m<sub>i</sub></i>(<em>A</em>), where &lambda; <em>A</em> is the set rescaled by a factor of &lambda; in every direction. In particular, <i>m</i><sub>0</sub> of a finite set counts the number of points, and agrees with Euler characteristic for compact regions; the function <i>m</i><sub>0</sub> is the "combinatorial Euler characteristic". It is not homotopy-invariant: <i>m</i><sub>0</sub>([0,1]) = 1 whereas <i>m</i><sub>0</sub>(<strong>R</strong>) = -1. It is multiplicative.<br><br>Incidentally, Hadwiger's paper is in German and so I cannot read it. Apparently all this material is in Rota's book "Introduction to Geometric Probability", but I have been away from a library and haven't read it yet. Thus I don't know the precise statement of "nice".</p></li> <li><p>Schanuel in MR1173024 various "geometric categories". Namely, say that a subset of <strong>R</strong><sup>n</sup> is a "polyhedron" if it is the positive locus finitely many affine maps to <strong>R</strong>; close the collection of polyhedra under union, intersection, and complement, and thus recover the notion of "polyhedral set" (so that a polyhedral set is actually a pair (<em>n</em>,<em>S</em>) where <em>S</em> is a subset of <strong>R</strong><sup>n</sup> satisfying certain properties). Then morphism of polyhedral sets is a set-theoretic function whose graph (as a subset of <strong>R</strong><sup>n</sup> x <strong>R</strong><sup>m</sup>) is polyhedral. Then it's straightforward to check that a morphism is an isomorphism if it is a set-theoretic bijection &mdash; morphisms allow gluing and cutting.<br><br>Or replace the word "affine" with "polynomial" and thus recover the notion of "semi-algebraic set". Or restrict your attention to bounded polyhedral sets. Anyway, each of these geometric categories has well-behaved product and coproduct, and so a "Burnside Rig" (ring without negation) whose elements are isomorphism classes of objects. Schanuel computes each of these Burnside rigs, and shows that the universal cancelative quotient of each is the integers; this map to <strong>Z</strong> is the combinatorial Euler characteristic.</p></li> <li><p>Apparently there are also more analytic definitions. Schanuel in MR842922 (wonderful but only trying to develop intuition and motivation) suggests that each of the Hadwiger measures can be defined in terms of curvatures and whatnot, but the formulas he gives only make sense for compact manifolds (with boundaries, corners...).<br><br>Chen (MR1215324) describes the combinatorial Euler characteristic with the following fun integral: let <em>f</em>: <strong>R</strong> &rarr; <strong>R</strong> be continuous except for finitely many jump and/or removable discontinuities, and define &int;<sub>Euler</sub>f = &Sigma;<sub><i>x</i>&isin;<strong>R</strong></sub> [ f(x) - (1/2) (f(x<sup>+</sup>) + f(x<sup>-</sup>)) ]; then try to compute Euler integrals of characteristic functions. The problem is that he then defines the multi-dimensional version via the Fubini theorem, but suggests that his integrals depend on a choice of basis.</p></li> <li><p>The definition of combinatorial Euler characteristic is great for "finite polyhedral complexes", I think. By a "finite polyhedral complexes" I mean glue together finitely many polyhedra, but you're allowed to leave some faces open, so that unlike a CW complex not every cell must have complex closure. Then you can calculate Euler characteristic with the usual formula: (number of cells of even dimension) - (number of cells of odd dimension). I think this is a topological (but not homotopy!) invariant.</p></li> </ul> <p>Anyway, so first, are there references I've missed?</p> <p>Second and more importantly, all the references consider only subsets of Euclidean space (well, Schanuel briefly mentions the Burnside rig of varieties/<strong>C</strong>, but only computes a quotient). Why? Why isn't there an intrinsic topological description, or perhaps manifold-theoretic description?</p> <p>In particular, a "measure-theoretic" version that does not rely on embeddings in Euclidean space would be great, as it would presumably give "measures" against which we could integrate smooth functions. Any ideas?</p> http://mathoverflow.net/questions/1184/is-there-a-topological-description-of-combinatorial-euler-characteristic/1192#1192 Answer by Robert Ghrist for Is there a topological description of combinatorial Euler characteristic? Robert Ghrist 2009-10-19T10:08:00Z 2009-10-19T10:08:00Z <p>the best approach to the geometric euler characteristic comes from the theory of o-minimal structures. </p> <p>the best reference in this area is the book "tame topology and o-minimal structures" by lou van den dries. requires very little background to understand.</p> <p>in brief: an o-minimal structure is collection of boolean algebras of subsets of $R^n$ which satisfies a short list of axioms. (the name comes from model theory, but you don't need to know any model theory to understand the results)</p> <p>examples of o-minimal structures include the semialgebraic sets, the globally subanalytic sets, and (if you tweak the definitions a bit) the piecewise-linear sets.</p> <p>elements of an o-minimal structure are "tame" or "definable" sets. mappings between tame sets are tame iff their graph is a tame set.</p> <p>basic relevant results:</p> <p>every tame set has a well-defined euler characteristic.</p> <p>two tame sets are "definably homeomorphic" (there is a tame bijection between them --- not necessarily continuous!) iff they have the same dimension and euler characteristic. </p> <p>(yes, i wrote iff - this is the first surprise in this subject)</p> <p>one can so this for more general manifolds as well. </p> <p>concerning integration with respect to euler characteristic:</p> <p>1) in the o-minimal framework, one can integrate all constructible functions, as noted by viro and schapira in the 1980s, based on works of macpherson and kashiwara in the 1970s. these results follow from sheaf theory. though more difficult than the combinatorial approach, all these proofs are "natural" and don't rely on "luck".</p> <p>2) if you want to integrate non-constructible (e.g., smooth) integrands, the theory of chen (really due to rota) will fail -- that integral vanishes on all continuous integrands.</p> <p>3) baryshnikov and ghrist have extensions of the integral to definable integrands (see 2009 arxiv paper). there are two such extensions, and they are dual. there are deep connections with morse theory, but the integral operators are unfortunately non-linear, and the fubini theorem does not hold in full generality.</p> http://mathoverflow.net/questions/1184/is-there-a-topological-description-of-combinatorial-euler-characteristic/1261#1261 Answer by Reid Barton for Is there a topological description of combinatorial Euler characteristic? Reid Barton 2009-10-19T18:55:56Z 2009-10-19T18:55:56Z <blockquote> <p>Why isn't there an intrinsic topological description, or perhaps manifold-theoretic description?</p> </blockquote> <p>At least in some cases, the combinatorial Euler characteristic of X is equal to the homotopy Euler characteristic of the one-point compactification of X minus 1. For instance this is true when X is compact (of course) and also when X = R^n. It's true for all "nice" subsets of R^1. I don't know whether it works when X is, say, the open unit square plus one of its vertices.</p> <p>Of course the first question is whether the combinatorial Euler characteristic is even a homeomorphism invariant. I would like to know the answer also.</p> http://mathoverflow.net/questions/1184/is-there-a-topological-description-of-combinatorial-euler-characteristic/1447#1447 Answer by David Speyer for Is there a topological description of combinatorial Euler characteristic? David Speyer 2009-10-20T16:16:34Z 2009-10-20T16:16:34Z <p>Barvinok, in Lecture 1 of his Park City Lectures (reprinted in IAS/Park City Math Series Volume 13), defines an Euler characteristic which is very similar to this one. His domain of definition is sets whose indicator functions can be written as a finite linear combination of indicator functions of polyhedra, and he states as an exercise that this can be extended to linear combinations of indicator functions of convex sets. </p> <p>With his conventions, chi is not a homeomorphism invariant, because chi(\mathbb{R})=1 and chi( (0,1))=-1. It is not clear to me what harm would come from letting the Euler characteristic of the real line be -1. </p> http://mathoverflow.net/questions/1184/is-there-a-topological-description-of-combinatorial-euler-characteristic/1450#1450 Answer by Tom Leinster for Is there a topological description of combinatorial Euler characteristic? Tom Leinster 2009-10-20T16:39:13Z 2009-10-20T16:39:13Z <p>The precise statement of "nice" in Hadwiger's Theorem is "expressible as a finite union of compact convex sets". In their book <i>Introduction to Geometric Probability</i>, Klain and Rota use "polyconvex" for such a set.</p> <p>There's a whole list of possibly-relevant references here: <a href="http://math.ucr.edu/home/baez/counting/" rel="nofollow">http://math.ucr.edu/home/baez/counting/</a></p> http://mathoverflow.net/questions/1184/is-there-a-topological-description-of-combinatorial-euler-characteristic/3262#3262 Answer by Robert Ghrist for Is there a topological description of combinatorial Euler characteristic? Robert Ghrist 2009-10-29T14:06:51Z 2009-10-29T14:06:51Z <p>a few comments on the comments above:</p> <ol> <li><p>the combinatorial euler characteristic of a definable space (roughly speaking, a space with finite decomposition into finite-dimensional cells) is a homeomophism invariant, but not a homotopy invariant. there is a corresponding homological definition in terms of borel-moore homology or, if preferred, cohomology with local coefficients. it is, indeed, an invariant of definable bijections --- which do not need to be continuous. </p></li> <li><p>the "polyconvex" sets are the combinatorial approach to "tame" sets. if you use the o-minimal theory, then you can vastly generalize the class of spaces for which euler characteristic is well-defined.</p></li> <li><p>one reason to use the combinatorial (sometimes called "geometric") euler characteristic is that it satisfies the mayer-vietoris principle (or inclusion/exclusion) without requiring the spaces to be compact. specifically, $\chi(A \cup B) = \chi(A) + \chi(B) - \chi(A \cap B)$. hence, you can treat $d\chi$ as a finitely-additive signed measure on definable spaces and integrate constructible functions. </p></li> </ol> <p>i apologize for harping on the o-minimal theory, but i found that it greatly simplified and generalized otherwise clunky proofs. the book of van den dries on the subject is very elementary and clear. </p>