Containment orders – a lifelong journey

Abstract

Mathematical explorations steer us through fields and forests of applications where science and computing meet discrete structures and combinatorics. Today’s excursion takes us on one of the speaker’s favorite journeys in the world of algorithmic graph theory – containment orders, treelike orders and their comparability graphs.

Keywords:

• Comparability graphs
• containment graphs
• ordered sets
• posets
• trivially perfect graphs paths in a tree
• CPT graphs

1 Introduction

It is a great privilege for me to be speaking to you today about one of my favorite journeys in the world of algorithmic graph theory: containment orders and their comparability graphs. Mathematical explorations take us through fields and forests of applications where science and computing meet discrete structures and combinatorics. Today’s excursion began for me with a course in lattice theory at the Pennsylvania State University in early 1969, and with a flashback to an ancient collaboration on ordered sets at the University of Michigan in 1941 before I was born. Those 28 years of ancient history, on mathematical properties of the comparability graphs of ordered sets, led to 28 years of middle history as research expanded into algorithmic aspects with hundreds of newly published results by 1997. Our navigator then guides us into the next 28 years of recent history on classes of containment graphs. We have now arrived to the year 2024. Let us begin.

Look at the diagram of circles in Figure 1. Some of the circles are pairwise disjoint, others contain another circle, and some pairs overlap without any containment relation. I’ve drawn one of my favorite paintings, Several Circles by Wassili Kandinsky (1926). You can find the original at the Guggenheim Museum in New York City. When I first saw it I thought to myself, “Oh my gosh, this is what we graph theorists do! We look at intersecting patterns of circles and we characterize their mathematical properties.” But I don’t think that Kandinsky had this in mind when he painted it – he just enjoyed painting, so we would enjoy his painting.

Fig. 1 Artwork by the author, inspired by the painting Several Circles (Einige Kreise) by Wassily Kandinsky, 1926 at the Guggenheim Museum in New York City.

Containment of one disk inside another defines an order between them. Taking all containment relationships in the whole collection gives us a mathematical structure called a circle order. Had Kandinsky painted rectangles instead of circular disks, we would have rectangle containment orders. Similarly, if I were to draw paths in a tree, we might be motivated to study containment orders of paths in a tree. And indeed I have!

In this lecture, we will explore the many aspects of containment orders and their comparability graphs. We start by reminding ourselves of these basic notions.

2 Ordered sets

2.1 Basic definitions

An ordered set is a set of elements arranged in a hierarchy. The hierarchy allows us to distinguish between pairs of elements that are comparable – one is above the other, and pairs that are incomparable – neither is above the other.

Formally, an ordered set $P=(X,\prec )$ is a structure consisting of a non-empty set X of elements and a binary relation $\prec$ on X which is irreflexive, transitive and therefore asymmetric.

• irreflexive: $x\nprec x$, i.e. no element is related to itself

• transitive: if $x\prec y$ and $y\prec z$ then $x\prec z$

• asymmetric: if $x\prec y$ then $y\nprec x$

Ordered sets are also known as partially ordered setsor posets for short. We often call X the ground set of the order P. Two elements $x,y\in X$ are comparable in P if $x\prec y$ or $y\prec x$; otherwise x and y are incomparable which we denote $x\parallel y$. We say that y covers x or x is covered by y, if $x\prec y$ and there is no z with $x\prec z\prec y$. An element is minimal if it covers no other element, and is maximal if it is not covered by any other element.

An ordered set is often depicted by its cover diagram, often called a Hasse diagram, a hierarchical drawing with a downward edge from y to x whenever y covers x. Relations implied by transitivity are not drawn.

Example 1.

The cover diagram of an order. Figure 2 shows the cover diagram of an order whose comparabilities are the covers $u\prec v,v\prec w,w\prec y,u\prec x,x\prec y$ and the transitivities $u\prec w,v\prec y,u\prec y$. The element u is minimal and the element y is maximal. Figure 3 shows the order called the 5-crown which has 5 minimal elements and 5 maximal elements.

Fig. 2 The cover diagram of an order with 5 elements.

Fig. 3 The 5-crown order.

