Valuations and Oriented Matroids

估值和定向拟阵

• 批准号: 9970525
• 负责人: James Lawrence
• 金额: --
• 依托单位: George Mason University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-06-01 至 2001-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9970525&HistoricalAwards=false
• 关键词: Valuations; Oriented; Matroids

"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.

《估值与有向拟阵》 摘要：有向拟阵是反映欧氏空间中有限集子集的凸包之间的关联关系的组合对象。对于凸集族上的函数，评估属性被发现非常有用。这两种想法的结合应该能够对组合几何中许多有趣的开放问题进行富有成效的研究。均匀定向拟阵上的“线性变化”函数的概念提供了一种结合这两种想法的方法。线性变化函数的示例包括点配置中“k 集”的数量、单纯凸多面体的 k 面数量以及具有 n 个顶点的完整图的直线图中的交叉数量。研究者将研究均匀定向拟阵上线性变化函数的极值性质，期望获得有关这些函数和其他线性变化函数的大量知识。此外，研究人员将探索将线性变化函数的概念扩展到不一定均匀的定向拟阵的可能性。下面是组合几何问题的一个示例。假设平面上有 n 个点，并且没有三个点在一条公共直线上。如果一次绘制连接这些点两个点的所有线段，则必须有多少个交叉点？当 n 超过 10 时，没有人知道这种交叉的最少可能次数是多少。 “定向拟阵”的概念提供了用于研究二维及更高维度的组合几何的这个问题和其他问题的抽象框架。大约二十五年前，几位不同的数学家同时首次描述了定向拟阵，并且它们的使用取得了丰硕的成果。研究者打算将这个抽象框架与另一个富有成效的想法（“评估”）结合使用，以期解决该领域的一些问题。组合几何问题的解决通常会带来更好的计算几何算法，有时还会改进计算机芯片的设计。