Generalizations of interval and proper interval graphs for simplicial complexes

Fahimeh Khosh-Ahang Ghasr · 2025

Read Generalizations of interval and proper interval graphs for simplicial complexes by Fahimeh Khosh-Ahang Ghasr (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16722.txt.

Introduction

Fahimeh Khosh-Ahang Ghasr, in a single-author study, extends interval graphs and proper interval graphs from graph theory to simplicial complexes, which are higher-dimensional structures built from points, edges, triangles, and beyond. Interval graphs record overlap patterns of line segments. The generalized families include strong, unit, and closed variants.

Ghasr gives matching combinatorial and algebraic descriptions of these classes and maps how they rank against each other. Known results carry over to higher dimensions, such as closed and proper interval graphs turning out to be the same class. Uses include conditions for sorting certain independence complexes and constructions of special algebraic domains. Forbidden subgraph results add structure.

Catalog record

CREATORFahimeh Khosh-Ahang Ghasr
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16722

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generalizations of interval and proper interval graphs for simplicial complexes Fahimeh Khosh-Ahang Ghasr Abstract . We introduce and investigate generalizations of interval and proper interval graphs to simplicial complexes, including strong interval, unit interval, and under closed variants. Through equivalent combinatorial and algebraic characterizations, we uncover hierarchies among these classes and extend key results to higher dimensions, such as the equivalence of closed and proper interval graphs. These formulations enable significant applications, including finding conditions for the sortability of d d -independence complexes, constructions of normal Cohen-Macaulay domains linked to d d -unit interval graphs, and forbidden subgraph theorems establishing chordality and d d -claw-freeness. Our work advances the connections between graph theory, simplicial complexes, and commutative algebra, offering new insights into the algebraic underpinnings of combinatorial structures. 2010 Mathematics Subject Classification 05C40, 05C75, 05E45, 13H10 1. Introduction and Preliminaries In this paper, we explore connections between graph theory, simplicial complexes, and commutative algebra, focusing on generalizations of interval graphs and their higher-dimensional independence complexes. These structures arise naturally in various applications, including graph algorithms, bioinformatics, and algebraic combinatorics, and have been extensively studied over the past several decades [ 1 , 8 , 11 , 14 , 15 , 20 ] . We begin with some notation and definitions. Throughout, G=(V(G),E(G)) denotes a simple graph on n vertices, d\in\mathbb{N} , and \mathbb{K} is a field. Let \Delta be a pure d -dimensional simplicial complex (briefly, a d -complex) on n vertices, with facet set denoted by \mathcal{F}(\Delta) . We write any subset F=\{i_{1},\dots,i_{r}\} of [n] with 1\leq i_{1}<\dots<i_{r}\leq n as F:i_{1}\dots i_{r} . For an integer 0\leq k\leq d , k -skeleton of \Delta is the simplicial complex whose facets are all k -dimensional faces of \Delta . \Delta is called connected if for every two vertices u and v there is a sequence r_{0},G_{1},r_{1},\dots,r_{s-1},G_{s},r_{s} , with u=r_{0} and v=r_{s} such that for each k with 1\leq k\leq s , r_{k} is a vertex of \Delta and G_{k} is a facet containing r_{k-1} and r_{k} . For a subset U=\{u_{1},\dots,u_{k}\} of V(G) , the induced subgraph of G on U is denoted by G[U] or G[u_{1},\dots,u_{k}] . A clique in G is the vertex set of any complete subgraph, and a maximal clique is one that is maximal under inclusion. A noncut vertex of G is a vertex whose removal doesn’t effect the number of connected components of G . The path and cycle graphs on n vertices are denoted by P_{n} and C_{n} , respectively. An induced cycle of length k in G is formed by distinct vertices x_{1},\dots,x_{k} such that G[x_{1},\dots,x_{k}]\cong C_{k} ; we denote this cycle by (x_{1},\dots,x_{k}) if x_{1}x_{k}\in E(G) and x_{i}x_{i+1}\in E(G) for 1\leq i\leq k-1 . A subset U of V(G) is a d -independent set if every connected component of G[U] has at most d vertices. The union of graphs G and H (with possibly overlapping vertices) is denoted by G\cup H . We associate to G the simplicial complex \Delta_{d}(G) on vertex set V(G) , whose facets are all (d+1) -element subsets U of V(G) such that G[U] is connected. For d=1 , the facet ideal of \Delta_{d}(G) coincides with the edge ideal of G . The independence complex \mathrm{Ind}(G) of G is the simplicial complex whose faces are the independent sets of G (i.e., 1 -independent sets). More generally, the d -independence complex \mathrm{Ind}_{d}(G) has vertices V(G) and faces consisting of all d -independent subsets of V(G) . While the algebraic and combinatorial properties of \mathrm{Ind}(G) have been well-explored, higher independence complexes \mathrm{Ind}_{d}(G) for d\geq 2 are less understood, with recent advances in [ 4 , 5 , 6 ] . Interval graphs, defined as intersection graphs of intervals on a line, form a fundamental class with applications in scheduling, genetics, and beyond [ 11 , 13 , 20 ] . A graph G is an interval graph if its vertices can be labeled by nonempty intervals such that two vertices are adjacent precisely when their intervals intersect. A proper interval graph is one where no interval properly contains another, and a unit interval graph requires all intervals to have the same length. Equivalently, as introduced in [ 14 ] to study binomial edge ideals with quadratic Gröbner bases, a graph G is closed if there exists a labeling [n] of its vertices such that for edges ij and ik with i<j<k , we have jk\in E(G) , and for edges ij and kj with i<k<j , we have ik\in E(G) . There are generalizations of these graphs for simplicial complexes, such as unit interval, closed, under closed, poor closed, etc. [ 1 , 16 ] provide hierarchies of such generalizations. In this work, we study generalization of interval graphs, including strong interval, unit interval and under closed, for simplicial complexes (see Definitions 2.1 ). We establish hierarchies and equivalences among these classes of simplicial complexes in Lemma 2.4 and Theorem 3.1 . These relationships lead to conditions for sortability of d -independence complexes (Corollary 3.2 ), constructions of normal Cohen-Macaulay domains (Corollary 3.3 ), and characterizations of interval graphs (Theorem 3.4 ). Moreover, Theorem 2.6 extends the main result of [ 3 ] to simplicial complexes, showing that closed and proper interval graphs coincide. We also derive forbidden subgraph results, including chordality and claw-freeness (Propositions 4.2 and 4.3 ), culminating in sortability of \mathrm{Ind}_{d}(G) (Corollary 4.4 ) and characterizations of d -unit interval cycles and forests (Corollary 4.6 ). So we extend [ 3 ] ’s result to simplicial complexes and provide new characterizations beyond cycles/forests. 2. Variant of Interval Simplicial Complexes Interval graphs admit natural generalizations to higher-dimensional simplicial complexes, capturing richer combinatorial structures with algebraic implications. We study several such generalizations, including strong interval, unit interval and under closed simplicial complexes, to extend the framework of interval graphs and explore their properties. These definitions, inspired by [ 1 ] , facilitate the study of higher independence complexes and their associated algebras. Definitions 2.1 . (1) \Delta is called a strong interval simplicial complex if there exists a labelling [n] on V(\Delta) and a family \{I_{i}\}_{i\in[n]} of intervals such that for each 1\leq i_{1}<\dots<i_{d+1}\leq n , i_{1}\dots i_{d+1}\in\mathcal{F}(\Delta) if and only if \bigcup_{1\leq k\leq d+1}I_{i_{k}} is an interval. In this case \{I_{i}\}_{i\in[n]} is called an interval representation for \Delta and for each i\in[n] , if I_{i}=[a_{i},b_{i}] , then we set \mathrm{left}I_{i}=a_{i} and \mathrm{right}I_{i}=b_{i} . If all the intervals in an interval representation have unit length, \Delta is called a strong unit interval simplicial complex . If no interval is properly contained in another, \Delta is called a strong proper interval simplicial complex . (2) ( [ 1 , Definition 30] ) \Delta is called a unit interval simplicial complex if there is a labelling [n] on V(\Delta) such that for each facet F:i_{1}\dots i_{d+1} , every integers j_{1},\dots,j_{d+1} with i_{1}\leq j_{1}<\dots<j_{d+1}\leq i_{d+1} form a facet. (3) ( [ 1 , Definition 31] ) \Delta is called a under closed simplicial complex if there is a labelling [n] on V(\Delta) such that for each facet F:i_{1}\dots i_{d+1} , every integers j_{1},\dots,j_{d+1} with j_{1}=i_{1},j_{2}\leq i_{2},j_{d+1}\leq i_{d+1} form a facet. G is called d -strong interval (resp. d -strong unit interval,

Read the complete text