INSIDE-OUT POLYTOPES

MATTHIAS BECK AND THOMAS ZASLAVSKY

Abstract. We present a common generalization of counting lattice points in rational polytopes and the enumeration of proper graph colorings, nowhere-zero flows on graphs, strictly magic squares and graphs, strictly antimagic squares and graphs, and generalized latin squares. Our method is to generalize Ehrhart’s theory of lattice-point counting to a convex polytope dissected by a hyperplane arrangement. We particularly develop the applications to graph and signed-graph coloring and antimagic labellings.

Authors’ addresses: Matthias Beck, Max-Planck-Institut für Mathematik, Vivatsgasse 7, 53111 Bonn, Ger-

many, beck@mpim-bonn.mpg.de

Thomas Zaslavsky, Department of Mathematical Sciences, Binghamton University (SUNY), Binghamton, NY 13902-6000, U.S.A., zaslav@math.binghamton.edu

Running head: Inside-Out Polytopes

Date: Version of 24 May 2004. 2000 Mathematics Subject Classification. Primary 52B20, 52C35; Secondary 05B35, 05C15, 05C22,

05C78, 52C07.

Key words and phrases. Lattice-point counting, rational convex polytope, arrangement of hyperplanes, arrangement of subspaces, valuation, graph coloring, signed graph coloring, antimagic square, antimagic graph, antimagic labelling.

This paper was mostly written while the first author was a Robert Riley Assistant Professor at Binghamton University, SUNY. The author thanks the Department of Mathematical Sciences at Binghamton for its hospitality.

The research of the second author was partially supported by National Science Foundation grant DMS-0070729.

Contents

1. In which we introduce polytopes, hyperplanes, and lattice points to the reader and each other 2

2. In which more characters take the stage 7 3. In which we encounter facially weighted enumerations 8 4. In which we arrange Ehrhart theory with hyperplanes 10 5. In which we color graphs and signed graphs 13 6. In which we become antimagic 19 7. In which subspace arrangements put in their customary appearance 22 8. In which we prove a general valuation formula 23 Acknowledgement 25 References 25

1. In which we introduce polytopes, hyperplanes, and lattice points to the reader and each other

We study lattice-point counting in polytopes with boundary on the inside. To say this in a less mysterious way: we consider a convex polytope, P, together with an arrangement (a finite set) of hyperplanes, ℋ, that dissects the polytope, and we count points of a discrete lattice, such as the integer lattice ℤ^{d}, that lie in P. We want to count the lattice points that lie in the interior of P but not in any of the hyperplanes; in effect, we regard (P, ℋ), the polytope together with the hyperplanes, as a polytope with boundary on the inside as well as the outside (hence the name “inside-out polytope”) and our problem as that of counting points in the interior of an inside-out polytope. Among our results are generalizations of the usual Ehrhart theory of counting lattice points in dilated polytopes.

A simple illustration is the following situation. The polytope P is [0, 1]^{2} in ℝ^{2} and the hyperplane arrangement ℋ consists of the single line h : x_{1} = x_{2}. (See Figure 1.) The number of integral points in the interior of (P, ℋ) dilated by a factor t = 1, 2, 3, …, i.e., in (0, t)^{2} \ h, is f^{∘}(t) = (t − 1)(t − 2). The fact that this is a polynomial is a special case of one of our theorems (Theorem 4.1). Now, according to Ehrhart reciprocity for rational polytopes as extended in Theorem 4.1, the number of lattice points in the closed inside-out polytope (P, ℋ) ought to be f(t) := (−1)^{2}f^{∘}(−t) = (t+1)(t+2). But this is not the number of points in tP = [0, t]^{2}; instead, it is the number in tP plus the number in tP ∩ h; also, taking a different point of view, it is the number of points in tP counted with multiplicity 1 for a point not in h and 2 for a point in h, the multiplicity of the latter being 2 because such a point lies in two of the closed regions into which h divides ℝ^{2}. The fact that f(t) is such a count with multiplicity is another part of Theorem 4.1. The fact that f(t) is a sum of counts over tP and tP ∩ h illustrates another result, Theorem 4.2.

A similar computation results from taking the single hyperplane h′ : x_{1} + x_{2} = 1. In this case the method of dilation is unsatisfactory because it disturbs the hyperplane arrangement. We therefore generally adopt the point of view according to which the lattice is contracted by a factor of t while the polytope and arrangement remain fixed.

We became interested in inside-out lattice-point counting because of a geometrical interpretation of coloring of graphs and signed graphs. The first purpose of our paper, indeed, is to encompass colorings and acyclic orientations of graphs and signed graphs within the Figure 1. The lattice points in (k + 1)[0, 1]^{2} that k-color the graph K_{2}, with k = 8.

general framework of counting lattice points in polytopes. Our second purpose in this paper and its sequels [3, 4] is to apply the framework of inside-out polytopes to a multitude of counting problems in which there are forbidden values or relationships amongst the values of an integral linear function on a finite set which might, for instance, be the edge set of a graph or the set of cells of an n × n square. Main examples, aside from graph coloring, are nowhere-zero integral flows, magic, antimagic, and latin squares, magic and antimagic graphs, and generalizations involving rational linear forms. Our results are of three kinds: quasipolynomiality of counting functions, Möbius inversion formulas, and the appearance of quantities—the aforementioned multiplicities—that generalize the number of acyclic orientations of a graph but whose combinatorial interpretation is, in some examples at any rate, an open problem. Among our applications, two stand out. We show how to count antimagic labellings in a systematic way (Section 6), and we explain why a signed graph has not one, as with ordinary graphs, but two different chromatic polynomials (Theorem 5.6).

Let us begin with an explanation of graph coloring. A coloring in c colors of a graph Γ, with node set V = [n] := {1, 2, …, n}, is a function x : V → [c]. (By [k] we mean the set {1, 2, …, k}, the empty set if k = 0.) x is proper if, whenever there is an edge ij, x_{i} ≠ x_{j}. It is a short step to regard x as a point in the real affine space ℝ^{n} and call it proper if it lies in none of the hyperplanes h_{ij} : x_{i} = x_{j} for ij ∈ E, the edge set of Γ. That is, if we write

ℋ[Γ] := {h_{ij} : ij ∈ E},

which is the hyperplane arrangement of the graph Γ, then counting proper colorings of Γ means counting integral points in [c]^{n}\⋃ ℋ[Γ]. From a general point of view, we are counting lattice points in a polytope but outside an arrangement of hyperplanes. The polytope is (c + 1)P^{∘}, a dilation of the interior of the unit hypercube P := [0, 1]^{n}. Write E_{P^{∘},ℋ[Γ]}^{∘} (c + 1) for the number of points we count; that is, the number of proper c-colorings of Γ. It is well known that this is a monic polynomial in c, called the chromatic polynomial of Γ. In Section 5 we derive, from our inside-out counting theory, that fact and more. A famous theorem of Stanley’s [27] states that when one evaluates the chromatic polynomial at negative integers, one obtains the function, a priori unrelated to proper graph coloring, that counts pairs consisting of k-colorings (not necessarily proper) and compatible acyclic orientations of the graph; in particular, the evaluation at −1 gives the number of acyclic orientations. According to our theory, this fact is a particular case of the general geometrical phenomenon of Ehrhart reciprocity.

Standard Ehrhart reciprocity [11, 28] applies to a closed, d-dimensional polytope P with rational vertices. It says that, if E_{P} (t) is the number of points of the integer lattice ℤ^{d} that are contained in the dilation tP (t a positive integer) and E_{P^{∘}}(t) is the number in the interior tP^{∘}, then E_{P^{∘}}(t) = (−1)^{d}E_{P} (−t) [10, 21]. E_{P} is well defined at negative integers because of Ehrhart’s fundamental theorem [9] that E_{P} is a quasipolynomial in t: that is, E_{P} (t) = ∑_{0}^{d} c_{i}t^{i} with coefficients c_{i} that, though not necessarily constant, at any rate are periodic functions of t (so that E_{P} (t) is a polynomial on each residue class modulo some integer, called the period; these polynomials are the constituents of E_{P}). We generalize these results to inside-out polytopes in Theorem 4.1.

To indicate the generalization and the application to graph coloring, we must first expand on the geometry of real hyperplane arrangements. An arrangement ℋ of affine hyperplanes in ℝ^{d} divides up the space into regions: an open region is a connected component of ℝ^{d} \⋃ ℋ and a closed region is the topological closure of an open region. The theory of arrangements began in 1826 with arrangements of lines, planes, circles, and spheres in the article of Steiner [30] ultimately inspired by the progressive educational reformer Pestalozzi. Steiner wished to count the number of regions of ℝ^{2} or ℝ^{3} dissected by an arrangement, a project that was not truly completed, and then only for hyperplanes, until 150 years later in [34]. There it was found that the number of regions into which a hyperplane arrangement ℋ divides ℝ^{d} is

r(ℋ) = (−1)^{d}p_{ℋ} (−1);  (1.1)

here p_{ℋ} is the characteristic polynomial of ℋ, defined by

p_{ℋ} (λ) := ∑_{s∈ℒ(ℋ)} μ(s)λ^{dim s}

where

ℒ(ℋ) := {⋂𝒮 : 𝒮 ⊆ ℋ and ⋂𝒮 ≠ ∅},

ordered by reverse inclusion [34], and μ(s) is essentially the Möbius function of ℒ(ℋ) (see Section 2).

Inside-out Ehrhart reciprocity involves the concept of multiplicity of a point x, which is the number m(x) of closed regions of ℋ in which x lies. In the graphic case, where the arrangement is ℋ[Γ] in ℝ^{n}, each region corresponds (by [13] or [15, Section 7]) to an acyclic orientation of Γ that is compatible with each coloring x in the closure of the region, in the sense that each edge is oriented from a lower color to a color that is at least weakly higher. Thus m(x), if x is a coloring point, equals the number of acyclic orientations of Γ that are compatible with the coloring. If we write E_{P,ℋ[Γ]} (c) for the sum of m(x) over all integral points x ∈ cP, then E_{P,ℋ[Γ]} (c) = (−1)^{n}E_{P^{∘},ℋ[Γ]}^{∘} (−c): this is Stanley’s theorem expressed as Ehrhart reciprocity.