A linear order (or total order or chain) is one with no incomparabilities, and an antichain is an order with no comparabilities. The dual of the ordered set $P=(X,\prec )$ is the order $P^d=(X,{\prec }^d)$ with $x\prec y\iff y{\prec }^{d}x$. Thus, by flipping a cover diagram for $P=(X,\prec )$ upside down, we obtain a cover diagram for its dual $P^d=(X,{\prec }^d)$.

Two (complementary) graphs are naturally associated with the order $P=(X,\prec )$. The comparability graph $G=(X,E)$ of P has edge-set $E=\left\{\mathit{\text{xy}}\right|x\prec y\text{or}y\prec x\}$, and the incomparability graph $\overline{G}=(X,\overline{E})$ of P has edge-set $\overline{E}=\left\{\mathit{\text{xy}}\right|x\parallel y\}$. Figure 4 shows an order P, its comparability graph G, and its incomparability graph $\overline{G}$. The incomparability graph of an order is often called a cocomparability graph because it is the graph complement of the comparability graph of an order.

Fig. 4 An order P, its comparability graph G, and its incomparability graph $\overline{G}$.

Comparability graphs are precisely those graphs that admit a transitive orientation (TRO) of their edge-sets. A graph $G=(V,E)$ is transitively orientable if there exists an orientation F of its edges such that for all $x,y,z\in V$, $$\mathit{\text{xy}}\in F\text{and}\mathit{yz}\in F\text{implies}\mathit{xz}\in F.$$

Such a transitive orientation F is a strict partial order on V. Figure 5 shows a transitive orientation F of the graph G in Figure 4. Not all graphs are transitively orientable, see Figure 6.

Fig. 5 A transitively oriented graph.

Fig. 6 Four graphs which are not transitively orientable.

A comparability graph can have several different transitive orientations, so there may be several different orders with the same comparability graph. A property of an ordered set is said to be a comparability invariant if either all orders with a given comparability graph have that property, or none have that property. For example, the property of having a unique maximal element is not a comparability invariant, as seen by transitively orienting the edges of a 3-path $a\to b\leftarrow c$ versus $a\leftarrow b\to c$. The property of being a linear order is comparability invariant since every transitive orientation of a complete graph is a linear order. For more reading on comparability graphs and orders, see [16, 24, 30].

Commentary. When did I first get interested in ordered sets?

Answer: See Figure 7.

Fig. 7 When I was 21, it was a very good year.

2.2 Containment orders

Let $\mathcal{S}=\left\{S_j\right\}$ be a collection of subsets of a set S. For example, $\mathcal{S}$ might be a collection of Kandinsky disks in the plane, or intervals on the real line, or subtrees of a tree. The containment order $P=(X,\prec )$ of $\mathcal{S}$ will have elements $X=\left\{x_j\right\}$ corresponding to the subsets, and $x_i\prec x_{\mathcal{l}}\iff S_i\subset S_{\mathcal{l}}$, that is, precisely when $S_i$ is properly contained in $S_{\mathcal{l}}$. The containment graph of $\mathcal{S}$ is simply the comparability graph $G=(X,E)$ of P which has edge set $E=\left\{\mathit{\text{xy}}\right|x\prec y\text{or}y\prec x\}$.

Example 2.

Interval containment graphs and orders. Figure 5 shows a set of intervals $\mathcal{I}$ on the real line whose containment order is F.

We will see a characterization of interval containment orders in Theorem 5.

Generalizing from intervals on a line to other representations, researchers have studied the containment orders of rectilinear boxes in ${\mathbb{R}}^k$, arcs on a circle, unit balls in 3-space (sphere orders), paths in trees (CPT orders), and so on. In the most general case, however, we have a theorem stating that every order P is the containment order of a collection of substars of a star. This leads to a similar theorem for comparability graphs, which we state as follows.

Theorem 3.

The following conditions are equivalent:

1. G is a containment graph;

2. G is a comparability graph;

3. G is a containment graph of subtrees of a tree, in fact, of substars of a star T.

Proof.

[23]: $(i)\Rightarrow (\mathit{\text{ii}})$. Let G be the containment graph with x_j assigned to a set S_j. Define an orientation F of G by $x_i{x}_{\mathcal{l}}\in F\iff S_i\subset S_{\mathcal{l}}$. Clearly, F is transitive, so G is a comparability graph.

