Collapsibility and homological properties of I -contractible transformations

Jesús F. Espinoza; Martín Eduardo Frías-Armenta; Héctor A. Hernández-Hernández

doi:10.1007/s40590-022-00434-7

Collapsibility and homological properties of I -contractible transformations

Jesús F. Espinoza^*, Martín Eduardo Frías-Armenta, Héctor A. Hernández-Hernández

^*Corresponding author for this work

Departamento de Matemáticas

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

The family of I-contractible graphs and contractible transformations was defined by A. Ivashchenko in the mid-90s. In this paper we study the collapsibility and homological properties of the clique complex associated to I-contractible graphs. We show that for any graph in a special subfamily of the I-contractible graphs (the strong I-contractible ones) its clique complex is collapsible. Moreover, we present an algorithm that allows us to verify if any graph is strong I-contractible, as well as an algorithm to delete those vertices whose open neighborhood is also strong I-contractible. Finally, we show how to use these algorithms to compute the persistent homology of an arbitrary Vietoris–Rips complex for applications in topological data analysis.

Original language	English
Article number	42
Journal	Boletin de la Sociedad Matematica Mexicana
Volume	28
Issue number	2
DOIs	https://doi.org/10.1007/s40590-022-00434-7
State	Published - Jul 2022

Bibliographical note

Publisher Copyright:
© 2022, Sociedad Matemática Mexicana.

Keywords

Collapsible graph
Contractible transformations
Persistent homology
Vietoris–Rips complex

Access to Document

10.1007/s40590-022-00434-7

Cite this

@article{b24c579b89ea490fa9f4a0553145c8d0,

title = "Collapsibility and homological properties of I -contractible transformations",

abstract = "The family of I-contractible graphs and contractible transformations was defined by A. Ivashchenko in the mid-90s. In this paper we study the collapsibility and homological properties of the clique complex associated to I-contractible graphs. We show that for any graph in a special subfamily of the I-contractible graphs (the strong I-contractible ones) its clique complex is collapsible. Moreover, we present an algorithm that allows us to verify if any graph is strong I-contractible, as well as an algorithm to delete those vertices whose open neighborhood is also strong I-contractible. Finally, we show how to use these algorithms to compute the persistent homology of an arbitrary Vietoris–Rips complex for applications in topological data analysis.",

keywords = "Collapsible graph, Contractible transformations, Persistent homology, Vietoris–Rips complex",

author = "Espinoza, {Jes{\'u}s F.} and Fr{\'i}as-Armenta, {Mart{\'i}n Eduardo} and Hern{\'a}ndez-Hern{\'a}ndez, {H{\'e}ctor A.}",

note = "Publisher Copyright: {\textcopyright} 2022, Sociedad Matem{\'a}tica Mexicana.",

year = "2022",

month = jul,

doi = "10.1007/s40590-022-00434-7",

language = "Ingl{\'e}s",

volume = "28",

journal = "Boletin de la Sociedad Matematica Mexicana",

issn = "1405-213X",

publisher = "Sociedad Matematica Mexicana",

number = "2",

}

TY - JOUR

T1 - Collapsibility and homological properties of I -contractible transformations

AU - Espinoza, Jesús F.

AU - Frías-Armenta, Martín Eduardo

AU - Hernández-Hernández, Héctor A.

PY - 2022/7

Y1 - 2022/7

N2 - The family of I-contractible graphs and contractible transformations was defined by A. Ivashchenko in the mid-90s. In this paper we study the collapsibility and homological properties of the clique complex associated to I-contractible graphs. We show that for any graph in a special subfamily of the I-contractible graphs (the strong I-contractible ones) its clique complex is collapsible. Moreover, we present an algorithm that allows us to verify if any graph is strong I-contractible, as well as an algorithm to delete those vertices whose open neighborhood is also strong I-contractible. Finally, we show how to use these algorithms to compute the persistent homology of an arbitrary Vietoris–Rips complex for applications in topological data analysis.

AB - The family of I-contractible graphs and contractible transformations was defined by A. Ivashchenko in the mid-90s. In this paper we study the collapsibility and homological properties of the clique complex associated to I-contractible graphs. We show that for any graph in a special subfamily of the I-contractible graphs (the strong I-contractible ones) its clique complex is collapsible. Moreover, we present an algorithm that allows us to verify if any graph is strong I-contractible, as well as an algorithm to delete those vertices whose open neighborhood is also strong I-contractible. Finally, we show how to use these algorithms to compute the persistent homology of an arbitrary Vietoris–Rips complex for applications in topological data analysis.

KW - Collapsible graph

KW - Contractible transformations

KW - Persistent homology

KW - Vietoris–Rips complex

UR - http://www.scopus.com/inward/record.url?scp=85132599852&partnerID=8YFLogxK

U2 - 10.1007/s40590-022-00434-7

DO - 10.1007/s40590-022-00434-7

M3 - Artículo

AN - SCOPUS:85132599852

SN - 1405-213X

VL - 28

JO - Boletin de la Sociedad Matematica Mexicana

JF - Boletin de la Sociedad Matematica Mexicana

IS - 2

M1 - 42

ER -

Collapsibility and homological properties of I -contractible transformations

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this