Explicit Boij-Söderberg theory of ideals from a graph isomorphism reduction

DOI10.1016/J.JPAA.2020.106405MaRDI QIDQ2184790zbMATH OpenOpenAlexFDO

Authors Alexander Engström, Laura Jakobsson, Milo Orlich

Publication date 29 May 2020

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.10055

zbMATH Keywords

edge idealsgraded Betti numbersgraph isomorphismlinear resolutions

Mathematics Subject Classification ID

Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of commutative algebra (05E40) Syzygies, resolutions, complexes and commutative rings (13D02)

Abstract: In the origins of complexity theory Booth and Lueker showed that the question of whether two graphs are isomorphic or not can be reduced to the special case of chordal graphs. To prove that, they defined a transformation from graphs G to chordal graphs BL(G). The projective resolutions of the associated edge ideals is manageable and we investigate to what extent their Betti tables also tell non-isomorphic graphs apart. It turns out that the coefficients describing the decompositions of Betti tables into pure diagrams in Boij-Soderberg theory are much more explicit than the Betti tables themselves, and they are expressed in terms of classical statistics of the graph G.

Recommendations

• Betti diagrams from graphs
• Combinatorial interpretations of some Boij-Söderberg decompositions
• Betti numbers of chordal graphs and \(f\)-vectors of simplicial complexes
• Dimensions of Betti cones on edge ideals

Cites work

• Algebraic properties of edge ideals via combinatorial topology
• Anti-lecture hall compositions
• Betti diagrams from graphs
• Betti numbers of graded modules and cohomology of vector bundles
• Boij-Söderberg theory: introduction and survey
• Graded Betti numbers of Cohen-Macaulay modules and the multiplicity conjecture
• scientific article; zbMATH DE number 3679885 (Why is no real title available?)
• scientific article; zbMATH DE number 16165 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 482758 (Why is no real title available?)
• Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers
• The mathematics of lecture hall partitions
• Triangulations of polygons and stacked simplicial complexes: separating their Stanley-Reisner ideals

Cited in

(1)

• Syzygies of \(\mathbb{P}^1 \times \mathbb{P}^1\): data and conjectures

Describes a project that uses

Uses Software

• BoijSoederberg

This page was built for publication: Explicit Boij-Söderberg theory of ideals from a graph isomorphism reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2184790)