$(\mathit{\text{ii}})\Rightarrow (\mathit{\text{iii}})$. Let F be a transitive orientation of G. Let T be a star with central vertex z and pendant vertices numbered $1,\dots ,n$. To each vertex x_j we associate the subtree T_j induced by the central vertex z and those pendant vertices i such that $x_i{x}_j\in F$. Observe that $T_i\subset T_j\iff x_i{x}_j\in F$. Hence, the assignment of T_j to x_j gives a containment representation of G.

$(\mathit{\text{iii}})\Rightarrow (i)$. Trivial. □

Remark 4.

Since the transitive orientation F of G was chosen arbitrarily in the proof of $(\mathit{\text{ii}})\Rightarrow (\mathit{\text{iii}})$, we see that every transitive orientation of a comparability graph represents a containment order between a collection of substars of a star.

3 Ancient history (1941–1968)

In 1941, Ben Dushnik and Edwin W. Miller published their seminal paper, Partially Ordered Sets [7], in which they defined the concept of the dimension of a poset.¹ A realizer of an order $P=(V,\prec )$ is a collection of linear orders $L_1,L_2,\dots ,L_k$ such that $x\prec y$ if and only if $x{\prec }_{i}y$ for all $i=1,2,\dots ,k$. That is, $P=L_1\cap L_2\cap \cdots \cap L_k$. Every poset can be obtained as the intersection of some number of linear orders. The size of the smallest possible realizer of P is called the dimension of P and is denoted $\mathrm{\text{dim}}P$. Such a realizer is called a minimum realizer of P. Figure 8 shows a 3-realizer of an order and its comparability graph whose edges are implicitly transitively oriented downward. However, it is not a minimal realizer. As an exercise, find a 2-realizer for it.

Fig. 8 A 3-realizer of an order with transitively ordered comparability graph.

In the case of dimension 2, we have the following ancient and still interesting result regarding containment graphs.

Theorem 5

(Dushnik and Miller, 1941). The following conditions are equivalent for an order P:

1. P is a containment order of intervals on line;

2. P has dimension at most 2;

3. the complement $\overline{G}$ of its comparability graph G is also a comparability graph.

This theorem shows that the order theoretic property of being dimension 2 is comparability invariant. However, it took 35 years until a proof was found showing the general result that the parameter dimension for any k is a comparability invariant [31]. The result is stated as follows.

Theorem 6

(Trotter, Moore, Sumner, 1976). If two orders P and $P\prime$ have the same comparability graph, then $\mathrm{\text{dim}}P$ = $\mathrm{\text{dim}}P\prime$.

In this way, we can unambiguously define the order dimension $\mathrm{\text{dim}}G$ of a comparability graph G as (the common) value $\mathrm{\text{dim}}F$ for any of its transitive orientations F. A proof of Theorem 6 can be found in [24, 30].

The graph theoretic analogue of Theorem 5 can now be stated.

Theorem 7.

The following conditions are equivalent:

1. A graph G is the containment graph of intervals on line;

2. G is the comparability graph of an order of dimension at most 2;

3. G and its complement $\overline{G}$ are both comparability graphs.

In 1989, Golumbic and Scheinerman [23] generalized interval containment to the containment of rectilinear boxes in d-dimensional Euclidean space (sides parallel to the axes). Their result is stated here.

Theorem 8

(Golumbic and Scheinerman, 1989). Let P be an order. The following conditions are equivalent:

1. P is the containment order of boxes in d-space;

2. P is the intersection of d interval containment orders;

3. the dimension of P is at most 2d.

Corollary 9.

The following conditions are equivalent:

1. G is the containment graph of boxes in d-space;

2. the order dimension of G is at most 2d;

3. every transitive orientation of G is a containment order of boxes in d-space.

Algorithmically, Yannakakis [34] showed that deciding whether $\mathrm{\text{dim}}P\le d$ is NP-complete for every fixed $d\ge 3$. Therefore we have the following.

Corollary 10.

The problem of deciding whether an arbitrary comparability graph is the containment graph of boxes in d-space is NP-complete for any fixed $d\ge 2$.

By Hiraguchi’s theorem (see [30]), $\mathrm{\text{dim}}G\le \lceil n/2\rceil$, therefore, the “box containment dimension” of G is at most $\lceil n/4\rceil$ obtaining the following.