Our principal motivating example, signed graph coloring, is more complicated than ordinary graph coloring. A signed graph Σ is a graph in which each edge is signed, positive or negative. There is a notion of proper coloring of signed graphs [36] (which we explain in Section 5) according to which a signed graph has not one but two different chromatic polynomials. Why there are two polynomials and how they might be related was a mystery, but it is now possible to state the reason: the two polynomials are the two constituent polynomials of the single Ehrhart quasipolynomial E_{P,ℋ} of an inside-out polytope (P, ℋ) (Theorem 5.6). And there is another startling fact: the polynomials are the characteristic polynomial of the arrangement ℋ and a simple modification of it. A third purpose of our work is to explain and generalize this coincidence.

We have two techniques for attacking the problem of inside-out polytope counting. In the first we dissect the polytope into its intersections with the regions of the hyperplane arrangement. The intersections are rational polytopes whose Ehrhart quasipolynomials sum to that of the inside-out polytope. Thus we get quasipolynomiality and reciprocity together with interpretations of the leading coefficient and constant term. The second technique is Möbius inversion over the lattice of flats of the arrangement, i.e., sophisticated inclusionexclusion. This generalizes the unification of chromatic polynomials of graphs and signed graphs with inside-out polytopes and hyperplane arrangements. The strongest results come in applications where the two methods meld, as most neatly in graph coloring. (Curiously, both techniques were anticipated to an extent by Stanley, as we recently learned [29]. Stanley used a method equivalent to dissection to give a second proof of his combinatorial interpretation of the chromatic polynomial at negative arguments; the proof is that via the order polynomial [27]. Much later, Kochol applied a dissection argument to nowhere-zero flows [18]. Then, in his textbook [28, Exercise 4.10] Stanley suggests Möbius inversion over the Boolean algebra or the partition lattice to find the number of nonnegative integral solutions x, with all coordinates distinct, of a rational linear system Ax = 0—such as the equations of a magic square.)

Beyond graph coloring are other examples. A nowhere-zero k-flow on a graph Γ is a mapping x : E → [k − 1], defined on some orientation of Γ, such that the total inflow equals the total outflow at each node. The existence of nowhere-zero integral flows of small width k is a major open question in graph theory, whose solution could imply the Four-Color Theorem. Our theorems do not answer the existence question but they do prove that the number of nowhere-zero k-flows is a polynomial function of k (a result recently discovered by Kochol [18]) and they interpret the value of that function at negative arguments in terms of compatible pairs of k-flows and acyclic orientations. They also provide similar results for integral flows on signed graphs. This application is reported in a separate article [3].

In the same spirit as graphs and flows are applications to magic squares and their multitude of relatives: semimagic and pandiagonal magic squares, magic cubes [1, 2] and hypercubes, magic graphs, magical oddities like circles, spheres, and stars [1]. A magic square is an n×n array of distinct positive, or sometimes nonnegative, integers whose sum along any line (row, column, or diagonal) is the same number, the magic sum. The rules for a magic square have varied with time and writer; but historically the contents have been integers, positive and distinct. In the past century, though, mathematicians have made some simplifications in the interest of obtaining results about the number of squares with a fixed magic sum. Thus we have, most significantly, the omission of the fundamental requirement of distinctness. Since the terminology is rather confused, we call a square magic or strongly magic if its entries are distinct and weakly magic if they need not be distinct. The number of weakly magic squares is amenable to analysis in terms of Ehrhart theory, but there have been almost no exact (theoretical) formulas for strong magic. With inside-out polytopes we can attack this and many similar counting problems (of the kind that we describe below for antimagic) in a systematic way. We obtain not only a general result about their counting functions but also a fascinating interpretation of reciprocity that leads to a new kind of question about permutations.

Related to magic squares are something we call magilatin squares. A latin square is an n × n array in which each cell is filled by one of n symbols so that no row or column contains the same symbol twice. Allowing more symbols, but retaining the property of equal line sums, we have a magilatin square. Our treatment is similar to that of magic squares, but the distinctness requirement, and consequently the hyperplane arrangement, are different. While in a magic square each entry must differ from every other, in a magilatin square it must differ only from those that are collinear with it, a line here being a row or column.

We treat magic and magilatin objects in the separate paper [4]. Here, in Section 6, we examine the more difficult question of antimagic labellings.

Antimagic is like magic but with the crucial difference that the line sums all evaluate to different numbers. An antimagic square, for instance, is an n×n array of distinct positive, or nonnegative, integers whose sums along any line are all different numbers. In an antimagic graph the edges are assigned integers so that the label sums of the edges incident to the different nodes are distinct (see the survey [12, Section 5.4]). A very general picture consists of a covering clutter: a nonvoid finite set X of points together with a family ℒ of subsets, called lines for no particular reason, of which none contains any other, and whose union is X. We want to assign integers to X so that all line sums are distinct. Such a labelling is called strongly, or weakly, antimagic if we do, or do not, require the labels to be distinct. A standard labelling is strong and employs the label set {1, 2, …, |X|}. There are many interesting examples that have been the object of greatly varying degrees of attention. (X, ℒ) may be a finite affine or projective geometry, the “lines” being the subspaces of any fixed dimension; more generally it may be a block design. It may be an n×n×⋯×n hypercubical array. It may be a k-net, where the lines fall into k parallel classes (with k ≥ 2) so that each point belongs to a unique line in each parallel class. These examples have lines of equal size, a property that has certain advantages but, as in antimagic graphs where the line sizes may vary, is not necessary for the existence of the desired labellings.

For the greatest generality of all we take a set of homogeneous, rational linear forms f_{1}, …, f_{m} ∈ (ℝ^{d})^{∗}, and we want to count integer points x ∈ (0, t)^{d} such that

f_{j}(x) ≠ f_{k}(x) if j ≠ k.

These points are antimagic labellings. Counting antimagic labellings, whether strong or weak, is not readily done with standard methods, because it is intrinsic to the problem that one has nonequalities between the line sums. That is just what our approach is well suited to handle, by treating the process of line summation as a linear transformation into a vector space of sums, in which there is a hyperplane arrangement guaranteeing unequal sum values.

We conclude this paper with two short sections on supplemental topics: subspace arrangements and general valuations. These are intended to clarify the phenomena by indicating the essential requirements for a theory of our type. A lattice-point count is one kind of valuation; another example is the combinatorial Euler characteristic, which is the alternating sum a_{0} − a_{1} + ⋯ of the number a_{i} of open cells of each dimension i into which a geometrical object can be decomposed. In Section 8 we show that the Möbius inversion formulas (as will be no surprise) apply to any valuation.

2. In which more characters take the stage

The Möbius function of a finite partially ordered set (a poset) S is the function μ : S×S → ℤ defined recursively by

μ(r, s) := \begin{cases}0 & if r ≰ s, \\ 1 & if r = s, \\ − ∑_{r≤u<s} μ(r, u) & if r < s. \end{cases}

Sources are, inter alia, [24] and [28, Section 3.7]. S may be the class of closed sets of a closure operator; in that case if ∅ is not closed we define μ(∅, s) := 0 for s ∈ S.

In a poset P, ˆ0 denotes the minimum element and ˆ1 the maximum element, if they exist. A lattice poset (commonly called simply a “lattice” but we must differentiate it from a discrete lattice) is a poset in which any two elements have a meet and a join: a greatest lower bound and a least upper bound. A meet semilattice is a poset in which meets exist but not necessarily joins.

One kind of poset is the intersection semilattice of an affine arrangement ℋ of hyperplanes, that is, ℒ(ℋ) defined in the introduction. The elements of ℒ(ℋ) are called the flats of ℋ. ℒ is a geometric semilattice (of which the theory is developed in [32, 23]) with ˆ0 = ⋂ ∅ = ℝ^{d}; it is a geometric lattice (for which see [24, p. 357] or [28], etc.) if ℋ has nonempty intersection, as when all the hyperplanes are homogeneous. A hyperplane arrangement decomposes the ambient space into relatively open cells called open faces of ℋ, whose topological closures are the closed faces. For a more precise definition we need the arrangement induced by ℋ on a flat s; this is

ℋ^{s} := {h ∩ s : h ∈ ℋ, h ⊉ s}.

A face of ℋ is then a region of any ℋ^{s} for s ∈ ℒ(ℋ). One face is ˆ1 = ⋂ ℋ itself, if nonempty. An oddity about hyperplane arrangements is that, for technical reasons, one wants to treat the whole space as a hyperplane (called the degenerate hyperplane) that may or may not belong to ℋ. If ℋ contains the degenerate hyperplane, it has no regions, because ℝ^{d} \ ⋃ ℋ = ∅. However, ℋ does have faces; e.g., its d-dimensional faces are the regions of ℋˆ0, the arrangement induced in ˆ0 = ℝ^{d}.

The characteristic polynomial of ℋ is defined in terms of the Möbius function of ℒ(ℋ) by

p_{ℋ} (λ) := \begin{cases}0 & if ℋ contains the degenerate hyperplane, and \\ ∑_{s∈ℒ(ℋ)} μ(ˆ0, s)λ^{dim s} & otherwise. \end{cases}

And three more definitions: for a set or point X in ℝ^{d},

ℋ(X) := {h ∈ ℋ : X ⊆ h},
s(X) := ⋂ ℋ(X) = ⋂{h ∈ ℋ : X ⊆ h},

the smallest flat of ℋ that contains X, and

F (X) := the unique open face of ℋ that contains X

provided that X is contained in an open face, as for instance when it is a point.

A convex polytope P (for which see, e.g., [38]) is a bounded, nonempty set that is the intersection of a finite number of open and closed half spaces in ℝ^{d}; P may be closed, relatively open, or neither. A closed convex polytope is also the convex hull of a finite set of points in ℝ^{d}. Another kind of poset is the face lattice of P. A closed face of P is either P̄, the topological closure of P, or the intersection with P̄ of any hyperplane h such that P \ h is connected. (Then h is a supporting hyperplane of P; this includes hyperplanes that do not intersect P at all.) An open face is the relative interior F^{∘} of a closed face F. (The relative interior of a point is the point.) The null set is a face; it and P̄ (or P^{∘}) are the improper faces. The face lattice ℱ(P) is the set of open faces, partially ordered by inclusion of the closures. A vertex is a 0-dimensional face. A facet is a face whose dimension is dim P − 1; a facet hyperplane is the affine span of a facet. If P ⊆ ℝ^{d} is not full-dimensional, then a facet hyperplane is a relative hyperplane of the affine flat spanned by P.

A dilation of a set X ⊆ ℝ^{d} (also called a contraction if t < 1) is any set tX = {tx : x ∈ X} for a real number t > 0.

