Study of universal Grobner bases of zero-dimensional lattice ideals

零维晶格理想通用格罗布纳基的研究

基本信息

批准号：
15340007
负责人：
HIBI Takayuki
金额：
$ 5.5万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15340007/
关键词：
Grobner Basis Universal Grobner Basis Lattice Ideal Integer Programming Corner Polytope Finite Graph Toric Ideal Initial Ideal 隣接行列符号理論組合せ最適化問題 Gomory relaxation corner polyhedron

项目摘要

The lattice ideal of dimension zero appears in the research of both pure mathematics and applied mathematics. The original purpose of the present research project was to establish the algebraic theory of universal Groebner bases of lattice ideal of dimension zero and to study of its theoretical effectivity to commutative algebra and algebraic geometry as well as its practical effectivity to integer programming, coding theory together with algebraic statistics. First, we investigated the universal Groebner basis of the lattice ideal of dimension zero arising from the toric ideal of a finite graph and succeeded in describing its structure in terms of the finite graph. Second, in the study of a problem on integer programming arising from a finite graph for which Gomory's relaxation can be applied, we developed the technique to decide the estimation of the computational complexity of finding an optimal solution by using combinatorics on finite graphs. Third, we achieved the study of finding an explicit expression of the corner polyhedron of a lattice ideal of dimension zero in terms of the Minkowski sum of a bounded convex polytope and a convex cone, and obtained some results on the combinatorics of the polyhedral structure of the corner polyhedron. Finally, we developed the algebraic study on the Markov basis of the contingency table in algebraic statistics and presented a statistic model arising from a complete multipartite graph. These research results will contribute to the development of the algebraic study of integer programming. In addition, we organized two international meetings related with computational commutative algebra and Groebner bases.

零尺寸的晶格理想出现在纯数学和应用数学的研究中。本研究项目的最初目的是建立零尺寸的晶格理想的通用格罗布纳基础的代数理论，并研究其对交换代数和代数几何形状的理论有效性，以及对整数编码，编码理论以及代数统计的实际有效性。首先，我们研究了由有限图的复曲率理想产生的零尺寸晶格理想的通用groebner基础，并成功地用有限图描述了其结构。其次，在对可以应用Gomory放松的有限图引起的整数编程的问题的研究中，我们开发了该技术来确定通过在有限图上使用组合仪来找到最佳解决方案的计算复杂性的估计。第三，我们实现了找到尺寸为零的晶格理想的角度表达的研究，该晶格的圆角理想是根据有界凸层和凸锥的Minkowski总和，并获得了角度多角体的多面性结构的组合。最后，我们在代数统计中的应急表的马尔可夫基础上开发了代数研究，并提出了由完整的多方图引起的统计模型。这些研究结果将有助于开发整数编程的代数研究。此外，我们组织了两次与计算交换代数和格罗布纳基地有关的国际会议。