Valuations and 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.