3. In which we encounter facially weighted enumerations

Our first main result expresses the Ehrhart quasipolynomials of an inside-out polytope (P, ℋ) in terms of the combinatorics of ℋ; but its natural domain is far more general. We may take any discrete set D in ℝ^{d}, any bounded convex set C, and any hyperplane arrangement ℋ that is transverse to C: every flat u ∈ ℒ(ℋ) that intersects the topological closure C̄ also intersects C^{∘}, the relative interior of C, and C does not lie in any of the hyperplanes of ℋ. (The definition of transversality does not require C to be bounded or convex. A convenient sufficient condition for transversality is that C^{∘} ∩ ⋂ ℋ ≠ ∅ and C ⊈ ⋃ ℋ.)

We think of (C, ℋ) as having both an external boundary ∂C, the topological boundary of C, and an internal boundary C ∩ (⋃ ℋ), together constituting the complete boundary ∂(C, ℋ). The relative interior (C, ℋ)^{∘} is C^{∘} \ ⋃ ℋ. A region of (C, ℋ), or of ℋ in C, is one of the components of C \ ⋃ ℋ, or the closure of such a component. A vertex of (C, ℋ) is a vertex of any of its regions.

The multiplicity of x ∈ ℝ^{d} with respect to ℋ is

m_{ℋ} (x) := the number of closed regions of ℋ that contain x.

The multiplicity with respect to (C, ℋ) is

m_{C,ℋ} (x) := \begin{cases}the number of closed regions of ℋ in C that contain x, & if x ∈ C, \\ 0, & if x ∉ C. \end{cases}

This may not equal m_{ℋ} (x) for x ∈ C, unless one assumes transversality. The closed and open D-enumerators of (C, ℋ) are

E_{C,ℋ} (D) := ∑_{x∈D} m_{C,ℋ} (x)

and

E_{C,ℋ}^{∘} (D) := #(D ∩ C \ ⋃ ℋ).

Theorem 3.1. Let C be a full-dimensional, bounded, convex subset of ℝ^{d}, ℋ a hyperplane arrangement not containing the degenerate hyperplane, and D a discrete set in ℝ^{d}. Then

E_{C,ℋ}^{∘} (D) = ∑_{u∈ℒ(ℋ)} μ(ˆ0, u)#(D ∩ C ∩ u)  (3.1)

and if ℋ is transverse to C,

E_{C,ℋ} (D) = ∑_{u∈ℒ(ℋ)} |μ(ˆ0, u)|#(D ∩ C ∩ u),  (3.2)

where μ is the Möbius function of ℒ(ℋ).

Proof of Equation (3.1). We begin with the observation that, for any flat r of ℋ,

#(D ∩ C ∩ r) = ∑_{u∈ℒ:u≥r} E_{C∩u,ℋ^{u}}^{∘} (D).

The reason for this is that C ∩ r is the disjoint union of all the open faces of ℋ in C ∩ r, C ∩ u \ ⋃ ℋ^{u} is the disjoint union of the open faces of ℋ that span u, and counting points of D is an additive function on open faces (a valuation in technical language). By Möbius inversion,

E_{C∩r,ℋ^{r}}^{∘} (D) = ∑_{u∈ℒ:u≥r} μ(r, u)#(D ∩ C ∩ S).

Setting r = ˆ0 gives the desired formula unless ℋ contains the degenerate hyperplane. In that case, however, both sides of (3.1) equal zero. ■

The proof of the second equation depends on two lemmas about transversality and an algebraic expression for the multiplicity of a point.

Lemma 3.2. Let C be a convex set and ℋ a transverse hyperplane arrangement. If u is a flat of ℋ, then \overline{u ∩ C^{∘}} = u ∩ C̄.

Proof. We need to prove that every neighborhood of a point x ∈ u∩∂C intersects u∩C^{∘}. By transversality u intersects C^{∘}, say in a point y. Then the segment conv(x, y) lies in u ∩ C^{∘} except possibly for x. This implies our desideratum. ■

Lemma 3.3. Let C be a convex set and ℋ a transverse hyperplane arrangement. If F is a face of ℋ, then \overline{F ∩ C^{∘}} = F̄ ∩ C̄.

Proof. The question reduces to proving that \overline{F ∩ C^{∘}} ⊇ F̄ ∩ C̄ when F is an open face of ℋ. Take x ∈ (F̄ ∩ C̄) \ (F ∩ C^{∘}). Then x ∈ F (x) ∩ ∂C. By Lemma 3.2 with u = aff F (x), every neighborhood of x intersects u ∩ C^{∘}. Because F (x) is open in u, every small neighborhood of x in u is contained in F (x). Since F (x) ⊆ F̄, every small neighborhood of x in ℝ^{d} meets F ∩ C^{∘} and therefore x ∈ \overline{F ∩ C^{∘}}. ■

Lemma 3.4. The multiplicity of x ∈ ℝ^{d} with respect to a hyperplane arrangement ℋ is given by

m_{ℋ} (x) = (−1)^{codim s(x)}p_{ℋ(x)} (−1).

Proof. x belongs to the unique open face F (x), which is an open region of ℋ^{s(x)}. There is an obvious bijection between (closed) regions R of ℋ that contain F (x) and regions R′ of ℋ(x): R′ ↔ R if R′ ⊆ R. In fact, each region R′ contains s(x) and is dissected by ℋ \ ℋ(x) into regions of ℋ, of which one and only one contains x. Therefore, the number of regions of ℋ that contain x equals the number of regions of ℋ(x), which is (−1)^{codim s(x)}p_{ℋ(x)} (−1). ■

Lemma 3.5. Let C be a full-dimensional, bounded, convex subset of ℝ^{d} and ℋ a transverse hyperplane arrangement. The multiplicity of x ∈ ℝ^{d} with respect to C and ℋ is given by

m_{C,ℋ} (x) = \begin{cases}(−1)^{codim s(x)}p_{ℋ(x)} (−1) & if x ∈ C, \\ 0 & if x ∉ C. \end{cases}

Proof. We may assume x ∈ C. In relation to C, x lies in the open face F (x) ∩ C of ℋ in C. We must prove that every region R of ℋ that contains x corresponds to a region of ℋ in C, so that m_{C,ℋ} (x) = m_{ℋ} (x). This follows from Lemma 3.3 with F = R^{∘}: since x ∈ R ∩ C̄, R^{∘} ∩ C^{∘} is nonempty, so R ∩ C is full-dimensional. ■

Proof of Equation (3.2). We apply Lemma 3.5, the definition of the characteristic polynomial, and Rota’s sign theorem [24, Section 7, Theorem 4].

E_{C,ℋ} (D) = ∑_{x∈C∩D} |p_{ℋ(x)} (−1)|

= ∑_{x∈C∩D} ∑_{u≤s(x)} |μ(ˆ0, u)|

= ∑_{u∈ℒ}|μ(ˆ0, u)|#{x ∈ C ∩ D : s(x) ⊆ u}

= ∑_{u∈ℒ}|μ(ˆ0, u)|#(D ∩ C ∩ u).

■

There is also a proof of (3.2) by inversion. See Section 8.

4. In which we arrange Ehrhart theory with hyperplanes

We are interested in counting those points of a discrete lattice D that are contained in a D-fractional convex polytope but not in a hyperplane arrangement. A discrete lattice is a set of points in an affine space (such as ℤ^{d} in ℝ^{d}) that is locally finite and is invariant under any translation that carries some lattice point to another lattice point. (Any discrete lattice in ℝ^{d}, which is ℝ^{d} with coordinates, is a translate of a lattice group, which is a discrete lattice that contains the origin.) We call a polytope D-integral if its vertices all lie in D and D-fractional if the vertices lie in the contracted lattice t^{−1}D for some positive integer t. The denominator of P [11] is the smallest such t. (To define t^{−1}D here we assume coordinates chosen so that 0 ∈ D. Later, at Corollary 4.3, we deal with a more general situation.) According to Ehrhart [9, 10], if P is a closed, d-dimensional, D-fractional convex polytope and

E_{P} (t) := #(D ∩ tP) = #(P ∩ t^{−1}D),  (4.1)

then E_{P} is a quasipolynomial whose degree is d, whose period divides the denominator of P, and whose leading coefficient equals vol_{D} P, the volume of P normalized with respect to D (that is, we take the volume of a fundamental domain of D to be 1; in the case of the integer lattice ℤ^{d} this is the ordinary volume), and whose constant term, defined as E_{P} (0) even when E_{P} is not a true polynomial, equals one. Ehrhart [10] and Macdonald [20, Theorem (3.1)] proved this for the integer lattice; it follows in general because every discrete lattice is affinely equivalent to ℤ^{d}. Defining the Ehrhart quasipolynomial of any rational polytope P, not necessarily closed, by Equation (4.1), it applies to relatively open as well as closed polytopes, except that then the constant term is the combinatorial Euler characteristic of P. Ehrhart [10] then conjectured and he, Macdonald [21], and McMullen [22] proved the reciprocity law

E_{P^{∘}}(t) = (−1)^{dim P} E_{P} (−t).

This is ordinary Ehrhart theory.

Our theory begins with a rational, closed convex polytope P and an arrangement ℋ of rational hyperplanes that is transverse to P. Rationality means that the vertices of P are rational points and the hyperplanes in ℋ are specified by equations with rational coefficients. We call (P, ℋ) a rational inside-out polytope of dimension dim P. More generally we have any discrete lattice D, a closed D-fractional convex polytope P, and a D-fractional hyperplane arrangement ℋ (transverse to P): that is, each hyperplane in ℋ is spanned by the Dfractional points it contains. Then (P, ℋ) is a D-fractional inside-out polytope. The vertices of (P, ℋ) are all the intersection points in P formed by the hyperplanes of ℋ and the facets of P, including the vertices of P. The denominator of (P, ℋ) (with respect to the discrete lattice D) is the smallest positive integer t for which t^{−1}D contains every vertex of (P, ℋ). We call (P, ℋ) D-integral if all its vertices lie in D. We always assume that P is closed.

The Ehrhart quasipolynomials of (P, ℋ) (recall that we always assume P is closed) are the (closed) Ehrhart quasipolynomial,

E_{P,ℋ} (t) := E_{P,ℋ} (t^{−1}D) = ∑_{x∈t^{−1}D} m_{P,ℋ} (x),

and the open Ehrhart quasipolynomial,

