Containment Graphs, Posets, and Related Classes of Graphs

Edward R. Scheinerman; Martin Charles Golumbic

arxiv: 1907.07414 · v1 · pith:MBUM7BMAnew · submitted 2019-07-17 · 💻 cs.DM · math.CO

Containment Graphs, Posets, and Related Classes of Graphs

Martin Charles Golumbic , Edward R. Scheinerman This is my paper

Pith reviewed 2026-05-24 20:12 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords containment graphscontainment posetsset representationsintersection graphsoverlap graphsgraph class characterizationsiso-oriented boxesposet representations

0 comments

The pith

Classes of graphs and posets are characterized by exact containment representations using sets from a given family Z.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a Z-containment graph by assigning each vertex a set from family Z such that adjacency holds exactly when one set contains the other. It defines a Z-containment poset similarly, with the order relation matching strict containment. The central results characterize which poset and graph classes admit such representations for particular set families, including iso-oriented boxes in d-space. The characterizations are extended to injective versions where all assigned sets are distinct. Parallel results are given for intersection, overlap, and disjointedness classes, while strong containment classes are shown to lack any characterization theorem.

Core claim

A graph G is a Z-containment graph when vertices receive sets from Z so that two vertices are adjacent precisely if one set contains the other. A poset P is a Z-containment poset when the order holds precisely under set containment. The paper characterizes the classes of posets and graphs that possess these representations for specific Z, extends the results to injective containment, supplies analogous characterizations for intersection, overlap, and disjointedness classes, and proves that no characterization theorem exists for strong containment classes.

What carries the argument

The Z-containment representation, equating edges or order relations exactly with containment between assigned sets from family Z.

If this is right

Containment graphs formed by iso-oriented boxes in d-dimensional space form a well-defined and characterizable class.
Injective containment classes of graphs and posets admit the same style of characterizations as the non-injective versions.
Intersection, overlap, and disjointedness classes of graphs receive parallel representation characterizations.
Strong containment classes of graphs admit no characterization theorem of the same form.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The characterizations may yield recognition algorithms for the corresponding geometric graph classes.
The containment framework connects representation theorems across different geometric relations.
Similar results could be sought for additional set families such as disks or axis-aligned polygons.

Load-bearing premise

The target classes must permit an assignment of sets from the chosen family Z such that containment holds exactly when the edge or order relation is present, with no extra containments forced by the geometry of the sets.

What would settle it

A graph or poset that satisfies the abstract definition of a Z-containment class yet admits no assignment of sets from Z that realizes the edges or relations without introducing extraneous containments.

Figures

Figures reproduced from arXiv: 1907.07414 by Edward R. Scheinerman, Martin Charles Golumbic.

read the original abstract

In this paper, we introduce the notion of the containment graph of a family of sets and containment classes of graphs and posets. Let $Z$ be a family of nonempty sets. We call a (simple, finite) graph G = (V, E) a $Z$-containment graph provided one can assign to each vertex $v_i \in V $ a set $S_i \in Z$ such that $v_i v_j \in E$ if and only if $S_i \subset S_j$ or $S_j \subset S_i$ . Similarly, we call a (strict) partially ordered set $P = (V, <)$ a $Z$-containment poset if to each $v_i \in V $ we can assign a set $S_i \in Z$ such that $v_i < v_j$ if and only if $S_i \subset S_j$. Obviously, $G$ is the comparability graph of $P$. We give some basic results on containment graphs and investigate the containment graphs of iso-oriented boxes in $d$-space. We present a characterization of those classes of posets and graphs that have containment representations by sets of a specific type, and we extend our results to ``injective'' containment classes. After that we discuss similar characterizations for intersection, overlap, and disjointedness classes of graphs. Finally, in the last section we discuss the nonexistence of a characterization theorem for ``strong'' containment classes of graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper sets up Z-containment graphs and posets and supplies characterizations for specific families like iso-oriented boxes plus a non-existence result for strong containment.

read the letter

