intersection of total orders

121 Views Asked by At

A graph $G$ with vertex set $V$ has $\dim(G) \leq d$ if and only if there exists a sequence $<_{1},<_{2}, \ldots , <_{d}$ of total orders on $V$ satisfying the following conditions:

(1) the intersection of $<_{1},<_{2}, \ldots , <_{d}$ is empty;

(2) for each edge $\{x,y\}$ and each vertex $z \notin \{x,y\}$ of $G$, there is at least one order $<_{i}$ in the sequence such that $x<_{i}z$ and $y<_{i}z$.

I know what the intersection of two total orders is, but I do not understand what it means for the intersection to be empty?

1

There are 1 best solutions below

0
On

If a sequence of total orders $<_{1},...,<_{d}$ satisfies (1), then for all $x,y\in G$, $x\neq y$, there exist $i,j$ such that $x<_{i}y$ and $y<_{j}x$.