E_{P,ℋ}^{∘} (t) := E_{P,ℋ}^{∘} (t^{−1}D) = #(t^{−1}D ∩ [P \ ⋃ ℋ]),

both defined for positive integers t in terms of the D-enumerators of Section 3 with D replaced by t^{−1}D. Thus if P is full-dimensional and R_{1}, …, R_{k} are the closed regions of (P, ℋ),

E_{P,ℋ} (t) = ∑_{i=1}^{k} E_{R_{i}}(t) and E_{P^{∘},ℋ}^{∘} (t) = ∑_{i=1}^{k} E_{R_{i}^{∘}}(t)  (4.2)

by the definition of multiplicity and ordinary Ehrhart quasipolynomials. We use the term “quasipolynomial” in anticipation of the theorem:

Theorem 4.1. If D is a full-dimensional discrete lattice and (P, ℋ) is a closed, fulldimensional, D-fractional inside-out polytope in ℝ^{d} such that ℋ does not contain the degenerate hyperplane, then E_{P,ℋ} (t) and E_{P^{∘},ℋ}^{∘} (t) are quasipolynomials in t, with period equal to a divisor of the denominator of (P, ℋ), with leading term c_{d}t^{d} where c_{d} = vol_{D} P, and with the constant term E_{P,ℋ} (0) equal to the number of regions of (P, ℋ). Furthermore,

E_{P^{∘},ℋ}^{∘} (t) = (−1)^{d}E_{P,ℋ} (−t).  (4.3)

Proof. By (4.2), standard Ehrhart theory, and the fact that a closed region has Euler characteristic 1. ■

The periodically varying quasiconstant term c_{0}(t) has no presently known interpretation, save at t ≡ 0.

One might use Theorem 4.1 to compute the number of regions of a hyperplane arrangement. Suppose, for instance, that ℋ has nonempty intersection and this intersection meets the interior of P. Then the constant term E_{P,ℋ} (0) equals the number of regions of ℋ. If one can evaluate E_{P,ℋ} (kp) (where p is the period) for enough values of k, one can deduce the constant term, thus the number of regions, by polynomial interpolation. Sometimes this is feasible, as in [4, Example 3.15].

It is easy to prove as well that E_{P,ℋ}^{∘} (t) and E_{P^{∘},ℋ} (t) are quasipolynomials in t with some of the same properties, e.g., the leading term, although we do not know they have the same period as each other or as E_{P,ℋ} (t).

The first theorem does not require transversality, but the next one does, in part.

Theorem 4.2. If D, P, and ℋ are as in Theorem 4.1, except that P need not be closed, then

E_{P,ℋ}^{∘} (t) = ∑_{u∈ℒ(ℋ)} μ(ˆ0, u)E_{P ∩u}(t),  (4.4)

and if ℋ is transverse to P,

E_{P,ℋ} (t) = ∑_{u∈ℒ(ℋ)} |μ(ˆ0, u)|E_{P ∩u}(t).  (4.5)

Proof. A special case of Theorem 3.1. ■

If it so happens that, as in the graph coloring examples, E_{P ∩u}(t) = f(t)^{dim u}, then the right side of (4.5) becomes (−1)^{d}p_{ℋ} (−f(t)) and that of (4.4) becomes p_{ℋ} (f(t)). For instance, f(t) may be t or t − 1.

One can potentially evaluate the inside-out Ehrhart quasipolynomial E_{P^{∘},ℋ}^{∘} in an example by counting lattice points for enough values of t and using polynomial interpolation. (This requires knowing an upper bound on the period, such as the denominator.) The number of values necessary is lessened if one knows something of the coefficients in advance. For example, the leading coefficient of every constituent of E_{P^{∘},ℋ}^{∘} is vol P; this is also the leading coefficient of the ordinary Ehrhart quasipolynomial E_{P^{∘}}, which can be interpolated from many fewer evaluations. By Theorem 4.2 one can simplify the computation further, even without evaluating the Möbius function, if one first calculates E_{P^{∘}}. Consider the second leading coefficients c_{d−1}(t) in E_{P^{∘},ℋ}^{∘} and c_{P,d−1}(t) in E_{P^{∘}}. By Theorem 4.2,

c_{d−1}(t) = c_{P,d−1}(t) − ∑_{\begin{matrix}u∈ℒ(ℋ) \\ codim u=1 \end{matrix}} vol(P ∩ u),  (4.6)

because μ(ˆ0, u) = −1. The sum is a constant, so if it is evaluated for one constituent of E_{P^{∘},ℋ}^{∘} it is known for all; whence one needs fewer evaluations to determine the coefficients of all the constituents of E_{P^{∘},ℋ}^{∘} . This idea sees a practical application in [4, Example 3.17].

Theorem 4.2 gives a second proof of inside-out Ehrhart reciprocity, Equation (4.3). Apply ordinary reciprocity in flats and Rota’s sign theorem:

E_{P^{∘},ℋ}^{∘} (t) = ∑_{u∈ℒ}μ(ˆ0, u)E_{P^{∘}∩u}(t)

= ∑_{u∈ℒ}μ(ˆ0, u)(−1)^{dim u}E_{P ∩u}(−t)

= (−1)^{d} ∑_{u∈ℒ}|μ(ˆ0, u)|E_{P ∩u}(−t)

= (−1)^{d}E_{P,ℋ} (−t). ■

Often the polytope is not full-dimensional; its affine span, aff P, might not even intersect the discrete lattice. Suppose, then, that D is a discrete lattice in ℝ^{d} and s is any affine subspace. The period p(s) of s with respect to D is the smallest positive integer p for which p^{−1}D meets s. Then Theorem 4.1 implies

Corollary 4.3. Let D be a discrete lattice in ℝ^{d}, P a D-fractional convex polytope, and ℋ a hyperplane arrangement in s := aff P that does not contain the degenerate hyperplane. Then E_{P,ℋ} (t) and E_{P^{∘},ℋ}^{∘} (t) are quasipolynomials in t that satisfy the reciprocity law E_{P^{∘},ℋ}^{∘} (t) = (−1)^{dim s}E_{P,ℋ} (−t). Their period is a multiple of p(s) and a divisor of the denominator of (P, ℋ). If t ≡ 0 mod p(s), the leading term of E_{P,ℋ} (t) is (vol_{p(s)^{−1}D} P)t^{dim s} and its constant term is the number of regions of (P, ℋ); but if t ≢ 0 mod p(s), then E_{P,ℋ} (t) = E_{P^{∘},ℋ}^{∘} (t) = 0. ■

The period’s being greater than one suggests that we should renormalize, multiplying s, P, and ℋ by p(s). This divides both the denominator of the inside-out polytope and the period of the Ehrhart quasipolynomials by p(s) and eliminates the zero constituents of the quasipolynomials. The 3 × 3 magic squares are a perfect example [4, Section 3.2].

Usually ℋ will be induced by an arrangement ℋ_{0} in ℝ^{d}. It is easy to see that ℋ is transverse to P if and only if ℋ_{0} is.

5. In which we color graphs and signed graphs

The best way to approach graph coloring geometrically is not precisely the one sketched in the introduction. Especially with signed graphs we do better to make two subtle changes: for one, rather than inflating the fundamental polytope we should contract the lattice (which also suits unsigned graphs perfectly well); the other is a translation that we explain in our treatment of signed graphs.

We take up unsigned graphs first. Our purpose is to see how much information we can extract purely from inside-out Ehrhart theory; let the reader therefore forget everything he or she knows about the chromatic polynomial except the definition:

χ_{Γ}(c) := the number of proper c-colorings of Γ.

An ordinary graph is a graph whose edges are links (with two distinct endpoints) and loops (with two coinciding endpoints); multiple edges are permitted. We treat, always, only finite graphs. The order is the number of nodes; we write n for the order of Γ.

Theorem 5.1. Let Γ be an ordinary graph and let P = [0, 1]^{n}. The closed and open Ehrhart quasipolynomials of (P, ℋ[Γ]) satisfy

(−1)^{n}E_{P,ℋ[Γ]} (−t) = E_{P^{∘},ℋ[Γ]}^{∘} (t) = χ_{Γ}(t − 1).

Proof. In t^{−1}ℤ^{n} the points that are counted by E_{P^{∘},ℋ[Γ]}^{∘} (t) are those of (t^{−1}{1, 2, …, t − 1})^{n} that do not lie in any forbidden hyperplane. The number of such points is the number of proper t − 1-colorings of Γ. ■

Corollary 5.2 (Birkhoff [5] for maps, Whitney [33] for graphs). For an ordinary graph Γ with no loops, χ_{Γ} is a monic polynomial of degree n. If Γ has a loop, χ_{Γ} = 0.

Proof. Since P is full-dimensional in ℝ^{n} and has volume 1, the leading term of χ_{Γ} is 1x^{n} by Ehrhart theory. It remains to prove that (P, ℋ[Γ]) has denominator 1, or in other words that (P, ℋ[Γ]) has integer vertices. This is the next lemma. ■

Lemma 5.3. If Γ is an ordinary graph, (P, ℋ[Γ]) has integer vertices.

Proof. The proof is simple; we supply it because the lemma is so important. Because, as is well known, ℋ[Γ] is a hyperplanar representation of the graphic matroid G(Γ), the flats of ℋ[Γ] correspond to closed subgraphs of Γ, i.e., to partitions π of V into blocks that induce connected subgraphs. The flat s(π) corresponding to π is described by x_{i} = x_{j} if i and j belong to the same block of π (we write i ∼_{π} j). A vertex of (P, ℋ[Γ]) is determined by a flat s(π) of dimension k, say, together with k facet hyperplanes of P that have the form x_{i} = a_{i} ∈ {0, 1}. Obviously, such points are integral. ■

Theorem 5.4. For an ordinary graph Γ, χ_{Γ}(c) = p_{ℋ[Γ]} (c).

Proof. We apply Theorem 4.2. It is easy to see that E_{P^{∘}∩u}(t) = (t − 1)^{dim u}. Therefore, E_{P^{∘},ℋ[Γ]}^{∘} (t) = p_{ℋ[Γ]} (t − 1). This equals χ_{Γ}(t − 1) by Theorem 5.1. ■

Given an orientation α of Γ and a c-coloring x : V → [c], Stanley calls them compatible if x_{j} ≥ x_{i} whenever there is a Γ-edge oriented from i to j, and proper if x_{j} > x_{i} under the same condition [27]. An orientation is acyclic if it has no directed cycles. From Theorem 5.1 we derive a more unified version of Stanley’s second proof of his famous result.

