---
tags: FYP
---

# 26/05/2023 Homework

## Dilworth's Theorem [DONE]

> Prove Dilworth's Theorem: *for any partial order, the size of maximal antichain is equal to the size of minimal chain cover*

We will denote $w_P$ as the width of a partial order $P$, $A_P$ as a maximal antichain of $P$, and $C_P$ as a minimal chain cover of $P$. Note that the $w_P = |A_P|$ by definition.

It is easy to see that $|A_P| \leq |C_P|$, as all pairs of elements in antichain is incomparable, no chain can cover two distinct elements of an antichain. Hence, we need at least $|A_P|$ chains to cover $P$.

We will prove $|A_P| \geq |C_P|$ by induction.

Suppose we have partial order $P = (S, <)$. If $|S| = 1$, then it's trivially true. Assume that the property holds for all partial order whose size is less than $|S|$.

Let $a$ be a maximal element in $P$. We take $a$ out and obtain $P' = P - \{a\}$.

### Case 1: $a$ is a free element in $P$

We can form a new antichain $A_{P'} \cup \{a\}$ to form an antichain for $P$. We will prove that this antichain is also maximal.

Suppose this is not maximal, then there exists some other antichain $A$ s.t. it has size of $|A_{P'}| + 2$. There are two cases:
- If $a \in A$, then $A - \{a \}$ is also an antichain for $P'$, but it contradicts that $A_{P'}$ is a maximal antichain of $P'$.
- If $a \not\in A$, then $A$ is also an antichain of $P'$, but it contradicts that $A_{P'}$ is a maximal antichain of $P'$.

