Ex. 17.1

For the Markov graph of Figure 17.8, list all of the implied conditional independence relations and find the maximal cliques.

Soln. 17.1

Recall that a clique is a complete subgraph (every pair of vertices joined by an edge). A clique is called maximal if no other vertices can be added into it and still yields a clique. In the Figure 17.8 the maximal cliques are \(\{X_1, X_2, X_6\}, \{X_3, X_4\}, \{X_5\}\).

We check each pair of vertices and list the implied conditional independence below.

\(X_1 \bot X_3|X_4\)
\(X_1 \bot X_5|X_2, X_6\)
\(X_2 \bot X_3|X_1, X_4, X_6\)
\(X_2 \bot X_4|X_1, X_6\)
\(X_2 \bot X_5|X_1, X_6\)
\(X_3 \bot X_5|\text{rest}\)
\(X_3 \bot X_6|X_1, X_2, X_4\)
\(X_4 \bot X_5|X_1, X_2, X_6\)
\(X_4 \bot X_6|X_1, X_2\)