Corollary 5.5 (Stanley [27]). The number of pairs (α, x) consisting of an acyclic orientation of an ordinary graph Γ and a compatible c-coloring equals (−1)^{n}χ_{Γ}(−c). In particular, (−1)^{n}χ_{Γ}(−1) = the number of acyclic orientations of Γ.

Proof. From Theorem 5.1,

E_{P,ℋ[Γ]} (t) = (−1)^{n}χ_{Γ}(−(t + 1)).

What E_{P,ℋ[Γ]} (t) counts is the number of pairs (x, R) where x is a coloring with color set {0, 1, …, t}, R is a closed region of ℋ[Γ], and x ∈ R. Greene observed that regions R correspond with acyclic orientations α in the following way: R^{∘} is determined by converting each equation x_{i} = x_{j} corresponding to an edge of Γ into an inequality x_{i} < x_{j}; then in α the edge ij is directed from i to j. (See [13] or [15, Section 7].) The orientation is acyclic because R^{∘} ≠ ∅. Thus x is compatible with α if and only if x ∈ R. The final assertion is an instance of the evaluation E(0) in Theorem 4.1. ■

This proof generalizes Greene’s geometrical approach to counting acyclic orientations (that is, the case c = 1); see [13] or [15, Section 7].

Now we turn to signed graphs. To repeat, a signed graph Σ is an ordinary graph (loops and multiple edges being allowed) in which each edge is labelled + or −. A c-coloring [36] of a signed graph with node set V = [n] is a function

x : V → {−c, −(c − 1), …, 0, …, c − 1, c};

we say x is proper if it has the property that, when there is an edge ij with sign ε, then x_{j} ≠ εx_{i}. Geometrically, x ∈ ({−c, −(c − 1), …, c})^{n} \ ⋃ ℋ[Σ] where

ℋ[Σ] := {h_{ij}^{ε} : Σ has an edge ij with sign ε}

and h_{ij}^{ε} is the hyperplane x_{j} = εx_{i}. The function

χ_{Σ}(2c + 1) := the number of proper c-colorings of Σ

is a polynomial, called the chromatic polynomial of Σ [36]. We see that χ_{Σ}(2c + 1) = E_{P^{∘},ℋ[Σ]}^{∘} (c + 1), the number of lattice points that lie in (c + 1)P^{∘} (where now P := [−1, 1]^{n}) but not in any of the hyperplanes of ℋ[Σ]. (See Figure 2.) Furthermore, the regions of ℋ[Σ] are known to correspond to the acyclic orientations of Σ [37] and the regions that contain a coloring x correspond to the acyclic orientations that are compatible with x [36]. Thus E_{P,ℋ[Σ]} (c) is the number of pairs consisting of a coloring and a compatible acyclic orientation, which is known to equal (−1)^{n}χ_{Σ}(−(2c + 1)) [36]. Signed graphs have a second chromatic polynomial: the zero-free chromatic polynomial

χ_{Σ}^{∗}(2c) := the number of proper c-colorings x : V → ±[c],

that is, it counts colorings not taking the value 0. This is obviously also an inside-out Ehrhart polynomial, but it is not obvious that χ_{Σ} and χ_{Σ}^{∗} are closely related. In fact, they are the two constituent polynomials of a single Ehrhart quasipolynomial.

In order to see how this is so, we must realign and rescale the whole picture so that the fundamental polytope is P = [0, 1]^{n} (just as with unsigned graph coloring) and the hyperplanes center on the point \frac{1}{2}1, where 1 := (1, 1, …, 1). (See Figure 3. This enables us to unify unsigned and signed graph coloring and, in addition, the two kinds of signed chromatic polynomial.) We replace ℋ[Σ] by its translate ℋ′′[Σ] = ℋ[Σ] + \frac{1}{2}1; that is, we add (\frac{1}{2}, \frac{1}{2}, …, \frac{1}{2}) to every hyperplane. (Translating the hyperplane of a positive edge leaves it unchanged; thus, ℋ′′[Γ] = ℋ[Γ], which is why translation was unnecessary for Theorem 5.1.) A signed graph, defined in complete generality, is Σ = (Γ, σ) where Γ is a graph that may have, besides links and loops, also halfedges (with only one endpoint) and loose edges (no endpoints), and σ is a signature defined only on links and loops (which are called ordinary edges). The hyperplane corresponding to a halfedge at node i is x_{i} = 0, the same as for a negative loop at i, and the “hyperplane” that corresponds to a loose edge is the degenerate hyperplane 0 = 0, just as for a positive loop. The order of a signed graph is the number of nodes, written n.

Theorem 5.6. Let Σ be a signed graph and let P = [0, 1]^{n}. The Ehrhart quasipolynomial of (P, ℋ′′[Σ]) satisfies

(−1)^{n}E_{P,ℋ′′[Σ]} (−t) = E_{P^{∘},ℋ′′[Σ]}^{∘} (t) = \begin{cases}χ_{Σ}(t − 1) & if t is even, \\ χ_{Σ}^{∗}(t − 1) & if t is odd. \end{cases}

PSfrag replacements ±K_{2}

Figure 2. Illustrating for k = 8: On the left, the lattice points in (k + 1)[−1, 1]^{2} that k-color the signed graph ±K_{2}. On the right, the lattice points that k-color it without 0.

Proof. An easy way to see the correctness of the expression for E^{∘} in terms of χ_{Σ} and χ_{Σ}^{∗} is to translate the center of P to the origin and dilate by t. Then P becomes P̃ = [−\frac{t}{2}, \frac{t}{2}]^{n} and ℋ′′[Σ] becomes ℋ[Σ]. What happens to t^{−1}ℤ^{n} depends on the parity of t. If t is even, t^{−1}ℤ^{n} becomes ℤ^{n} and, much as in the introduction and the proof of Theorem 5.1, E_{P^{∘},ℋ[Σ]}^{∘} (t) = χ_{Σ}(2c + 1) with c = \frac{t}{2} − 1. When t is odd, t^{−1}ℤ^{n} is transformed to ℤ^{n} + \frac{1}{2}1, in which no vector has an integral entry; the number of points of this lattice in P̃^{∘} and not in ⋃ ℋ[Σ] equals χ_{Σ}^{∗}(t) if we regard the latter as counting colorings with color set \frac{1}{2}\{±1, ±3, …, ±(t − 2)\}, which is an acceptable color set because it consists of \frac{1}{2}(t − 1) colors, each with both signs, and does not contain 0. ■

The effect on the geometry of the parity of t is what prevents us from conveniently stating the entire result in terms of ℋ[Σ]. See Theorem 5.10.

Corollary 5.7 (Zaslavsky [36, Theorem 2.2]). For a signed graph with no positive loops or loose edges, χ_{Σ} and χ_{Σ}^{∗} are monic polynomials of degree n. If Σ has a positive loop or a loose edge, χ_{Σ} = χ_{Σ}^{∗} = 0.

Proof. The leading terms are 1x^{n} because P is n-dimensional with volume 1. Polynomiality is a consequence of the next lemma, by which (P, ℋ′′[Σ]) has denominator 1 or 2. ■

Lemma 5.8. If Σ is a signed graph, (P, ℋ′′[Σ]) has half-integral vertices.

Proof. The flats of ℋ[Σ] correspond to partial signed partitions (π, σ) of V. (This description is based on [8, Section 3], interpreted in light of [35, Theorems 5.1(b) and 8.1].) A partial partition is a partition of a subset of V. A signed partition is a partition π along with, for each block B, a pair [σ] = {σ, −σ} where σ : B → {+1, −1} is a signature on B. In the PSfrag replacements

±K_{2}^{∘}

Figure 3. Illustrating for k = 8: On the left, the \frac{1}{2(k+1)}-lattice points in [0, 1]^{2} that k-color the signed graph ±K_{2}^{∘}, with shifted hyperplanes. On the right, the \frac{1}{(2k+1)}-lattice points that k-color it without 0.

correspondence (π, σ) ↦ s, the flat s has the equations x_{i} = 0 for i ∉ ⋃ π and, for each block B ∈ π, σ_{i}x_{i} = σ_{j}x_{j} if i, j ∈ B. (In general not all subspaces of this form are flats of ℋ[Σ], the exception being the complete signed graph ±K_{n}^{•} [35].)

A flat of ℋ′′[Σ] therefore has the equations x_{i} = \frac{1}{2} if i ∉ ⋃ π and σ_{j}x_{j} = σ_{i}x_{i} + \frac{1}{2}(σ_{j} −σ_{i}) if i ∼_{π} j. The constant term in the latter is integral. A vertex of (P, ℋ′′[Σ]) is described by n−k equations of these kinds, determining a k-flat s, and k equations of the form x_{i} = a_{i} ∈ {0, 1}; clearly, then, the vertex has half-integral coordinates. ■

We say more about half integrality in relation to the incidence matrix in [3].

There is a stronger conclusion if Σ is balanced, that is, it has no halfedges and no circles with negative sign product. In that case Σ is obtained from an all-positive graph by reversing the signs of all edges of a cutset, an operation called switching. (This was proved by König [19, Theorem X.10]. See [35, Corollary 3.3] for more detail.) We represent switching by a function η : V → {+, −} such that the cutset consists of all edges whose endpoints have opposite signs. When Σ is balanced, obtained by switching +Γ (where Γ is the underlying graph of Σ), an edge has sign σ(ij) = η(i)η(j) and a flat of ℋ[Σ] is specified by a partition π of V and equations η(i)x_{i} = η(j)x_{j} when i ∼_{π} j.

Corollary 5.9 (Zaslavsky [36, Section 2.1]). For a balanced signed graph, χ_{Σ} = χ_{Σ}^{∗}.

Proof. Σ is obtained through switching +Γ by a switching function η. The effect of η on ℋ′′[Σ] is to reverse coordinates: x_{i} → 1 − x_{i} if η(i) = −, but x_{i} → x_{i} if η(i) = +. We apply η to P and t^{−1}ℤ^{n} in the same way so that switching does not alter the Ehrhart quasipolynomials. Therefore, we may apply Lemma 5.3 to (P, ℋ′′[Σ]). ■

The switching equivalence of a balanced signed graph to an all-positive graph demonstrates that (P, ℋ′′[Σ]) then has integral vertices. Another proof is by observing that its equations are totally unimodular, that is, every subdeterminant is 0 or ±1, as shown in [17, Theorem 1] and later in [35, Proposition 8A.5]. We omit the details.

