Arrangements, channel assignments, and associated polynomials (Q1961908)

In generalization of the classical definition, the authors define an arrangement \(\mathcal A\) to be any collection of elements \(E\) of a geometric lattice \(L\). The classical definitions are obtained by regarding \(L\) to be the appropriate lattice of subspaces of a vector or affine space. Such an arrangement has an upper rank function \(\mu\) and a lower rank function \(\delta\). The functions \(f\), besides being submodular, satisfy the conditions: (i) \(f(\varnothing)=0\) and (ii) \(f(A)\geq f(B)\) for \(A\supseteq B\), and \(A,B \subseteq E\). A configuration \(Q\) is defined to be a pair \((E,f)\), where \(E\) is any set and \(f\) is a function satisfying conditions (i) and (ii), and is called the rank function of \(Q\). Given \(Q=(E,r)\) and \(e\in E\), the deletion \(Q_{e}'= (E\setminus e, r_{e}')\) where \(r_{e}'(A) = r(A)\) and the contraction \(Q_e'' = (E\setminus e, r_e'')\) with \(r_e''(A) = r(A\cup e) - r\{ e \}\) for \(A\subseteq E\). Allowing \(E\) to be a multiset of elements of \(L\), for an arrangement \(\mathcal A = (E,L)\) and \(e \in E\) , we can define the deletion \(\mathcal A_e' = (E\setminus e,L)\) and the upper and lower contractions \(\mathcal A_e'' =(\{[a\vee e] : a\in \{E\setminus e\}\} , [e,\widehat{1}])\) and \( \mathcal A_e''' = (\{a \wedge e : a \in \{E\setminus e\}\} ,[0,e])\). A lattice and an arrangement based on \(\mathcal A\) is said to be coloured by simply specifying a prescribed subset \(B\) of elements of \(L\) to be coloured (= blue). An element \(x\) of \(L\) is above an element \(y\) if \(x\geq y\). Let \(\phi_c({\mathcal A})\) denote the number of blue elements of the coloured arrangement \(\mathcal A\) that are above exactly \(e\) elements of \(\mathcal A\). Then \(\phi_c\) is shown to satisfy the three-term recurrence \(\phi_c (\mathcal A) = \phi_c ({\mathcal A}'_e)- \phi_c ({\mathcal A}_e'')+ \phi_{c-1} ({\mathcal A}_e'')\). This is the natural generalization of the three-term recurrence \(b_k (G;\lambda) = b_k (G'_e ; \lambda) - b_k (G''_e;\lambda) + b_{k-1} ( G''_e;\lambda)\) for a graph \(G\), where \(b_k (G ; \lambda)\) denotes the number of \(\lambda\)-colourings of \(G\) in which exactly \(k\) edges are monochromatic or bad, \(( k \geq 1)\) , and \(G'_e , G_e''\) denote the usual deletion and contraction for graphs. A framed configuration \(\widehat{Q}\) has a distinguished element \(\square \) and its rank function satisfies \(r_{\widehat{Q}} (A) = r_{Q}( A)\) if \(\square \not\in A\) and \(r_{\widehat{Q}}(A) = n\) if \(\square \in A\). For each integer \(k\geq 0\) a single element framed configuration \(Z_k\) is defined with \(E=\square \), \(r(\varnothing) = 0\), \(r(\square) = k\). The Whitney polynomial of a framed configuration \(Q\) is then defined as \[ W(Q) W(Q; s,z_0, z_1,\ldots) = \sum_{A \subseteq \{E\setminus \square \}} (s-1)^{|A |} z_{r(E) - r(A)}. \] It is deduced that \(W(Z_{k}) = z_{k}\) and \(W\) satisfies \(W(Q) = W(Q'_{e}) + (s-1)W(Q_e'')\), for \(e \neq \square \). A configuration obtained from \(Q\) by a series of deletions and contractions is a minor. A Whitney invariant \(\psi \) of a minor-closed family \(\mathcal F\) of framed configurations is defined to be a function from \(\mathcal F\) to a commutative ring \(R\) satisfying \(\psi(Q) = \alpha \psi(Q'_{e}) + \beta \psi (Q_{e}'')\) for all \(e\in \{ E(Q)\setminus \square \}\), all \(Q\in \mathcal F\), and some \(\alpha ,\beta \in R\). It is shown that the Whitney polynomial evaluates all Whitney invariants of framed configurations. A Whitney sequence of \(\mathcal F\) is then defined and the Whitney polynomial is shown to be the generating function of such a sequence. These general ideas are used in a wide variety of applications like counting lattice points, the problem of assigning radio frequencies to channels, hypergraph colouring, the critical problem for a set of points in a vector space over a finite field, intersection theory of algebraic geometry and of hypergraphs, and Redei functions of relations. Simple examples are given to illustrate the computations. There are a few obvious typos.