Valuations and Oriented Matroids

摘要：有向拟阵是反映欧几里德空间中有限集合子集的凸壳之间关联关系的组合对象。对于凸集族上的函数，我们发现它是一个赋值的性质是非常有用的。这两种思想的结合应该会导致对组合几何中许多有趣的开放问题的富有成果的研究。一致定向拟阵上的“线性变化”函数的概念提供了一种结合这两种思想的方法。线性变化函数的例子包括点结构中的“k集”的数量，简单凸多面体的k个面的数量，以及具有n个顶点的完整图的直线图中的交叉点的数量。研究者将研究均匀取向拟阵上线性变化函数的极值性质，期望获得关于这些函数和其他线性变化函数的实质性知识。此外，研究者将探索将线性变化函数的概念扩展到不一定均匀的定向拟阵的可能性。下面是组合几何问题的一个例子。假设平面上有n个点，没有3个点在同一条直线上。如果所有连接这些点的线段一次画两个，那么有多少个交叉点？当n超过10时，没有人知道这种交叉的最小可能次数是多少。“有向矩阵”的概念提供了一个抽象框架，用于研究这个问题和其他二维及高维组合几何问题。定向拟阵是在大约25年前由几个不同的数学家同时首次描述的，它们的应用取得了丰硕的成果。研究者打算将这一抽象框架与另一个富有成效的想法结合起来，即“估值”，以期解决这一领域的一些问题。组合几何问题的解决通常会导致更好的计算几何算法，偶尔也会改进计算机芯片的设计。

"Valuations and Oriented Matroids"Abstract: Oriented matroids are combinatorial objects which reflect incidence relations among convex hulls of subsets of finite sets in Euclidean space. For functions on families of convex sets, the property of being a valuation has been found to be very useful. The combination of these two ideas should result in a fruitful study of many interesting open problems in combinatorial geometry. The notion of a "linearly varying" function on uniform oriented matroids provides a means of combining the two ideas. Examples of linearly varying functions include the number of "k-sets" in a configuration of points, the number of k-faces of a simplicial convex polytope, and the number of crossings in a rectilinear drawing of the comlete graph with n vertices. The investigator will study the extremal properties of linearly varying functions on uniform oriented matroids, with the expectation that substantial knowledge about these and other linearly varying functions will be obtained. Additionally, the investigator will explore the possibility of extending the notion of linearly varying functions to oriented matroids which are not necessarily uniform. An example of a problem in combinatorial geometry is the following. Suppose n points in the plane are given, and no three are on a common line. If all of the line segments joining these points two at a time are drawn, how many crossings must there be? When n exceeds 10, no one knows what the least possible number of such crossings is. An abstract framework for studying this and other problems of combinatorial geometry in two and higher dimensions is provided by the notion of an "oriented matroid." Oriented matroids were first described about twenty-five years ago, simultaneously by several different mathematicians, and their use has been fruitful. The investigator intends to use this abstract framework in conjunction with another fruitful idea, that of a "valuation," with the expectation of solving some problems in this area. Solutions of problems in combinatorial geometry often lead to better algorithms for computational geometry, and occasionally to improved designs for computer chips.