Arrangements, channel assignments, and associated polynomials
type: Item
instance of: scholarly article
title: Arrangements, channel assignments, and associated polynomials
zbMATH Open document ID: 0942.05063
published in: Advances in Applied Mathematics
publication date: 2000-07-31T00:00:00Z
review text: 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…
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 51N35
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 14N10
zbMATH DE Number: 1394764
zbMATH Keywords: arrangement
zbMATH Keywords: channel assignment
zbMATH Keywords: configuration
zbMATH Keywords: Whitney polynomial
zbMATH Keywords: Tutte-Grothendieck invariant
zbMATH Keywords: graph colouring
zbMATH Keywords: intersection theory
zbMATH Keywords: Redei functions
zbMATH Keywords: geometric lattice
zbMATH Keywords: rank function
author: D. J. A. Welsh
author: Geoff Whittle
MaRDI profile type: Publication
OpenAlex ID: W2047371574
cites work: Characteristic polynomials of subspace arrangements and finite fields
cites work: Characteristic and Ehrhart polynomials
cites work: Intersection Theory for Embeddings of Matroids into Uniform Geometries
cites work: Intersection theory for graphs
cites work: Q5619114
cites work: Chromatic invariants for finite graphs: Theme and polynomial variations
cites work: Graph labeling and radio channel assignment
cites work: Q4053708
cites work: The Redei function of a relation
cites work: Q4717847
cites work: Q4133994
cites work: Q4003206
cites work: Q3135082
cites work: Star chromatic number
cites work: Q4111952
cites work: Q3140234
cites work: Characteristic polynomials of weighted lattices
cites work: A geometric theory of hypergraph colouring
cites work: THE CRITICAL PROBLEM FOR POLYMATROIDS
cites work: Q3768917
DOI: 10.1006/AAMA.1999.0660
description: scientific article; zbMATH DE number 1394764