Valuations and Oriented Matroids

“赋值与定向拟阵”摘要：定向拟阵是反映欧氏空间中有限集子集的凸壳之间关联关系的组合对象。对于凸集族上的函数，赋值的性质已经被发现是非常有用的。这两个想法的结合应该会导致对组合几何中许多有趣的开放问题的富有成效的研究。均匀定向拟阵上的“线性变化”函数的概念提供了一种结合这两种思想的方法。线性变化函数的例子包括点的配置中的“k-集合”的数目，单凸多面体的k-面的数目，以及具有n个顶点的Comlet图的直线图中的交叉数目。研究者将研究一致定向拟阵上线性变化函数的极值性质，以期获得关于这些函数和其他线性变化函数的实质性知识。此外，研究人员将探索将线性变化函数的概念扩展到定向拟阵的可能性，这些定向拟阵不一定是一致的。下面是组合几何中的一个问题的例子。假设平面上有n个点，并且没有三个点在一条公共直线上。如果一次绘制两个连接这些点的所有线段，那么必须有多少个交叉点？当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.