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.$