In this case, since $a$ is a free element, we can use $\{a\} \cup C_{P'}$ as chain cover for $P$. Note that in this case, $|A_{P'} \cup \{a\}| = |A_{P'}| + 1 \geq |C_{P'}| + 1 = |C_{P'} \cup \{a\}|$

### Case 2: $a$ is not free element

Take some minimal element $b$ from the set $\{x \, | \, x < a\}$. Let $P' = P - \{a, b\}$. Suppose $|A_{P'}| < |A_P|$, then the chains $C_{P'} \cup \{a, b\}$ covers $P$. It is of size $|C_{P'}| + 1 = |A_{P'}| + 1 \leq |A_P|$.

Suppose $|A_{P'}| = |A_P|$. An antichain of $P'$ is also an antichain of $P$. Split $S$ into two different sets $S^+$ and $S^-$, s.t.

$$
S^+ = \{v \, | \, \exists x \in A_{P'}, v > x\} \\
S^- = \{v \, | \, \exists x \in A_{P'}, v < x\}
$$

$S^+ \cup S^- = S$, because for any element $v$, it must be comparable with at least one antichain in $A_{P'}$.

Note that $a \not\in S^-$ and $b \not\in S^+$, because they cannot be part of the antichain $A_{P'}$. Hence, $S^+$ and $S^-$ are strict subsets of $S$. By induction, we can form a chain cover for $S^+$ and $S^-$ such that $\forall v \in A_P$, there exists a chain that includes $v$. Call such chain $C^+_v$ and $C^-_v$ respectively. We can form new chains $C^+_v \cup {v} \cup C^-_v$ for all $v \in A_{P'}$ to cover $P$. Therefore, $|C_P| = |A_{P'}| = |A_P|$.

## Dimension [DONE]

> It is NP-complete to determine if a partial order of has dimension 3 [^1]

[^1]: Yannakakis, Mihalis. The Complexity of the Partial Order Dimension Problem. https://doi.org/10.1137/0603036

### Preliminary

Suppose we have a partial order $P$ over the set $N$. Partition $N$ into two disjoint set $S$ and $S'$, such that there is no edge going from $S'$ and $S$. Let $B(P)$ be a bipartite graph with $N$ as its vertices and $\{[x, y] | x \in S, y \in S', x \text{ and } y \text{ are incomparable} \}$.

Consider a linearization $L$ of $P$. Denote $\bar{L}$ as a bipartite graph with $N$ as its vertices and $\{[x, y] | x \in S, y \in S', (y, x) \in L\}$. We can see that $\bar{L}$ is a subgraph of $B(P)$, because all edges in $\bar{L}$ must also be in $B(P)$.

> ***Property 1:** for any linearization $L$ of $P$, $\bar{L}$ cannot have two independent edges*

We call $[x, y]$ and $[z, w]$ are ***independent edges*** iff the subgraph induced by $x, y, z, w$ only contains those two edges.

***Proof:***

Suppose $\bar{L}$ has independent edges $[x, y]$ and $[z, w]$, where $x, z \in S$ and $y, w \in S'$. By definition of $L$, it contains the arcs $(y, x), (w, z), (x, w), (z, y)$ (The last two arcs is due to the fact that $L$ is a linear order, since $\bar{L}$ does not contain edge $[w, x]$, then it must be the case that $(x, w) \in L$). However, this forms a cycle $x \rightarrow w \rightarrow z \rightarrow y \rightarrow x$, but $L$ is a linear order. This type of bipartite graph is also called as a ***chain graph***.

A ***chain graph*** is a bipartite graph whose neighbourhood of its vertices satisfies the following property: $\Gamma(x) \subseteq \Gamma(y) \lor \Gamma(y) \subseteq \Gamma(x)$ for all distinct vertices $x, y$ on the same partition.

> ***Lemma 1:** $d(P) \geq ch(B(P))$*

where $d(P)$ denotes degree of partial order $P$ and $ch(G)$ as the number of chain graphs needed to cover all edges of graph $G$.

***Proof:***

Let $L_1, L_2, \dots, L_d$ be linearizations of $P$ such that the intersection is $P$. Let $\bar{L}_1, \bar{L}_2, \dots, \bar{L}_d$ be bipartite graphs defined on previous section.

For every $x \in S, y \in S'$ s.t. $[x, y]$ is an edge of graph $B(P)$, the arc $(y, x)$ must be covered by at least one $L_i$. Otherwise, all linearizations $L_i$ will have the arc $(x, y)$, which implies that the intersection is not $P$ as it contains $(x, y)$, which is not in $P$.

Since the above is a necessary condition, we have shown that $d(P) \geq ch(B(P))$.

### Reduction

We will do reduction from the chromatic number 3 problem.

Suppose we have a graph $G = (V, E)$. Let $V = \{u_1, \dots, u_n\}$ and $E = \{e_1, \dots, e_m\}$. Construct a set $N$ which is a union of $S$ and $S'$. $S$ consists of:

- The nodes $u_{ia}, u_{ib}$ for all $u_i \in V$
- The nodes $u_{ik}, u_{jk}$ for all $e_k = [u_i, u_j] \in E$

$S'$ also contain the primed version of $S$.

Construct a partial order $P$ of $N$ s.t.

$$
\begin{align}
P = \, &\{(u_{ia}, u_{it}') | 1 \leq i \leq n, t \neq a\} \\
&\cup \{(u_{ib},u_{it}') | 1 \leq i \leq n, t \neq b \} \\
&\cup \{(u_{ik},u_{jk}') | 1 \leq k \leq m, e_k = [u_i, u_j] \} \\
&\cup \{(u_{ik},u_{jl}') | 1 \leq i,j \leq n, 1 \leq k \leq m, l > k \text{ or } l = a \text{ or } b \} \\
&\cup \{(u_{ik},u_{jl}) | 1 \leq i,j \leq n, 1 \leq k < l \leq m \}
\end{align}
$$

Note that no edge is going from $S'$ to $S$.

### How does $B(P)$ look like?

Let $Q$ be set of nodes $u_{ik}$ where $1 \leq k \leq m$, and $R$ be $u_{ia}$ and $u_{ib}$, for all $1 \leq i \leq n$. Define analogously for $Q'$ and $R'$.

$Q$ is connected to its primed version and all nodes in $Q'$ whose second index is strictly smaller. $R$ is connected to its primed version and all nodes in $S'$ whose first index is not the same.

> ***Lemma 2:** If $ch(B(P)) \leq 3$, then $G$ can be colored with $\leq 3$ colours*

***Proof:***

Let $B_1, B_2, B_3$ be chain subgraphs of $B(P)$ that covers it. Consider subgraph induced by vertices $u_{it}$ and $u_{it}'$ for a fixed $i$. It contains three connected components:

- $u_{ia}$ to $u_{ia}'$
- $u_{ib}$ to $u_{ib}'$
- Subgraph induced by $u_{it}$ and $u_{it}'$, where $1 \leq t \leq m$

As a chain cannot contain independent edges, no two connected components can belong to the same chain. Hence, each component can only belong to exactly one chain subgraph. Suppose the third component is part of $B_j$. Colour vertex $u_i$ with $j$.

This is a legal colouring for $G$. Suppose not, i.e. there exists two adjacent vertices $[u_i, u_j] = e_k$ that is coloured with the same colour $c$. Hence, $[u_{ik}, u_{ik}'], [u_{jk}, u_{jk}'] \in B_c$. However, these two edges are independent, contradicting the assumption that $B_c$ is a chain graph.

> ***Lemma 3:** If $G$ can be coloured with $\leq 3$ colours, then $d(P) \leq 3$*

***Proof:***

We will introduce several notations for linear order operations. If $X$ is a set, $X$ denote any linear order of $X$. If $F_1, F_2$ are linear orders of disjoint sets $X_1, X_2$, then $F_1F_2$ denotes concatenation of two linear orders. If $I = \{i_1, \dots, i_k\}$ and $i_1 < i_2 < \dots < i_k$, and $F_{i_1}, \dots, F_{i_k}$ are linear orders of disjoint sets $X_{i_1}, X_{i_2}, \dots, X_{i_k}$, $\langle F_i \uparrow i \in I\rangle$ represents $F_{i_1}, F_{i_2}, \dots, F_{i_k}$. $\langle F_i \downarrow i \in I\rangle$ is defined analogously.

Let $R_i = \{u_{ia}, u_{ib} | u_i \in C_i\}$, and define $R_i'$ analogously. For every edge $e_k = [u_i, u_j]$:

- If none of the endpoints coloured 1, then $E_k = \{u_{ik}, u_{jk}\}$
- If, for instance, $u_i$ has colour 1, then $E_k = u_{jk}u_{ik}'u_{ik}$

Define $K_i$ as linear order of $\{u_{ia}, u_{ib}, u_{ia}', u_{ib}'\} \cup \{u_{ik}' | u_i \in e_k\}$. If $u_i$ has colour 2, then $K_i$ is $u_{ib}u_{ia}'u_{ia}u_{ib}'$ followed by the latter in decreasing $k$. If $u_i$ has colour 3, then $K_i$ is $u_{ia}u_{ib}'u_{ib}u_{ia}'$ followed by the latter in decreasing $k$.

We construct $L_1 = R_1 \langle E_k \uparrow k \in \{1, 2, \dots, m\} \rangle R_1' \langle K_i \uparrow u_i \in C_2 \rangle \langle K_i \downarrow u_i \in C_3\rangle$. $L_2$ and $L_3$ are defined cyclically symmetric.

We can verify that $L_i$'s are linearizations of $P$. Next, we need to show that for every incomparable elements $x$ and $y$, $(x, y)$ is covered by at least one $L_i$.

- *Case 1*. $x \in S'$ and $y \in S$. We simply show that the chain subgraphs $\bar{L}_1, \bar{L}_2, \bar{L}_3$ covers $B(P)$. Let $x = u_{ik}'$ and $y = u_{jl}$. Suppose $u_i$ has colour 1 and $u_j$ has colour $c$. If $c \neq 1$ or $l \in \{1, 2, \dots, m\}$, then $(x, y) \in L_1$. Assume that $c = 1$ and $l \in \{a, b\}$. If $i > j$, then $(x, y) \in L_2$. If $i < j$, then $(x, y) \in L_3$.
- *Case 2*. $x, y \in S'$. Let $x = u_{ik}'$ and $y = u_{jl}$. If $i = j$ and $1 \leq l < k \leq m$, then $(x, y) \in L_c$, where $c$ is of different colour from $u_i$.
For other cases, we can find an element $z$ such that $(z, y) \in P$, but $z$ and $x$ are incomparable. If $i \neq j$ or [$i = j$ and $k \in \{a, b\}$], then $z = u_{jk}$. If $i = j$, $k \in \{1, 2, \dots, m\}$, and [$l \in \{a, b\}$ or $l > k$], $z = u_{ik}$. $(x, z)$ is covered by one $L_i$ from case 1.
- *Case 3*. $x \in S, y \in S'$. Find $z \in S'$ such that $(x, z) \in P$ but $z$ and $y$ are incomparable. This follows case 2.
- *Case 4*. $x, y \in S$. Find $z \in S'$ such that $(x, z) \in P$ and $z$ is incomparable to $y$. If such $z$ exists, this follows case 3. Otherwise, $x = u_{ik}$ for some $k \in \{a, b\}$ and $y = u_{jl}$ for some $l \in \{1, \dots, m\}$. Hence, $(x, y) \in L_c$ where $c$ is colour of $u_i$.

From Lemma 1 - 3, we can conclude that it is NP-complete to determine if the dimension of a partial order is at most 3.

## Hitting Family [DONE]

> It is NP-hard to determine if $d$-hitting family has size of 3.

We will do reduction from the dimension of a partial order from previous section. For simplicity, we will do reduction to 2-hitting family.

Given a partial order $P = (S, \leq)$. Let $d(P)$ be the dimension of the partial order $P$ and $h_d(P)$ be the size of optimal $d$-hitting family of $P$.

> ***Lemma 1:** If $d(P) \leq 3$, then $h_2(P) \leq 3$*

***Proof:***

Let $L_1, L_2, L_3$ be linearizations of $P$ such that the intersection is $P$. For any $x, y \in S$ where $x$ and $y$ are incomparable, $(x, y)$ must be covered of some $L_i$. Likewise for $(y, x)$.

Construct a hitting family with $L_1, L_2, L_3$ as its members. This is also a 2-hitting family. For any two distinct $x, y \in S$:

- If $x$ and $y$ are comparable, it must be covered by all $L_i$
- Otherwise, at least one of $L_i$ covers $(x, y)$; and at least one of $L_i$ covers $(y, x)$.

Therefore, for every possible ordering pairs of $S$, it is covered by at least one $L_i$.

> ***Lemma 2:** If $h_2(P) \leq 3$, then $d(P) \leq 3$*

***Proof:***

Let $L_1, L_2, L_3$ be linearizations of $P$ such that it is a 2-hitting family $P$. The intersection of them must also be $P$. For any $x, y \in S$:

- If $x$ and $y$ are comparable, then it must be covered by all $L_i$
- Otherwise, at least one of $L_i$ covers $(x, y)$. If not, then the $L_i$'s are not 2-hitting family as the tuple $\langle x, y\rangle$ is not hit by any of the $L_i$'s.

---

Therefore, determining if there is 2-hitting family of size 3 is NP-hard from lemma 1 and 2. Corollary: it is NP-hard to determine whether $d$-hitting family has size of 3.