Corollary 11.

Every comparability graph on n vertices is the containment graph of boxes in $\lceil n/4\rceil$-dimensional Euclidean space.

For more reading on order dimension, see [16, 22, 30].

4 Middle history (1969–1996)

4.1 Geometric containment orders

In May 1984, Ivan Rival organized a 2-week NATO Advanced Study Institute on Graphs and Order at Banff, Canada. It was the second of four conferences during the 1980s that he organized, creating what has been described as an “order theory community”. In the same year, the first issue of the journal Order was published with Ivan as editor. Sadly, his life was cut short in the midst of a brilliant career [6].

Many of the people involved in this research community exchanged ideas on containment orders at the conference. In my own lecture, based on [14], I advocated for a broad study of containment graph classes, which prompted a lively discussion. The result was an immediate series of papers on several such classes: sphere orders (Brightwell and Winkler [5]), circle orders and angle orders (Fishburn, Scheinerman, Trotter, Wierman [8–11, 29]), box containment orders (Golumbic and Scheinerman [23]), circular-arc containment graphs (Nirkhe, Masuda, and Nakajima [27]). This continued into the next decade; see the 1998 survey paper by Fishburn and Trotter [12] and the many recent citations to it.

4.2 The comparability graph of a rooted tree

The cover diagram D of an order P may reveal interesting properties. The structure of one of them influences the structure of the other. For example, D is a path if and only if P is a linear order. One might ask, if P is an interval containment order, what properties characterize the structure of D? Or, the opposite type of question, if D is a bipartite graph, what properties characterize the structure of P?

Elliot Samuel Wolk (August 5, 1919–April 18, 2015) asked this very question for D being a forest of rooted trees. In his two papers [32, 33] published in the early 1960s, he characterized the orders for which this is possible. Independently over a decade later, and coming from my interest in perfect graphs, I defined a graph class called trivially perfect graphs [13], whose characterization showed it to be equivalent to Wolk’s graph class. The union of our results is the following.

Theorem 12.

Let $G=(V,E)$ be an undirected graph. The following statements are equivalent:

1. G has a transitive orientation whose cover diagram is a forest of rooted trees;

2. G is trivially perfect, that is, the stability number $\alpha (G_X)$ equals the number of maximal cliques $\mathit{\text{mc}}(G_X)$ for all induced subgraphs G_X of G;

3. G contains no induced subgraph isomorphic to C₄ or P₄;

4. each connected induced subgraph of G has a universal vertex;

5. G can be formed by repeatedly applying these three rules:

   1. add a new isolated vertex,

   2. add a new universal vertex, that is, adjacent to all old vertices,

   3. take the disjoint union of two such graphs.

Wolk [32, 33] showed the implications (i) $\Rightarrow$ (iii) $\Rightarrow$ (iv) $\Rightarrow$ (i); Golumbic [13] showed (ii) $\iff$ (iii); the equivalence (iv) $\iff$ (v) is straightforward to show.

You might wonder, “Why are they called trivially perfect graphs?” I chose this name since it is trivial to show that such a graph is perfect. Let’s see why. Here is the trivial proof:

A graph $G=(V,E)$ is perfect if $\alpha (G_X)=\kappa (G_X)$ for all induced subgraphs G_X of G $(X\subseteq V)$, where $\kappa (G)$ denotes the size of a minimum clique cover of G. It is always the case that the maximum stable set number $\alpha (G)$ is smaller than or equal to $\kappa (G)$, and trivially, $\kappa (G)$ is at most mc(G). In other words, $\alpha (G_X)\le \kappa (G_X)\le \mathit{\text{mc}}(G_X)$. Therefore, if the first term equals the last, then they are all equal, and G is perfect.

Other algorithmic results for trivially perfect graphs can be found in [19].

Commentary. A family tree is not a tree.

In my 60th birthday lecture, Landmarks in algorithmic graph theory [17], I asked a mathematical open question: Can we characterize family trees? An obvious observation is that a family tree is the union of two rooted trees, the “father-of” tree and the “mother-of” tree. See Figure 9. A full characterization and formal treatment of the question seems still to be open.

Fig. 9 A “father-of” rooted tree and a “mother-of” rooted tree.

