Ordering points by linear functionals (Q1964657): Difference between revisions

Let \(\mathcal C\) denote a configuration of points in \({\mathbb R}^n\). Fixing a generic direction \(\vec{v}\) in \({\mathbb R}^n\) yields a linear ordering of the points of \(\mathcal C\). The author establishes upper and lower bounds on the number \(f({\mathcal C})\) of such orderings, using results from matroid theory. Let \(\mathcal A\) denote the arrangement of hyperplanes orthogonal to the difference vectors \(x - y\) for \(x,y\in {\mathcal C}\). Then \(\vec{v}\) is generic if and only if \(\vec{v}\) lies in the complement of \(\mathcal A\), and two directions \(\vec{v}\) and \(\vec{w}\) induce the same order on \(\mathcal C\) if and only if they lie in the same component of the complement. Then the number of linear orderings is expressed in terms of Whitney numbers of the geometric lattice associated with \(\mathcal A\). If \(\mathcal C\) is a basis for \({\mathbb R}^n\) then \(\mathcal A\) is the arrangement associated with the root system of type \(A_{n-1}\). Loosely speaking, the author shows that every other case can be obtained from this one via iterated truncations and weak maps. These operations cannot increase Whitney numbers, so one obtains an upper bound on \(f({\mathcal C})\) in terms of Stirling numbers, the Whitney numbers associated with the \(A_{n-1}\) arrangement. Lower bounds on \(f({\mathcal C})\) in general are difficult to come by. For \(n=2\) this is equivalent to the slope problem: to determine the minimum number of slopes determined by \(k\) points in the plane. This was solved by \textit{P. Ungar} [J. Comb. Theory, Ser. A 33, 343-347 (1982; Zbl 0496.05001)]. Here Edelman establishes a lower bound for arbitrary \(n\) in terms of falling factorials, but only for generic configurations. He conjectures a specific lower bound for configurations in slope-general position, i.e., configurations of \(k\) points that determine \(k\choose 2\) different slopes. A coherent monotone path on a polytope is an edge-path which is monotonic increasing relative to some direction. In the last section the author shows how to construct from a given zonotope \(Z\) a configuration \({\mathcal C}(Z)\) such that \(f({\mathcal C}(Z))\) is precisely the number of coherent monotone paths on \(Z\).