Hamiltonian paths, unit-interval complexes, and determinantal facet ideals
From MaRDI portal
Publication:2168562
DOI10.1016/J.AAM.2022.102407zbMATH Open1496.13034arXiv2101.09243OpenAlexW3161289065WikidataQ114214497 ScholiaQ114214497MaRDI QIDQ2168562FDOQ2168562
Authors: Bruno Benedetti, Lisa Seccia, Matteo Varbaro 
Publication date: 31 August 2022
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Abstract: We study d-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 Posa'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 Hamiltonian paths in simplicial complexes. Some important consequences of our work are: (1) Every almost-closed strongly-connected d-dimensional simplicial complex is traceable. (This extends the well-known result "unit-interval connected graphs are traceable".) (2) Every almost-closed d-complex that remains strongly connected after the deletion of d or 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 Groebner 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 the d-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 characteristic p, they are even F-pure.
Full work available at URL: https://arxiv.org/abs/2101.09243
Recommendations
- Hilbert function and facet ideals of products of simplicial complexes
- Hamiltonism, degree sum and neighborhood intersections
- Hankel edge ideals of trees and (semi-)Hamiltonian graphs
- Path complexes and their homologies
- Counting of paths and coefficients of the Hilbert polynomial of a determinantal ideal
- scientific article; zbMATH DE number 1500636
- Toric ideals of lattice path matroids and polymatroids
- Determinantal facet ideals
- Hamilton Paths in Graphs of Linear Extensions for Unions of Posets
- On the matroidal path ideals
Paths and cycles (05C38) Syzygies, resolutions, complexes and commutative rings (13D02) Rings with straightening laws, Hodge algebras (13F50) Commutative rings defined by binomial ideals, toric rings, etc. (13F65)
Cites Work
- Reducibility among combinatorial problems
- On Hamilton's ideals
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding Hamiltonian circuits in proper interval graphs
- Proper interval graphs and the guard problem
- Optimal greedy algorithms for indifference graphs
- Incidence matrices and interval graphs
- Pancyclic graphs. I
- On closed graphs. I
- Note on Hamilton Circuits
- A simple polynomial algorithm for the longest path problem on cocomparability graphs
- Title not available (Why is that?)
- Some Theorems on Abstract Graphs
- Representation of a finite graph by a set of intervals on the real line
- Hamiltonian chains in hypergraphs
- A Characterization of Comparability Graphs and of Interval Graphs
- New sufficient conditions for cycles in graphs
- A class of hypergraphs that generalizes chordal graphs
- An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
- Dirac-type results for loose Hamilton cycles in uniform hypergraphs
- How the upper bound conjecture was proved
- A decomposition theorem for partially ordered sets
- Determinantal rings
- Generically acyclic complexes and generically perfect ideals
- Large cycles in graphs
- Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
- A method in graph theory
- Loose Hamilton cycles in hypergraphs
- Regularity bounds for binomial edge ideals
- Pancyclic graphs and a conjecture of Bondy and Chvatal
- A generalization of Ore's Theorem involving neighborhood unions
- A generalization of Fan's condition for Hamiltonicity, pancyclicity, and Hamiltonian connectedness
- Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
- Hamiltonian graphs involving distances
- A linear time recognition algorithm for proper interval graphs
- Binomial edge ideals and conditional independence statements
- The Roberts characterization of proper and unit interval graphs
- An efficient condition for a graph to be Hamiltonian
- Binomial edge ideals of graphs
- Graphs and ideals generated by some 2-minors
- Weakly closed graphs and \(F\)-purity of binomial edge ideals
- Title not available (Why is that?)
- Gröbner bases and Stanley decompositions of determinantal ideals
- Higher chordality: from graphs to complexes
- Knutson ideals of generic matrices
- Square-free Gröbner degenerations
- Hamiltonian cycle is polynomial on cocomparability graphs
- On Hamiltonian Circuits in Finite Graphs
- Determinantal facet ideals
- Knutson ideals and determinantal ideals of Hankel matrices
- Closed graphs are proper interval graphs
- Non-ridge-chordal complexes whose clique complex has shellable Alexander dual
- Fan type condition and characterization of Hamiltonian graphs
Cited In (1)
Uses Software
This page was built for publication: Hamiltonian paths, unit-interval complexes, and determinantal facet ideals
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2168562)
