Hamiltonian paths, unit-interval complexes, and determinantal facet ideals
Hamiltonian paths, unit-interval complexes, and determinantal facet ideals
复制标题
DOI：
10.1016/j.aam.2022.102407
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Bruno Benedetti;Lisa Seccia;M. Varbaro
中科院分区：
文献类型：
--
作者：
Bruno Benedetti;Lisa Seccia;M. Varbaro
我们研究了图论中三个相互关联的主题的二维推广：哈密顿路径，（单位）区间图，和二项式边理想。我们给出了Ore的部分高维推广和Pósa图是哈密顿的充分条件。我们为推广单位间隔图、区间图和共可比性图的简单复合体引入了组合性质的层次结构。我们将这些性质与简单复合体中已经存在的决定面理想和（紧和弱）哈密顿路径的概念联系起来。本文的一些重要结论是：(1)每一个单位区间强连通维简单复形都是可追溯的。（这扩展了众所周知的结果“单位间隔连通图是可追踪的”。）(2)每一个单位间隔复合体在删除少顶点后仍然保持强连接，是哈密顿的。（这扩展了“单位间隔2连通图是哈密顿图”的事实。）(3)在可追溯的配合物中，单位区间配合物的特征在于，定义其决定面理想的次元形成了与配合物可追溯性相容的对角项顺序的Gröbner基。（这修正了Ene等人最近的一个定理，扩展了Herzog等人的一个结果，并部分回答了Almousa-Vandebogert的一个问题。）(4)只有单纯形的骨架具有线性分辨率的确定性面理想。（这扩展了Kiani和Saeedi-Madani的结论，即“只有完全图具有线性分辨率的二项边理想”。）(5)所有欠封闭和半封闭复形的行列式面理想对于lex都有一个无平方的初始理想。在特征上，它们甚至是f纯的。
We studyd-dimensional generalizations of three mutually related topics in graph theory: Hamiltonian paths, (unit) interval graphs, and binomial edge ideals. We provide partial high-dimensional generalizations of Ore and Pósa's sufficient conditions for a graph to be Hamiltonian. We introduce a hierarchy of combinatorial properties for simplicial complexes that generalize unit-interval, interval, and co-comparability graphs. We connect these properties to the already existing notions of determinantal facet ideals and (tight and weak) Hamiltonian paths in simplicial complexes. Some important consequences of our work are:(1)Every unit-interval strongly-connectedd-dimensional simplicial complex is traceable.(This extends the well-known result “unit-interval connected graphs are traceable”.)(2)Every unit-intervald-complex that remains strongly connected after the deletion ofdor less vertices, is Hamiltonian.(This extends the fact that “unit-interval 2-connected graphs are Hamiltonian”.)(3)Unit-interval complexes are characterized, among traceable complexes, by the property that the minors defining their determinantal facet ideal form a Gröbner basis for a diagonal term order which is compatible with the traceability of the complex.(This corrects a recent theorem by Ene et al., extends a result by Herzog and others, and partially answers a question by Almousa–Vandebogert.)(4)Only thed-skeleton of the simplex has a determinantal facet ideal with linear resolution.(This extends the result by Kiani and Saeedi-Madani that “only the complete graph has a binomial edge ideal with linear resolution”.)(5)The determinantal facet ideals of all under-closed and semi-closed complexes have a square-free initial ideal with respect to lex. In characteristicp, they are even F-pure.