Combinatorial Degree Bound for Toric ideals of hypergraphs
Combinatorial Degree Bound for Toric ideals of hypergraphs
复制标题
超图环面理想的组合度界
DOI：
--
复制
发表时间：
2012
影响因子：
0.8
通讯作者：
Sonja Petrović
中科院分区：
文献类型：
--
作者：
Elizabeth Gross;Sonja Petrović
与任何超图相关联的是一个环面理想，编码其边之间的代数关系。我们研究这些理想及其最小生成器的组合，并根据平衡超图双色、分隔符和分裂集导出均匀和非均匀超图的一般度界限。反过来，这为与超图相关的代数统计模型提供了复杂性界限。作为两个主要应用，我们恢复了任意三向表的马尔可夫基的众所周知的复杂性结果，并且我们表明切向簇的定义理想是由累积坐标中的二次和三次生成的。
Associated to any hypergraph is a toric ideal encoding the algebraic relations among its edges. We study these ideals and the combinatorics of their minimal generators, and derive general degree bounds for both uniform and non-uniform hypergraphs in terms of balanced hypergraph bicolorings, separators, and splitting sets. In turn, this provides complexity bounds for algebraic statistical models associated to hypergraphs. As two main applications, we recover a well-known complexity result for Markov bases of arbitrary 3-way tables, and we show that the defining ideal of the tangential variety is generated by quadratics and cubics in cumulant coordinates.