Corollary 5.9 is not the whole story. Going beyond Ehrhart theory, one can prove that χ_{Σ} ≠ χ_{Σ}^{∗} when Σ is unbalanced, by comparing the lattice Lat G(Σ) of closed subgraphs of Σ to the semilattice Lat^{b} Σ of closed, balanced subgraphs [35, Section 5]. They are equal if and only if Σ is balanced, and by [36, Theorem 2.4] χ_{Σ} = χ_{Σ}^{∗} if and only if they are equal. Expressed in Ehrhartian terms: for a signed-graphic inside-out polytope the period of the Ehrhart quasipolynomial is equal to the denominator of (P, ℋ) (which is noteworthy because such an equation does not hold true in general).

The relationship between the hyperplane arrangement and the chromatic polynomials of a signed graph is rather complicated. For a flat u of ℋ[Σ] let Σ(u) be the subgraph consisting of the edges whose hyperplanes contain u.

Theorem 5.10 (Zaslavsky [36, Theorem 2.4]). For a signed graph Σ,

χ_{Σ}(c) = p_{ℋ[Σ]} (c).

and

χ_{Σ}^{∗}(c) = ∑_{u∈ℒ(ℋ) Σ(u) is balanced} μ(ˆ0, u)c^{dim u}.

Proof. We apply Theorem 4.2 again. Assume t is even. Then \frac{1}{2}1, which belongs to every flat of ℋ′′[Σ], is one of the coloring points, so (as one can easily see) every E_{P^{∘}∩u}(t) = (t−1)^{dim u}. Therefore, E_{P^{∘},ℋ′′[Σ]}^{∘} (t) = p_{ℋ′′[Σ]} (t − 1). This equals χ_{Σ}(t − 1) by Theorem 5.6.

If, however, t is odd there are two kinds of flats. Any flat that lies in a hyperplane x_{i} = \frac{1}{2} contains no coloring points at all. One can see from the proof of Lemma 5.8 and the fact that a flat is balanced if and only if its signed partial partition is a partition (that is, ⋃ π = V) that these are precisely the flats that correspond to unbalanced subgraphs. These flats therefore drop out of the sum in (4.4). The other flats, which correspond to balanced subgraphs, behave as in the even case. ■

The signed-graphic generalization of Stanley’s theorem, Corollary 5.5, is also a consequence of Ehrhart theory.

Corollary 5.11 ([36, Theorem 3.5]). The number of compatible pairs (α, x) consisting of an acyclic orientation α and a c-coloring of a signed graph Σ is equal to (−1)^{n}χ_{Σ}(−(2c + 1)). The number in which x is zero-free equals (−1)^{n}χ_{Σ}^{∗}(−2c). In particular, (−1)^{n}χ_{Σ}(−1) = the number of acyclic orientations of Σ.

Sketch of Proof. We omit the details of proof because they are as in our proof of Stanley’s theorem. We omit the definitions because they are lengthy. Acyclic orientations and compatible pairs are defined in [36, Section 3]. Acyclic orientations are defined in [37] and their correspondence to regions of ℋ[Σ] is proved in [37, Theorem 4.4]. ■

Problem 5.12. A combinatorial interpretation of (−1)^{n}χ_{Σ}^{∗}(−1) would be a valuable contribution, since it would interpret the quasiconstant term c_{0}(1) of the t ≡ 1 polynomial.

6. In which we become antimagic

The general antimagic picture starts with homogeneous, rational linear forms f_{1}, …, f_{m} ∈ (ℝ^{d})^{∗}, which may be the line sums of a covering clutter. We want to count integer points x, drawn from a bounded subset of ℤ^{d} which we take to be the set of integral points in [0, t]^{d} or (0, t)^{d}, such that

f_{j}(x) ≠ f_{k}(x) if j ≠ k.

As we mentioned in the introduction, we may or may not require that the coordinate values of a point be all distinct; thus we have strongly or weakly antimagic labellings of [d]. Let us therefore define, given the forms f_{1}, …, f_{m}, the weak antimagic enumerator

A^{∘}(t) := the number of integer points x ∈ (0, t)^{d} such that all f_{j}(x) are distinct, and the strong antimagic enumerator A^{∗}^{∘}(t) := the number of such points x in which all entries x_{i} are also distinct. These are the open Ehrhart polynomials of inside-out polytopes with

P = [0, 1]^{d}

but with hyperplane arrangements of a new kind, as we now explain.

We want to think of the forms as a single function f = (f_{1}, …, f_{m}) : ℝ^{d} → ℝ^{m}. The antimagic property is the requirement that f(x) ∉ ⋃ ℋ[K_{m}] in ℝ^{m}. (K_{m} denotes the complete graph on m nodes.) Let us imagine that f is any linear transformation ℝ^{d} → ℝ^{m} and that in ℝ^{m} we have a hyperplane h that is the kernel of a homogeneous (or affine) linear functional φ. Then φf is a homogeneous (or affine) linear functional on ℝ^{d} defining a hyperplane h^{♯}, the pullback of h. Applying this construction to all the hyperplanes of an arrangement ℋ in ℝ^{m} we get the pullback ℋ^{♯} in ℝ^{d}. Note that ℋ^{♯} might include the degenerate hyperplane ℝ^{d}, even if ℋ does not, since h^{♯} is degenerate if and only if h ⊇ Im f. The antimagic property of x is now the statement that x ∈ ℝ^{d} \ ⋃ ℋ[K_{m}]^{♯}. The entries of x are distinct if x ∉ ⋃ ℋ[K_{d}]. Thus, the hyperplane arrangement for A^{∘} is ℋ[K_{m}]^{♯} and for A^{∗}^{∘} it is ℋ := ℋ[K_{m}]^{♯} ∪ ℋ[K_{d}]. To complete the preparation for our antimagic theorem, recall the multiplicity of x with respect to ℋ[K_{m}]^{♯} or ℋ from Section 3, here written m(x) or m^{∗}(x) for simplicity. We define

A(t) := the sum of multiplicities m(x) of all integer points x ∈ [0, t]^{d}, and

A^{∗}(t) := the sum of multiplicities m^{∗}(x) of all integer points x ∈ [0, t]^{d}.

Theorem 6.1. Given homogeneous rational linear forms f_{1}, …, f_{m} : ℝ^{d} → ℝ, no two equal, the antimagic enumerators A^{∗}(t), A^{∗}^{∘}(t), A(t), and A^{∘}(t) are monic quasipolynomials in t that satisfy the reciprocity laws

A^{∗}(t) = (−1)^{d}A^{∗}^{∘}(−t) and A(t) = (−1)^{d}A^{∘}(−t).

Proof. From Theorem 4.1. Distinctness of the forms ensures that antimagic points x do exist so that the enumerators are not identically zero. ■

Problem 6.2. Is there a combinatorial interpretation of the regions? What is the intersectionlattice structure of ℋ[K_{m}]^{♯}? It seems improbable that any simple description could be given for arbitrary forms, but maybe there is one in a special case like that of antimagic graphs.

The intersection lattices of ℋ[K_{m}]^{♯} and ℋ are implicated in the next theorem.

Lemma 6.3. If all forms are distinct but have equal weight, then ℋ[K_{m}]^{♯} and ℋ are transverse to [0, 1]^{d}.

Proof. If all forms have equal weight, then \frac{1}{2}1 ∈ ⋂ ℋ. Therefore, any flat of ℋ or ℋ[K_{m}]^{♯} intersects P^{∘} = (0, 1)^{d}. ■

Theorem 6.4. If all forms are different but have equal weight, then

A^{∗}^{∘}(t) = ∑_{u∈ℒ(ℋ)} μ(ˆ0, u)E_{(0,1)^{d}∩u}(t) ,
A^{∗}(t) = ∑_{u∈ℒ(ℋ)} |μ(ˆ0, u)|E_{[0,1]^{d}∩u}(t) ,

where μ is the Möbius function of ℒ(ℋ), and there are similar formulas for A^{∘} and A with ℋ[K_{m}]^{♯} replacing ℋ.

Proof. By Theorem 4.2 and Lemma 6.3. ■

The main examples are particular cases of antimagic labelling of covering clutters, especially ones from graphs.

Example 6.5 (Antimagic graphs). The edges of a simple graph are labelled by integers and we want the sum of all labels incident to a node to be different for every node. The covering clutter here has for points the edges and for lines the sets of all edges incident to each node. These examples are the most studied, normally with the standard label set [q] if there are q edges (no doubt because the existence question is otherwise trivial). The one case that must be excluded because it has no antimagic labellings is the graph with just two nodes and one edge. (See [7] for a proof. [7] calls our strong antimagic “weak” because it reserves the term “strong” for use of the standard label set [q].)

One could generalize to bidirected graphs, although we are not aware of any such work. In the form associated with a node, the labels on the edges are added if the edge is directed into the node and subtracted if not. If the graph is directed these forms have weight zero so Theorem 6.4 does apply.

A dual example has also been studied.

Example 6.6 (Node antimagic). Integers are assigned to the nodes and an edge receives the sum of its endpoint values; one wants every edge to have a different label. The forms all have weight two so Theorem 6.4 applies. In the literature normally the label set is the standard one, [n] where there are n nodes; see [26] where the notion is generalized to hypergraphs.

In the bidirected graph generalization the rule for addition and subtraction is the same as in the preceding example. For a directed graph, therefore, the differences of the endpoint labels are what should be distinct. (If we could take the absolute values of these differences we would be close to the famous problem of graceful labelling [16], but we do not see how to do that within our framework.)

Combining the two labellings of a graph we have

Example 6.7 (Total graphical antimagic). In a total labelling both nodes and edges are labelled. For antimagic one wants all node and edge sums to be different. See [12, Section 5.4].

The bidirected generalization is as in the preceding examples.

Example 6.8 (Squares antimagic, semi-antimagic, and antipandiagonal, hypercubes, etc.). These are just like magic, semimagic, and pandiagonal magic squares, except, of course, that the line sums must all be different. There is a scattered literature on antimagic squares, triangles, pentagrams, etc., in which it is generally assumed that the labels are consecutive. (See Swetz [31, p. 130] on antimagic squares. What we call a pandiagonal antimagic square was introduced under the name “heterosquare” by Duncan, according to [31, p. 131].) One could extend these notions to affine and projective planes, k-nets, and hypercubes but we do not know of any such work.