5 Recent history (1997–2024)

5.1 CPT orders

An order $P=(X,\prec )$ is called a containment order of paths in a tree (CPT for short) if it admits a representation by containment where each element of X corresponds to a path in a tree and for two elements x and y, we have $x\prec y$ if and only if the path corresponding to x is properly contained in the path corresponding to y. Figure 10 shows a CPT representation for the graph C₈ transitively oriented according to containment.

Fig. 10 A CPT representation for the graph C₈.

As we have seen, several classes of orders are known to admit specific containment models, for example, containment orders of circular arcs on a circle [27, 28], containment orders of axis-parallel boxes in ${\mathbb{R}}^d$ [23], or containment orders of disks in the plane [5, 8, 9], to cite just a few. All the aforementioned classes, as well as CPT orders, generalize the class of containment orders of intervals on a line which go back to Dushnik and Miller [7].

In 1984, Corneil and Golumbic observed that a graph G may be the comparability graph of a CPT order, yet a different transitive orientation of G may not necessarily have a CPT representation, (see Golumbic [14]). Figure 11 shows a CPT representation for the 6-wheel W₆. Its central vertex c must be a sink in any CPT representation, for the following reason: In any transitive orienttion, the edges of the outer 6-cycle would have to alternate in their orientation, and by transitivity, this forces the central vertex c to be either a sink or a source. If, however, c would be a source, then its corresponding path P_c in the tree must contain the paths $P_1,P_2,P_3,P_4,P_5,P_6$. Thus, they would be intervals on the path P_c inducing a chordless cycle C₆. This cannot happen since C₆ is not an interval containment graph.

Fig. 11 A CPT representation for the 6-wheel W₆. The central vertex c must be a sink.

This observation, that the CPT property is not a comparability invariant, stands in contrast to dimension, interval orders, unit interval orders, box containment orders, tolerance orders and others which are all comparability invariant. Golumbic and Scheinerman [23] called such classes strong containment order classes.

Recently, interest in CPT orders has been revived and several groups of researchers have considered various aspects of this class [2, 3, 21, 25]. Since CPT orders are not a strong containment class, Alcón, Gudiño and Gutierrez [2] introduced the study of the subclasses dually-CPT and strongly-CPT orders. An order P is called dually-CPT if P and its dual P^d admit a CPT representation. An order P is called strongly-CPT if P and all the orders that share the same underlying comparability graph admit CPT representations. From the definition it is clear that the class of strongly-CPT orders is included in the class of dually-CPT orders. Many families of separating examples are now known between the class of dually-CPT and general CPT orders, however, concerning the strongly and dually-CPT, it was left as an open problem for many years to determine whether the inclusion is strict or if the two classes coincide.

A solution to this question was finally shown by Alcón, Golumbic et al. [1] with the following theorem.

Theorem 13.

An order P is strongly-CPT if and only if it is dually-CPT.

The proof of this result relies on the link between modular decomposition of the underlying comparability graph and its transitive orientations.

Another longstanding question was polynomially bounding the dimension of CPT orders by a parameter of its size. Majumder, Mathew and Rajendraprasad [25] have answered this by showing the following.

Theorem 14.

If an order P admits a CPT model in a host tree T of maximum degree Δ and radius r, then $\mathrm{\text{dim}}(P)\le \mathrm{\text{lg}}\lg \Delta +(\frac{1}{2}+o(1))\text{lglglg}\Delta +\mathrm{\text{lg}}r+\frac{1}{2}\mathrm{\text{lg}}\lg r+\frac{1}{2}\mathrm{\text{lg}}\pi +3$ This bound is asymptotically tight up to an additive factor of $\mathrm{\text{min}}(\frac{1}{2}\text{lglglg}\Delta ,\frac{1}{2}\mathrm{\text{lg}}\lg r)$.

5.2 Partial wheels as CPT graphs

A partial wheel consists of a chordless cycle and a central vertex adjacent to some but not all of the cycle vertices. Since a containment graph must always be a comparability graph, one might ask first (a) which partial wheels have a transitive orientation? and then ask (b) which of those TROs admit a CPT representation? Theorem 15 gives the surprising result that all partial wheels that admit a TRO are CPT. We then move on to characterize the CPT orders whose comparability graph is a partial wheel in Theorem 16. These results provide us with a characterization of the partial wheels for which every transitive orientation is a CPT order.

