Hamiltonian paths, unit-interval complexes, and determinantal facet ideals
From MaRDI portal
Publication:2168562
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.
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
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 482758 (Why is no real title available?)
- scientific article; zbMATH DE number 3293646 (Why is no real title available?)
- scientific article; zbMATH DE number 3307330 (Why is no real title available?)
- scientific article; zbMATH DE number 3186565 (Why is no real title available?)
- A Characterization of Comparability Graphs and of Interval Graphs
- A class of hypergraphs that generalizes chordal graphs
- A decomposition theorem for partially ordered sets
- A generalization of Fan's condition for Hamiltonicity, pancyclicity, and Hamiltonian connectedness
- A generalization of Ore's Theorem involving neighborhood unions
- A linear time recognition algorithm for proper interval graphs
- A method in graph theory
- A simple polynomial algorithm for the longest path problem on cocomparability graphs
- An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
- An efficient condition for a graph to be Hamiltonian
- Binomial edge ideals and conditional independence statements
- Binomial edge ideals of graphs
- Closed graphs are proper interval graphs
- Determinantal facet ideals
- Determinantal rings
- Dirac-type results for loose Hamilton cycles in uniform hypergraphs
- Fan type condition and characterization of Hamiltonian graphs
- Finding Hamiltonian circuits in proper interval graphs
- Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
- Generically acyclic complexes and generically perfect ideals
- Graphs and ideals generated by some 2-minors
- Gröbner bases and Stanley decompositions of determinantal ideals
- Hamiltonian chains in hypergraphs
- Hamiltonian cycle is polynomial on cocomparability graphs
- Hamiltonian graphs involving distances
- Higher chordality: from graphs to complexes
- How the upper bound conjecture was proved
- Incidence matrices and interval graphs
- Knutson ideals and determinantal ideals of Hankel matrices
- Knutson ideals of generic matrices
- Large cycles in graphs
- Loose Hamilton cycles in hypergraphs
- New sufficient conditions for cycles in graphs
- Non-ridge-chordal complexes whose clique complex has shellable Alexander dual
- Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
- Note on Hamilton Circuits
- On Hamilton's ideals
- On Hamiltonian Circuits in Finite Graphs
- On closed graphs. I
- Optimal greedy algorithms for indifference graphs
- Pancyclic graphs and a conjecture of Bondy and Chvatal
- Pancyclic graphs. I
- Proper interval graphs and the guard problem
- Reducibility among combinatorial problems
- Regularity bounds for binomial edge ideals
- Representation of a finite graph by a set of intervals on the real line
- Some Theorems on Abstract Graphs
- Square-free Gröbner degenerations
- The Roberts characterization of proper and unit interval graphs
- Weakly closed graphs and \(F\)-purity of binomial edge ideals
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)