Our results will also apply if one imposes symmetry on squares (or hypercubes). By this we mean that the sum of a centrally symmetric pair of numbers is constant. Our treatment of symmetric magic squares in [4] shows how one handles symmetry geometrically.

Example 6.9 (Small antimagic). We take a look at 2 × 2 semi-antimagic and antimagic squares.

First, semi-antimagic; that is, we require each row and column sum to be different. (This is the same as antimagic edge labelling of K_{2,2}.) By inspecting the equations of the hyperplanes and facets, we conclude that the vertices of (P, ℋ) for weak antimagic are vertices of P; thus we expect a monic polynomial and indeed

A^{∘}(t) = t^{4} − \frac{22}{3}t^{3} + 19t^{2} − \frac{62}{3}t + 8 = \frac{(t − 1)(t − 2)(t − 3)(3t − 4)}{3}.

The vertices for strong semi-antimagic, however, are half integral; thus we expect, and obtain, a monic quasipolynomial of period 2:

A^{∗}^{∘}(t) = \begin{cases}t^{4} − \frac{34}{3}t^{3} + 45t^{2} − \frac{218}{3}t + 38 \\ = \frac{(t−1)(t−3)(3t^{2}−22t+38)}{3} & if t is odd, \\ t^{4} − \frac{34}{3}t^{3} + 45t^{2} − \frac{218}{3}t + 40 \\ = \frac{(t−2)(t−4)(3t^{2}−16t+15)}{3} & if t is even. \end{cases}

Now, antimagic. The six required inequalities imply that all entries differ. The vertices are half integral. The enumerators are

A^{∘}(t) = A^{∗}^{∘}(t) = \begin{cases}t^{4} − 12t^{3} + 50t^{2} − 84t + 45 \\ = (t − 1)(t − 5)(t − 3)^{2} & if t is odd, \\ t^{4} − 12t^{3} + 50t^{2} − 84t + 48 \\ = (t − 2)(t − 4)(t^{2} − 6t + 6) & if t is even. \end{cases}

To conclude we mention that the theorems apply perfectly well to limited antimagic, where only some pairs of form values need be distinct, by replacing ℋ[K_{m}] with a subgraphic arrangement ℋ[Γ′] where Γ′ ⊆ K_{m}, and to partially distinct values, ℋ[K_{d}] being replaced by ℋ[Γ] for Γ ⊆ K_{d}. Moreover, one can treat negative point values, either |x_{i}| < t or 0 < |x_{i}| < t, by taking the polytope [−1, 1]^{d} and a suitable hyperplane arrangement, but the same theorems will not hold exactly since the quasipolynomials are not monic.

7. In which subspace arrangements put in their customary appearance

An arrangement of subspaces in ℝ^{d} is an arbitrary finite set 𝒜 of (affine) subspaces. (We assume all the subspaces are proper.) We wish to generalize our results to a polytope with a subspace arrangement, along the lines taken by Blass and Sagan [6] for graph coloring. This is possible in part. For instance, we can define the “multiplicity” of a point with respect to 𝒜, but only algebraically; it need not count anything, in fact it could be negative.

To begin with we take the situation of Section 3 in which C is a bounded convex set, D is a discrete set, and 𝒜 is an arrangement, now a subspace arrangement, that is transverse to C. We can take over most of the definitions from Sections 1–3 simply by changing ℋ to 𝒜. For one example, the open D-enumerator of (C, 𝒜) is

E_{C,𝒜}^{∘} (D) := #(D ∩ C \ ⋃ 𝒜).

There are some complications, however. The semilattice ℒ(𝒜), still partially ordered by reverse inclusion, is not necessarily geometric or ranked; instead it is extrinsically graded by the rank function

ρ(u) = codim u

and the total rank ρ(ℒ) = d, so that u has extrinsic corank ρ(ℒ) − ρ(u) = dim u. The notion of extrinsic grading, without a particular name, is common in writings on subspace arrangements.) The multiplicity of x ∈ ℝ^{d} with respect to C and 𝒜 is

m_{C,𝒜} (x) := \begin{cases}(−1)^{d}p_{𝒜(x)} (−1) = ∑_{u∈ℒ(𝒜):x∈u} μ(ˆ0, u)(−1)^{ρ(u)} & if x ∈ C, \\ 0 & if x ∉ C. \end{cases}

Lemma 3.5 ensures that this agrees with the definition for hyperplane arrangements, in Section 3. Now we can define the closed D-enumerator of (C, 𝒜) as before:

E_{C,𝒜} (D) := ∑_{x∈D} m_{C,𝒜} (x).

Theorem 7.1. Let C be a bounded, convex subset of ℝ^{d}, 𝒜 a subspace arrangement that is transverse to C, and D a discrete set in ℝ^{d}. Then

E_{C,𝒜} (D) = ∑_{u∈ℒ(𝒜)} μ(ˆ0, u)(−1)^{codim u}#(D ∩ C ∩ u)

and

E_{C,𝒜}^{∘} (D) = ∑_{u∈ℒ(𝒜)} μ(ˆ0, u)#(D ∩ C ∩ u).

Proof. That of Theorem 3.1, including Lemmas 3.2 and 3.3, goes through with obvious modifications and the understanding that an “open face” must be interpreted as a connected component of u \ ⋃ 𝒜^{u} but may not be simply connected, much less a cell. ■

For the main result about subspace arrangements we adapt the notation of Section 4, in particular the closed and open Ehrhart functions,

E_{P,𝒜} (t) := E_{P,𝒜} (t^{−1}D) = ∑_{x∈t^{−1}D} m_{P,𝒜} (x)

and

E_{P,𝒜}^{∘} (t) := E_{P,𝒜}^{∘} (t^{−1}D) = #(t^{−1}D ∩ [P \ ⋃ 𝒜]).

Theorem 7.2. If D is a discrete lattice in ℝ^{d}, P is a full-dimensional D-fractional convex polytope, and 𝒜 is a D-fractional subspace arrangement, then E_{P,𝒜} (t) and E_{P,𝒜}^{∘} (t) are quasipolynomials in t, each with period equal to a divisor of the D-denominator of (P, 𝒜) and with leading term (vol_{P} D)t^{d}. We have

E_{P^{∘},𝒜}^{∘} (t) = (−1)^{d}E_{P̄,𝒜} (−t).  (7.1)

Furthermore,

E_{P,𝒜} (t) = ∑_{u∈ℒ(𝒜)} μ(ˆ0, u)(−1)^{codim u}E_{P ∩u}(t)  (7.2)

and

E_{P,𝒜}^{∘} (t) = ∑_{u∈ℒ(𝒜)} μ(ˆ0, u)E_{P ∩u}(t)  (7.3)

Proof. The two latter equations are special cases of Theorem 7.1. The reciprocity law (7.1) follows from (7.2), (7.3), and standard Ehrhart reciprocity. ■

Problem 7.3. The constant term E(0) does not seem to have an obvious combinatorial interpretation except in special cases, as for instance if the arrangement leaves P connected, when E(0) = ε(P) as in ordinary Ehrhart theory.

8. In which we prove a general valuation formula

A normalized valuation on the faces of a hyperplane arrangement is a function v on finite unions of open faces, with values in an abelian group, such that v(A ∪ B) + v(A ∩ B) = v(A) + v(B) for any two such unions, or more simply

v(F_{1} ∪ ⋯ ∪ F_{k}) = v(F_{1}) + ⋯ + v(F_{k})

for distinct open faces F_{1}, …, F_{k}, and also

v(∅) = 0

(the normalization). For example, if D_{0} is a finite subset of ℝ^{d}, v(F) = #(D_{0} ∩ F) is a valuation. Specializing further, if D is a discrete set and C is a bounded convex set, then v(F) = #(D ∩ C ∩ F) is a valuation. For a flat u of ℋ, set

E_{v}(u) = ∑_{R} v(R)

summed over closed regions R of ℋ^{u}. If v(F) = #(D ∩ C ∩ F), and ℋ is transverse to C, this is simply E_{C∩u,ℋ^{u}} (D).

Theorem 8.1. For u ∈ ℒ(ℋ) and v a normalized valuation on the faces of ℋ,

E_{v}(u) = ∑_{s∈ℒ:s≥u} |μ(s, u)|v(s).

Equation (3.2) is a special case. What is different about this theorem compared to Theorem 3.1, besides its general statement, is the proof by Möbius inversion. The proof is more complicated, but we think it is interesting.

Theorem 8.1 can be interpreted in terms of the Möbius algebra of ℒ(ℋ). The Möbius algebra M(L) of a poset L, introduced by Solomon [25] and developed by Greene [14], is the algebra (over any nice ring) generated by the elements of L as orthogonal idempotents. For u ∈ L we define û = ∑_{s≥u} μ(u, s)s. (Technically, this defines the Möbius algebra of the dual poset L^{∗}; but that is a difference without a difference.) Let ε denote the combinatorial Euler characteristic, ε(u) = (−1)^{dim u}, and let εf denote the pointwise product with a function f. A function defined on ℒ(ℋ) naturally extends by linearity to the Möbius algebra of ℒ(ℋ). Theorem 8.1 says that, if v is a normalized valuation on ℱ(ℋ), extended in the obvious way to ℒ(ℋ) and then to the Möbius algebra, then εE_{v}(u) = εv(û).

Proof. In effect, we use Möbius inversion twice.

The first time is in the semilattice of faces of ℋ,

ℱ(ℋ) = {F : F is an open face of ℋ}

ordered by inclusion of the closures. The maximal elements of ℱ(ℋ) are the open regions; let ℛ(ℋ) be the set of open regions. We show that

(−1)^{dim u}v(u) = ∑_{s∈ℒ:s≥u}(−1)^{dim s}E_{v}(s)  for u ∈ ℒ(ℋ).  (8.1)

Multiplying by (−1)^{dim u}, the left side equals

∑_{F ∈ℱ(ℋ^{u})} v(F).  (8.2)

The right side equals

∑_{s≥u}(−1)^{dim u−dim s} ∑_{R∈ℛ(ℋ^{s})} v(R̄)

= ∑_{s≥u}(−1)^{dim u−dim s} ∑_{R∈ℛ(ℋ^{s})} ∑_{F ∈ℱ(ℋ^{s}):F ≤R} v(F)

= ∑_{F ∈ℱ(ℋ^{u})} (−1)^{dim u−dim F} v(F) ∑_{\begin{matrix}R∈ℱ(ℋ^{u}) \\ R≥F \end{matrix}} (−1)^{dim R−dim F} .  (8.3)