Theorem 15

(Golumbic and Limouzy, 2021). Let W be a partial wheel. The following conditions are equivalent:

1. W has a transitive orientation,

2. W is a containment graph of paths in a tree,

3. the outer cycle of W is of even length, and either

   1. the central vertex is adjacent to exactly two consecutive outer vertices, or

   2. all maximal sets of consecutive neighbors and of consecutive non-neighbors of the central vertex are of odd length (i.e., cardinality).

Figure 12 illustrates conditions (a) and (b).

Fig. 12 An illustration of conditions (a) and (b).

5.3 When can the central vertex of a partial wheel be a source?

From our previous discussion we have the following:

Full wheels: central vertex x must be a sink.

Partial wheels, case (a): central vertex x must be mixed (1 incoming and 1 outgoing).

Partial wheels, case (b): central vertex x was a sink in our construction, but there are many examples where this does not have to happen – namely, partial wheels where x is a source.

When the central vertex x of a partial wheel is a source, the path P_x contains all the paths of its neighbors, and the induced subgraph of the closed neighborhood $N[x]$ is necessarily an interval containment graph. This leads to many impossible configurations, assisting us to characterize all CPT orders of partial wheels. Figure 13 shows some forbidden induced subgraphs for CPT graphs as a consequence of this observation – the vertices indicated by the pairs of arrows would both have to be sinks, which cannot happen.

Fig. 13 Some forbidden induced subgraphs for CPT graphs. The vertices indicated by pairs of arrows would both have to be sinks, which cannot happen.

Our next result characterizes CPT wheels and partial wheels.

Theorem 16

(Golumbic and Limouzy, 2021). For wheels and partial wheels, the following characterizes their containment orders of paths in a tree.

1. For the full wheel $W_{2k}(k\ge 3)$, the only transitive orientation which is CPT is that with the central vertex as a sink.

2. For an even length partial wheel with the central vertex adjacent to exactly 2 consecutive vertices, there are two transitive orientations and both are CPT.

3. For an even length partial wheel with the central vertex adjacent to exactly 3 consecutive vertices, there are four transitive orientations and all are CPT.

For any other partial wheel W of even length at least 6 satisfying condition (3)(b) of Theorem 15, we have the following:

1. If the gaps of W are all of length 1, then the only transitive orientation which is CPT is that with the central vertex a sink.

2. Otherwise, there are two transitive orientations: with the central vertex either a sink or source, and both are CPT.

As an example of the application of this characterization, we see that the bipartite 8-wheel BW₈ is a CPT graph since by (4) the gaps are all of length 1, and the central vertex must be a sink. The full proof of these results can be found in [21].

5.4 CPT open questions

1. Characterize the CPT graphs and the CPT orders.

2. The same questions for bipartite CPT graphs.

3. 3. For which CPT graphs will all transitive orientations admit CPT representations?

4. For which other comparability graphs will only one TRO be CPT and not its reversal, as in the case of full wheels?

5. Our Theorem 16 on partial wheels characterizes the dually-CPT orders of partial wheels by combining statements (2) and (4) of the theorem. Characterize the dually-CPT orders for other subfamilies.

6 Containment classes of graphs

There are two approaches to investigating classes of containment graphs:

1. Restrict the family of sets Σ to a certain type (such as intervals on a line, paths in a tree) and ask, What is the class obtained as Σ-containment graphs?

2. Begin with a class $\mathcal{C}$ of comparability graphs and ask, Can $\mathcal{C}$ be characterized as a family of Σ-containment graphs or some family of sets Σ?

Up until now, we have been studying instances of approach (A) for a variety of families Σ. We now look at approach (B) following the work of Golumbic and Scheinerman [23].

Spoiler: There are graph classes that do not admit a Σ-containment characterization for any family Σ of sets.

6.1 Which graph classes can be characterized as containment classes?

Our general question is, given a graph class $\mathcal{C}$, when does there exist a family Σ of sets such that $\mathcal{C}$ equals the class of Σ-containment graphs.

Example 17.

The comparability graphs of lattices does not form a containment class.