Colleague, what you need to know is that this paper introduces containment graphs and posets based on a family Z of sets, where the graph edges or poset relations correspond exactly to containment between the assigned sets. It then characterizes the classes that admit such representations for families like iso-oriented boxes, extends the results to injective containment, compares them to intersection and overlap classes, and proves that no such characterization exists for strong containment. The paper does a good job of setting up these notions cleanly and showing how they relate to comparability graphs. The characterizations provide a way to organize known graph classes under this representation lens, and the non-existence result is a useful stopping point. It stays within the standard definition of exact representation without introducing extra containments from the set geometry. The work is mostly theoretical and classificatory. It builds directly on intersection graph ideas but focuses on containment instead. No major inconsistencies or hidden assumptions stand out from the description. A minor limitation is the lack of any discussion on how to recognize these classes in practice or any complexity analysis, though that may be outside the paper's scope. The citation pattern seems appropriate for the field. This paper is for people working in discrete mathematics, particularly those interested in graph representations and posets. A reader who wants to see how containment fits alongside other set-based graph classes will get value from the framework and the boundary results. It shows clear thinking on the topic and honest engagement with the literature on these representations. I think it deserves to go to peer review so the details of the characterizations can be checked.

Referee Report

0 major / 2 minor

Summary. The paper defines Z-containment graphs (edges iff mutual containment of assigned sets from family Z) and Z-containment posets (relations iff containment), notes that the graph is the comparability graph of the poset, gives basic results, characterizes the classes admitting representations by iso-oriented boxes in d-space, extends the results to injective containment, provides analogous characterizations for intersection/overlap/disjointedness classes, and proves non-existence of a characterization theorem for strong containment classes.

Significance. If the stated characterizations hold, the work supplies a systematic treatment of containment representations that complements existing intersection-graph theory and supplies both positive classification results (for boxes and related families) and a negative result (for strong containment). The injective extension and the discussion of related classes (intersection, overlap, disjointedness) broaden the scope.

minor comments (2)

[Abstract] Abstract: 'disjointedness' appears to be a typographical variant of the standard term 'disjointness'; confirm the intended terminology in the body.
[Abstract] Abstract: the phrase 'Obviously, G is the comparability graph of P' is correct by the given definitions but could be stated once in the body rather than repeated if the paper re-derives it.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the manuscript. The description accurately reflects the paper's contributions on Z-containment graphs and posets, including characterizations for iso-oriented boxes, the injective case, related intersection/overlap/disjointedness classes, and the nonexistence result for strong containment. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces standard biconditional definitions for Z-containment graphs and posets (edge/relation holds iff one set contains the other) and derives characterizations for specific families such as iso-oriented boxes in d-space, plus extensions to injective cases and non-existence results for strong containment. These steps rest on explicit set assignments and geometric properties of Z rather than any fitted parameter renamed as prediction, self-citation chain, or self-definitional reduction. The central claims are independent mathematical statements about which poset/graph classes admit exact representations; no load-bearing step collapses to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The work rests on standard definitions from set theory and order theory; no free parameters are introduced and the only invented entities are the new containment classes themselves.

axioms (2)

standard math Graphs are simple and finite
Explicitly stated in the definition of G = (V, E).
standard math Posets are strict partial orders
Stated in the definition of the containment poset P = (V, <).

invented entities (1)

Z-containment graph no independent evidence
purpose: To represent graphs via set containment relations
Newly defined concept whose properties are investigated in the paper.

pith-pipeline@v0.9.0 · 5805 in / 1300 out tokens · 41899 ms · 2026-05-24T20:12:31.024496+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

B~GE, C. 1973. Graphs and Hypergraphs. North-Holland. Amsterdam

work page 1973
[2]

BUNEMAN, P. 1974. A characterization of rigid circuit graphs. Discrete Math. 9: 205-212

work page 1974
[3]

DUSHNIK, 9. Br E. W. MILLER. 1941. Partially ordered sets. Am. J. Math. 63: 600-610

work page 1941
[4]

PNUELi & A

EVEN, S., A. PNUELi & A. LEMPEL. 1972. Permutation graphs and transitive graphs. J. Ass. Comput. Mach. 19: 400-410

work page 1972
[5]

GAVRIL, F. 1974. The intersection graphs of subtrees of a tree are exactly the chordal graphs. J. Comb. Theory B 16: 47-56

work page 1974
[6]

GILMORE, P. C. & A. J. HOFFMAN. 1964. A characterization of comparability graphs and of interval graphs. Can. J. Math. 16: 539-548

work page 1964
[7]

G~LUMBIC, M. C. 1977. Comparability graphs and a new matroid. J. Comb. Theory B 22: 68-90

work page 1977
[8]

G~LUMBIC, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press. New York

work page 1980
[9]

GOLUMBIC, M. C. 1984. Containment graphs and intersection graphs. Invited lecture. NATO Advanced Institute on Ordered Sets, Banff, Canada, May, 1984. IBM Israel Scientific Center. Tech. Rep. 88.135

work page 1984
[10]

GOLUMBIC, M. C., D. ROTEM & J. URRUTIA. 1983. Comparability graphs and intersection graphs. Discrete Math. 43: 37-46