The lattice of faces of ℋ, ℱ̂(ℋ), is ℱ(ℋ) with an extra top element ˆ1 adjoined. It is known that ℱ̂(ℋ) is Eulerian, that is, μ(x, y) = (−1)^{rk y−rk x} if x ≤ y. Thus when x ≤ y < ˆ1, μ(x, y) = (−1)^{dim y−dim x}. The inner sum in (8.3) is therefore

∑_{R≥F} μℱ̂(F, R) = −μ_{ℱ̂(ℋ^{u})} (F, ˆ1) = (−1)^{dim u−dim F} ,

so (8.3) equals (8.2).

Having established (8.1) we invert to obtain

(−1)^{dim u}E_{v}(u) = ∑_{s≥u} μ_{ℒ} (u, s)(−1)^{dim s}v(s).

Multiplying this by (−1)^{dim u} and applying Rota’s sign theorem, we have the theorem. ■

For completeness we sketch a proof that ℱ̂(ℋ) is Eulerian. Let ℋ_{ℙ} be the projectivization of ℋ, that is, ℋ ∪ {h_{∞}} in ℙ^{d} with the affine hyperplanes extended into infinity. ℋ_{ℙ} is the projection of a homogeneous hyperplane arrangement ℋ′ in ℝ^{d+1}, whose face lattice is dual to that of a zonotope, whose face lattice is Eulerian because a zonotope is a convex polytope. Faces of ℋ′ other than the 0-face, F′_{0} = ⋂ ℋ′, come in opposite pairs, F′ and −F′, which project to a single face F of ℋ_{ℙ}. The interval [F_{1}, ˆ1] in ℱ̂(ℋ_{ℙ}) is isomorphic to [F′_{1}, ˆ1] in ℱ̂(ℋ′) if F′_{i} projects to F_{i}. As for F′_{0}, it projects to an infinite face. Therefore, for any face F of ℋ, which is necessarily a finite face of ℋ_{ℙ}, the interval [F, ˆ1] in ℱ̂(ℋ) is equal to [F, ˆ1]_{ℱ̂(ℋ_{ℙ})} , which is isomorphic to [F′, ˆ1]_{ℱ̂(ℋ′)} . It follows that μ(F, ˆ1) in ℱ̂(ℋ) equals (−1)^{d+1−dim F}.

Acknowledgement

We thank Jeffrey C. Lagarias for valuable criticisms and suggestions about the exposition.

References

[1] W. S. Andrews and others, Magic Squares and Cubes, 2nd ed. Open Court, La Salle, Ill., 1917. Repr. Dover, New York. 1960. MR 22 #5582.

[2] W. W. Rouse Ball, Mathematical Recreations and Essays, 11th ed., revised by H. S. M. Coxeter. Macmillan, London, 1939. MR 8, 440b. Zbl. 22, 1a (e: 022.00101).

[3] Matthias Beck and Thomas Zaslavsky, The number of nowhere-zero flows in graphs and signed graphs.

Submitted. Available on the Web at http://arXiv.org/abs/math.CO/0309331

[4] ——, An enumerative geometry for magic and magilatin labellings. In preparation.

[5] G. D. Birkhoff, A determinant formula for the number of ways of coloring a map. Ann. Math. (2) 14 (1912–13), 42–46.

[6] Andreas Blass and Bruce Sagan, Characteristic and Ehrhart polynomials. J. Algebraic Combin. 7 (1998), 115–126. MR 99c:05204. Zbl. 899.05003.

[7] R. Bodendiek and G. Walther, On the relations between certain graph labelings. Algebraic and Topological Methods in Graph Theory (Lake Bled, 1991). Discrete Math. 134 (1994), 9–16. MR 95m:05200. Zbl. 818.05055.

[8] T. A. Dowling, A class of geometric lattices based on finite groups. J. Combin. Theory Ser. B 14 (1973), 61–86. MR 46 #7066. Erratum. J. Combin. Theory Ser. B 15 (1973), 211. MR 47 #8369. Zbl. 247.05019.

[9] Eugène Ehrhart, Sur les polyèdres rationnels homothétiques à n dimensions. C. R. Acad. Sci. Paris 254 (1962), 616–618. MR 24 #A714. Zbl. .

[10] ——, Sur un problème de géometrie diophantienne linéaire. I: Polyèdres et réseaux. II: Systèmes diophantiens linéaires. J. reine angew. Math. 226 (1967), 1–29; 227 (1967), 25–49. Correction. J. reine angew. Math. 231 (1968), 220. MR 35 #4184, 36 #105. Zbl. 155.37503, 164.05304.

[11] ——, Polynômes Arithmétiques et Méthode des Polyèdres en Combinatoire. Int. Ser. Numer. Math., Vol. 35. Birkhäuser, Basel, 1977. MR 55 #5544. Zbl. 337.10019.

[12] Joseph A. Gallian, A dynamic survey of graph labeling. Electronic J. Combin. 5 (1998), Dynamic Survey # 8, 43 pp. (electronic). Revised ed. (2002), 106 pp. (electronic). MR 99m:05141. Zbl. 953.05067.

[13] Curtis Greene, Acyclic orientations (Notes). In: M. Aigner, ed., Higher Combinatorics (Proc. NATO Adv. Study Inst., Berlin, 1976), pp. 65–68. NATO Adv. Study Inst. Ser., Ser. C, Vol. 31. D. Reidel, Dordrecht, 1977. MR 58 #27507 (book). Zbl. 389.05036.

[14] ——, On the Möbius algebra of a partially ordered set. Adv. Math. 10 (1973), 177–187. MR 47 #4886. Zbl. 261.06001.

[15] Curtis Greene and Thomas Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Amer. Math. Soc. 280 (1983), 97–126. MR 84k:05032. Zbl. 539.05024.

[16] Nora Hartsfield and Gerhard Ringel, Pearls in Graph Theory. Academic Press, Boston, 1990. MR 91f:05001. Zbl. 703.05001.

[17] I. Heller and C. B. Tompkins, An extension of a theorem of Dantzig’s. In: H. W. Kuhn and A. W. Tucker, eds., Linear Inequalities and Related Systems, pp. 247–252. Annals of Math. Studies, No. 38. Princeton Univ. Press, Princeton, N.J., 1956. MR 18, 459. Zbl. 72, 378 (e: 072.37804).

[18] Martin Kochol, Polynomials associated with nowhere-zero flows. J. Combin. Theory Ser. B 84 (2002), 260–269. MR 2002k:05193.

[19] Dénes König, Theorie der endlichen und unendlichen Graphen. Mathematik und ihre Anwendungen, Band 16. Akademische Verlagsgesellschaft, Leipzig, 1936. Repr. Chelsea, New York, 1950. MR 12, 195. Zbl. 13, 228 (e: 013.22803). English trans. Theory of Finite and Infinite Graphs. Birkhäuser, Boston, 1990. MR 91f:01026. Zbl. 695.05015.

[20] I. G. Macdonald, The volume of a lattice polyhedron. Proc. Camb. Phil. Soc. 59 (1963), 719–726. MR 27 #4139. Zbl. 126.18103.

[21] ——, Polynomials associated with finite cell-complexes. J. London Math. Soc. (2) 4 (1971), 181–192. MR 45 #7594. Zbl. 216, 452 (e: 216.45205).

[22] P. McMullen, Lattice invariant valuations on rational polytopes. Arch. Math. (Basel) 31 (1978/79), 509–516. MR 80d:52011. Zbl. 387.52007.

[23] Jennifer McNulty, Generalized affine matroids. Proc. Twenty-fifth Southeastern Int. Conf. Combinatorics, Graph Theory and Computing (Boca Raton, Fla., 1994). Congr. Numer. 101 (1994), 243–254. MR 96k:05034. Zbl. 842.05019.

[24] Gian-Carlo Rota, On the foundations of combinatorial theory: I. Theory of Möbius functions. Z. Wahrsch. verw. Gebiete 2 (1964), 340–368. MR 30 #4688. Zbl. 121, 24f (e: 121.02406). Many times reprinted.

[25] Louis Solomon, The Burnside algebra of a finite group. J. Combin. Theory 2 (1967), 603–615. MR 35 #5528. Zbl. 183, 36 (e: 183.03601).

[26] Martin Sonntag, Antimagic vertex labelings of hypergraphs. Discrete Math. 247 (2002), 187–199. MR 2003d:05192. Zbl. 1008.05138.

[27] Richard P. Stanley, Acyclic orientations of graphs. Discrete Math. 5 (1973), 171–178. MR 47 #6537. Zbl. 258.05113.

[28] ——, Enumerative Combinatorics, Vol. I. Wadsworth & Brooks/Cole, Monterey, Calif., 1986. MR 87j:05003. Corrected repr., Cambridge Stud. Adv. Math., Vol. 49. Cambridge Univ. Press, Cambridge, Eng., 1997. MR 98a:05001. Zbl. 889.05001, 945.05006.

[29] ——, personal communication, June 16, 2003.

[30] J. Steiner, Einige Gesetze über die Theilung der Ebene und des Raumes. J. reine angew. Math. 1 (1826), 349–364.

[31] Frank Swetz, Legacy of the Luoshu: The 4,000 Year Search for the Meaning of the Magic Square of Order Three. Open Court, Chicago, 2002.

[32] Michelle L. Wachs and James W. Walker, On geometric semilattices. Order 2 (1986), 367–385. MR 87f:06004. Zbl. 589.06005.

[33] H. Whitney, A logical expansion in mathematics. Bull. Amer. Math. Soc. 38 (1932), 572–579. Zbl. 5, 146b (e: 005.14602).

[34] Thomas Zaslavsky, Facing Up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes. Mem. Amer. Math. Soc., No. 154. American Mathematical Society, Providence, R.I., 1975. MR 50 #9603. Zbl. 296.50010.

[35] ——, Signed graphs. Discrete Appl. Math. 4 (1982), 47–74. Erratum. Discrete Appl. Math. 5 (1983), 248. MR 84e:05095. Zbl. 503.05060.

[36] ——, Signed graph coloring. Discrete Math. 39 (1982), 215–228. MR 84h:05050a. Zbl. 487.05027.

[37] ——, Orientation of signed graphs. European J. Combin. 12 (1991), 361–375. MR 93a:05065. Zbl. 761.05095.

[38] Günther Ziegler, Lectures on Polytopes. Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995. MR 96a:52011. Zbl. 823.52002.