Seminar at SMU Delhi
September 6, 2013 (Friday) ,
3:30 PM at Webinar
Speaker:
Sunil Chandran,
IISc, Bangalore
Title:
Boxicity and Poset Dimension.
Abstract of Talk
Let $G$ be a simple, undirected, finite graph with vertex set $V(G)$ and
edge set $E(G).$ The boxicity of $G,$ box$(G)$ is the minimum integer $k$
such that $G$ can be represented as the intersection graph of $k$-dimensional
boxes. For a poset $P$ with ground set $S,$ the dimension
of the poset, $\dim(P)$ is the minimum integer $t$ such that $P$
can be expressed as the intersection of t total orders.
Let $G_P$ be the underlying comparability graph of the poset $P,$
i.e. $S$ is the vertex set and two vertices are adjacent if and only if
they are comparable in $P.$ It is a well-known fact that posets
with the same underlying comparability graph have the same dimension.
The first result of this paper links the dimension of a poset to the
boxicity of its underlying comparability graph. In particular, we
show that for any poset $P,$ box$(G_P)/(\chi(G_P)-1)
\le dim(P) \le 2 box(G_P),$ where $\chi(G_P)$ is the
chromatic number of $G_P$ and $\chi(G_P) \ne 1.$ It immediately
follows that if $P$ is a height-2 poset, then box$(G_P) \le
dim(P) \le 2$ box$(G_P),$ since the underlying comparability
graph of a height-2 poset is a bipartite graph.
The second result of the paper relates the boxicity of a graph $G$ with a
natural partial order associated with the extended double cover of
$G,$ denoted as $G_c$: Note that $G_c$ is a bipartite graph with partite
sets $A$ and $B$ which are copies of $V(G)$ such that corresponding
to every vertex $u$ of $V(G),$ there are two vertices $u_A$ in $A,$ and $u_B$ in $B$
and $(u_A,v_B)$ is an edge in $G_c$ if and only if either $u=v$ or $u$
is adjacent to $v$ in $G.$ Let $P_c$ be the natural height-2 poset
associated with $G_c$ by making $A$ the set of minimal elements and
B the set of maximal elements. We show that box$i(G)/2
\leq dim(P_c) \le 2 box(G)+4.$