Graphs generated from minimal sets of finite point-set topologies
Ketai Chen, Jared DeLeo, Owen Henderschedt · 2025
Read Graphs generated from minimal sets of finite point-set topologies by Ketai Chen, Jared DeLeo, Owen Henderschedt (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-2503-22490.txt.
Introduction
Ketai Chen, Jared DeLeo, and Owen Henderschedt join two old lines of graph theory in one frame. Their 2025 paper starts from finite topologies, ways of saying which sets of points count as open. From each such layout they build a graph, with points as nodes.
Two points are linked when their smallest containing sets overlap, read through the lens of how points can be told apart. Each grade of telling apart gives its own class of graphs. The chain of classes links and extends two classic results, one on containment graphs and one on upper bound graphs. The authors present the frame as a clean, shared way to see both results.
Catalog record
| CREATOR | Ketai Chen, Jared DeLeo, Owen Henderschedt |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22490
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graphs generated from minimal sets of finite point-set topologies Thanks: K. Chen: Department of Mathematics and Statistics, Auburn University. [email protected] Thanks: J. DeLeo: Department of Mathematics and Statistics, Auburn University. [email protected] Thanks: O. Henderschedt: Department of Mathematics and Statistics, Auburn University. [email protected] Ketai Chen, Jared DeLeo, Owen Henderschedt Abstract . In 1985, Golumbic and Scheinerman established an equivalence between comparability graphs and containment graphs—graphs whose vertices represent sets, with edges indicating set containment. A few years earlier, McMorris and Zaslavsky characterized upper bound graphs—those derived from partially ordered sets where two elements share an edge if they have a common upper bound—by a specific edge clique cover condition. In this paper, we introduce a unifying framework for these results using finite point-set topologies. Given a finite topology, we define a graph whose vertices correspond to its elements, with edges determined by intersections of their minimal containing sets, where intersection is understood in terms of the topological separation axioms. This construction yields a natural sequence of graph classes—one for each separation axiom—that connects and extends both classical results in a structured and intuitive way. 1. Introduction Given a partially ordered set (poset) P=(X,\leq) , one can construct many graphs which have been of interest in extremal set theory and graph theory. Among the most famous is the comparability graph of P which is the graph whose vertices are X and x,y\in X are adjacent if x\leq y or y\leq x . In general, we say a graph G=(V,E) is a comparability graph if it arises from some poset P=(V,\leq) . There are many graph-theoretic characterizations for comparability graphs including graphs which are transitively orientable , that is, there exists an orientation of G such that if x\to y and y\to z , then x\to z . This orientation can be easily obtained from the comparability graph of a poset by orienting x\to y if x\leq y . Comparability graphs are both subclasses and superclasses of other well-known and actively researched graph classes. Subclasses include complete graphs, bipartite graphs, permutation graphs, threshold graphs, and co-graphs ( P_{4} -free); see [ 5 , 15 ] . Superclasses include perfect graphs and word-representable graphs; see [ 3 , 11 ] . In what may seem like a different context, a graph G=(V,E) is a \Sigma -containment graph if there exists a family of sets \Sigma such that for each v_{i}\in V(G) , there exists a corresponding S_{i}\in\Sigma such that v_{i}v_{j}\in E(G) if and only if S_{i}\subset S_{j} or S_{j}\subset S_{i} . In [ 7 ] , M. Golumbic and E. Scheinerman proved that the two classes of graphs are, in fact, equivalent. Theorem 1.1 ( [ 7 ] ) . A graph is a comparability graph if and only if it is a containment graph. To see one direction of this theorem, for each S_{i},S_{j}\in\Sigma with S_{i} and S_{j} adjacent in G , we let S_{i}\leq S_{j} if S_{i}\subset S_{j} , or, in terms of an orientation we can orient S_{i}\to S_{j} . To see the other direction of this characterization, one can construct a set system \Sigma by associating for each element x of a poset P=(X,\leq) , the set S(x)=\{y:y\leq x\} . Another lesser-known graph obtained from a poset P=(X,\leq) is the upper bound graph of P . Like the comparability graph of P , this graph also has vertex set X but x,y\in X are adjacent if and only if there exists some z\in X with x\leq z and y\leq z . If x\leq y , i.e. the edge xy exists in the comparability graph of P , then y satisfies the conditions for z , as y is a common upper bound for x and y . Hence, the edges in an upper bound graph of P can be obtained by taking the edges of the comparability graph of P and adding edges. This notion of additional edges will be at the heart of our paper. Once again, in what may seem like a shift in direction, given a graph G=(V,E) , we say v\in V(G) is a simplicial vertex if its closed neighborhood, N[v] , induces a clique (a complete subgraph). We say a graph G=(V,E) is an edge-simplicial graph if there exists a collection of cliques that cover the edges of G such that every clique contains a simplicial vertex. Note that this definition of edge-simplicial graphs is equivalent to requiring every vertex to either be a simplicial vertex or to have a neighbor which is a simplicial vertex. These graphs are also equivalent to the class of graphs whose clique edge-cover number equals its clique vertex-cover number. These parameters are defined as the minimum number of cliques in a graph required to cover every edge (vertex). We will discuss edge-simplicial graphs in more detail in Section 5 . In [ 13 ] , McMorris and Zaslavsky in fact, showed that the class of edge-simplicial graphs are equivalent to upper bound graphs. Theorem 1.2 ( [ 13 ] ) . A graph is an upper bound graph if and only if it is an edge-simplicial graph. The goal of this paper is to unify these classical results and extend them both in terms of graphs generated from a poset and graphs with a clique-like structure (as seen with edge-simplicial graphs). To do this, we will soon define a sequence of six graph classes \mathcal{G}_{0},\hskip 2.84544pt\mathcal{G}_{1},\hskip 2.84544pt\mathcal{G}_{2},\hskip 2.84544pt\mathcal{G}_{3^{\prime}},\hskip 2.84544pt\mathcal{G}_{3^{\prime\prime}},\text{ and }\hskip 2.84544pt\mathcal{G}_{4} whose definitions we deliberately hold off on giving until Section 2 . These graph classes and the framework used to extend the notions of Theorem 1.1 and Theorem 1.2 are built using finite topologies, which will require some further definitions. Before giving those, we first extend the notion of comparability graphs and upper bound graphs by introducing three additional new graphs obtained from a poset. Let P=(X,\leq) be a poset. The half-closed upper bound graph of P is the graph whose vertices are X and x,y\in X are adjacent if and only if there exists a,b\in X such that a\leq x , a\leq b , and y\leq b and there exists \alpha,\beta\in X such that \alpha\leq y , \alpha\leq\beta , and x\leq\beta . In words, to be adjacent, two elements of a poset do not necessarily need to have a common upper bound anymore, but rather they each need a lower bound ( a , or \alpha ) which together with x or y have a common upper bound ( b or \beta ). If we relax the requirement of half-closed upper bound graphs to require either that there exists a,b\in X such that a\leq x , a\leq b , and y\leq b or there exists \alpha,\beta\in X such that \alpha\leq y , \alpha\leq\beta , and x\leq\beta , then we obtain the fully-closed upper bound graph of P . Finally, the extended-closed upper bound graph of P is the graph whose vertices are X and x,y\in X are adjacent if and only if there exists a,b,c\in X such that a\leq x , b\leq y , a\leq c and b\leq c . Given a poset P=(X,\leq) , as we have mentioned, the upper bound graph of P can be obtained from the comparability graph of P by adding