Why? Observe that a containment graph class must be hereditary (closed under induced subgraphs), since the containment relationship does not change between the remaining vertices. In Figure 14, we see the comparability graph of the lattice of subsets $\varnothing ,\left\{a\right\},\left\{b\right\},\{a,b\}$ ordered by inclusion. It is the diamond graph. Deleting the top vertex {a, b} gives the path graph P₃ which has no transitive orientation as a lattice.

Fig. 14 The lattice of subsets of {a, b}.

From this example, we see that the hereditary property is necessary for any characterization of containment graph classes. We now define two additional necessary properties.

A composition sequence for a class of graphs $\mathcal{C}$ is a (possibly infinite) sequence of graphs $G_1,G_2,G_3,\dots$ such that (1) each $G_i\in \mathcal{C}$, (2) G_i is an induced subgraph of $G_{i+1}$ for all i, (3) if $G\in \mathcal{C}$ then G is an induced subgraph of G_k for some k.

Definition.

A composition sequence is called coherently transitively orientable, provided each graph in the sequence can be transitively oriented so that $x\to y$ in G_i implies $x\to y$ in $G_{i+1}$.

A class of graphs $\mathcal{C}$ is closed under vertex multiplication if whenever $G\prime$ is obtained from some $G\in \mathcal{C}$ by adding false twins to any of the vertices of G, then $G\prime \in \mathcal{C}$.

Golumbic and Scheinerman [23] proved that combining these three conditions characterize containment graph classes.

Theorem 18.

Let $\mathcal{C}$ be a class of comparability graphs. $\mathcal{C}$ is a containment class if and only if

1. $\mathcal{C}$ is hereditary,

2. $\mathcal{C}$ has a coherently transitively orientable composition sequence, and

3. $\mathcal{C}$ is closed under vertex multiplication.

6.2 No characterization of strong containment classes is possible!

Recall that a Σ-containment graph class $\mathcal{C}$ is strong if for every transitive orientation F of $G\in \mathcal{C}$ we have that F is a Σ-containment order. For example, the containment graphs of intervals form a strong containment class, but the containment class of paths in trees is not a strong class.

It would have been very desirable to have a characterization of strong containment classes similar to our characterization of containment classes. However, Golumbic and Scheinerman [23] found that no such characterization is possible. They proved this by showing that there exists two families of sets Σ and $\Sigma \prime$, with the same class of comparability graphs $\mathcal{C}(\Sigma )=\mathcal{C}(\Sigma \prime )$, but where $\mathcal{C}(\Sigma )$ not a strong containment class, and $\mathcal{C}(\Sigma \prime )$ is a strong class.

Acknowledgments

Thank you for allowing me to journey with you today. I invite you to join me on other excursions and personal perspectives on algorithmic graph theory, reasoning about time, constraint-based scheduling, graph classes, and more [4, 15, 18, 20].

Notes

1 Commentary. Dushnik and Miller wrote, “We are indebted to S. Eilenberg for suggestions which enabled us to simplify several proofs and improve the form of several definitions.” Samuel Eilenberg was a renowned expert on algebraic topology, founder of homological algebra, and a non-French Bourbaki. He was on the faculty at Michigan 1940–1946 when they wrote their poset dimension paper. Eilenberg was also my doctoral advisor at Columbia University, and coincidentally, we share the same birthday, just 35 years apart.Dushnik and Miller met as doctoral students at University of Michigan and continued as professors there. Edwin Wilkinson Miller (1905-1942) received his Ph.D. in 1930 defending his dissertation, On subsets of a continuous curve which lie on an arc of the continuous curve, (see [26]). Following his untimely death, the mathematics department established an annual Edwin Wilkinson Miller Award that continues to this day.Ben Dushnik received his Ph.D. in 1931 defending his dissertation, On the Stieltjes integral, which he presented at the 294th regular meeting of the American Mathematical Society held at the Ohio State University on Friday afternoon November 27, 1931. It has been cited more than dozen times. Ben and Edwin were joint Ph.D. advisors of Horace Komm, whose 1943 dissertation was titled Concerning the dimension and the lambda-dimension of a partial order. Ten year later, Ben advised another doctoral student, the famous computer scientist Seymour Ginsburg, pioneer of automata theory, formal language theory, and database theory.