Explicit Boij-Soderberg theory of ideals from a graph isomorphism reduction

JOURNAL OF PURE AND APPLIED ALGEBRA

卷:224

Article

Engstrom, Alexander¹  Jakobsson, Laura¹  Orlich, Milo¹ 

[1] Aalto Univ, Dept Math & Syst Anal, Espoo, Finland

关键词: Linear resolutions;    Graded Betti numbers;    Edge ideals;    Graph isomorphism;   

DOI  :  10.1016/j.jpaa.2020.106405

来源: Elsevier

【 摘 要 】

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 I-BL(G) are 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. (C) 2020 Elsevier B.V. All rights reserved.

【 授权许可】

Free