work page 1983
[11]

HIRAGUCHI, T. 1951. On the dimension of partially ordered sets. Sci. Rep. Kanazawa Univ. 1 : 77-94. 204 ANNALS NEW YORK ACADEMY OF SCIENCES

work page 1951
[12]

ORE, 0. 1962. The Theory of Graphs, Sec. 10.4. Am. Math. SOC. Colloq. Pub. 38. Provi-

work page 1962
[13]

LEMPEL & S

PNUELI, A,, A. LEMPEL & S. EVEN. 1971. Transitive orientation of graphs and identifica-

work page 1971
[14]

SCHEINERMAN, E. R. 1984. Intersection classes and multiple intersection parameters of

work page 1984
[15]

SCHEINERMAN, E. R. 1985. Characterizing intersection classes of graphs. Discrete Math

work page 1985
[16]

T., JR., J

TROTTER, W. T., JR., J. I. MOORE & D. P. SUMNER. 1976. The dimension of a compara-

work page 1976
[17]

YANNAKAKIS, M. 1982. The complexity of the partial order dimension problem. SIAM J. dence, R.1. tion of permutation graphs. Can. J. Math. 23: 16CL175. graphs. Ph.D. dissertation. Princeton Univ., Princeton, N.J. bility graph. Proc. Am. Math. SOC. 60: 35-38. Algebraic Discrete Methods 3: 351-358

work page 1982

[1] [1]

B~GE, C. 1973. Graphs and Hypergraphs. North-Holland. Amsterdam

work page 1973

[2] [2]

BUNEMAN, P. 1974. A characterization of rigid circuit graphs. Discrete Math. 9: 205-212

work page 1974

[3] [3]

DUSHNIK, 9. Br E. W. MILLER. 1941. Partially ordered sets. Am. J. Math. 63: 600-610

work page 1941

[4] [4]

PNUELi & A

EVEN, S., A. PNUELi & A. LEMPEL. 1972. Permutation graphs and transitive graphs. J. Ass. Comput. Mach. 19: 400-410

work page 1972

[5] [5]

GAVRIL, F. 1974. The intersection graphs of subtrees of a tree are exactly the chordal graphs. J. Comb. Theory B 16: 47-56

work page 1974

[6] [6]

GILMORE, P. C. & A. J. HOFFMAN. 1964. A characterization of comparability graphs and of interval graphs. Can. J. Math. 16: 539-548

work page 1964

[7] [7]

G~LUMBIC, M. C. 1977. Comparability graphs and a new matroid. J. Comb. Theory B 22: 68-90

work page 1977

[8] [8]

G~LUMBIC, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press. New York

work page 1980

[9] [9]

GOLUMBIC, M. C. 1984. Containment graphs and intersection graphs. Invited lecture. NATO Advanced Institute on Ordered Sets, Banff, Canada, May, 1984. IBM Israel Scientific Center. Tech. Rep. 88.135

work page 1984

[10] [10]

GOLUMBIC, M. C., D. ROTEM & J. URRUTIA. 1983. Comparability graphs and intersection graphs. Discrete Math. 43: 37-46

work page 1983

[11] [11]

HIRAGUCHI, T. 1951. On the dimension of partially ordered sets. Sci. Rep. Kanazawa Univ. 1 : 77-94. 204 ANNALS NEW YORK ACADEMY OF SCIENCES

work page 1951

[12] [12]

ORE, 0. 1962. The Theory of Graphs, Sec. 10.4. Am. Math. SOC. Colloq. Pub. 38. Provi-

work page 1962

[13] [13]

LEMPEL & S

PNUELI, A,, A. LEMPEL & S. EVEN. 1971. Transitive orientation of graphs and identifica-

work page 1971

[14] [14]

SCHEINERMAN, E. R. 1984. Intersection classes and multiple intersection parameters of

work page 1984

[15] [15]

SCHEINERMAN, E. R. 1985. Characterizing intersection classes of graphs. Discrete Math

work page 1985

[16] [16]

T., JR., J

TROTTER, W. T., JR., J. I. MOORE & D. P. SUMNER. 1976. The dimension of a compara-

work page 1976

[17] [17]

YANNAKAKIS, M. 1982. The complexity of the partial order dimension problem. SIAM J. dence, R.1. tion of permutation graphs. Can. J. Math. 23: 16CL175. graphs. Ph.D. dissertation. Princeton Univ., Princeton, N.J. bility graph. Proc. Am. Math. SOC. 60: 35-38. Algebraic Discrete Methods 3: 351-358

work page 1982