% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Packages and Configurations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{amsmath, amsthm, amssymb} \usepackage{pstricks, pst-node} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Environments and Shorthands %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{observation}[theorem]{Observation} \theoremstyle{definition} \newtheorem{definition}{Definition} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheoremstyle{cases}% name of the style to be used {}% measure of space to leave above the theorem. E.g.: 3pt {}% measure of space to leave below the theorem. E.g.: 3pt {}% name of font to use in the body of the theorem {}% measure of space to indent {}% name of head font {\newline}% punctuation between head and body {0.5em}% space after theorem head {{\itshape \thmname{#1}} \thmnumber{#2} ({\itshape\thmnote{#3}}).\medskip}% Manually specify head \theoremstyle{cases} \newtheorem{case}{Case} \newcommand{\inlineHeading}[1]{ \medskip \noindent \emph{#1.} } \DeclareMathOperator{\sdiff}{\triangle} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Meta Data %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Product Dimension of Forests and\\ Bounded Treewidth Graphs} \usepackage[noblocks]{authblk} \renewcommand\Authfont{\small} \renewcommand\Affilfont{\itshape\small} \author[1]{L. Sunil Chandran} \author[2]{Rogers Mathew \footnote{Supported by an AARMS Postdoctoral Fellowship}} \author[1]{Deepak Rajendraprasad \footnote{Supported by Microsoft Research India PhD Fellowship}} \author[1]{Roohani Sharma} \affil[1] { Department of Computer Science and Automation, \authorcr Indian Institute of Science, \authorcr Bangalore, India, 560012. \authorcr \{sunil, deepakr\}@csa.iisc.ernet.in, \authorcr roohani.sharma90@gmail.com } \affil[2] { Department of Mathematics and Statistics, \authorcr Dalhousie University, Halifax, Canada - B3H 3J5 \authorcr rogersm@mathstat.dal.ca } % \author{% % L. Sunil Chandran\\ % \small Department of Computer Science and Automation,\\[-0.8ex] % \small Indian Institute of Science,\\[-0.8ex] % \small Bangalore, India, 560012.\\[-0.8ex] % \small\tt sunil@csa.iisc.ernet.in\\ % \and % Rogers Mathew\thanks{Supported by an AARMS Postdoctoral Fellowship.}\\ % \small Department of Mathematics and Statistics,\\[-0.8ex] % \small Dalhousie University, Halifax, Canada - B3H 3J5\\[-0.8ex] % \small\tt rogersm@mathstat.dal.ca\\ % % \and % Deepak Rajendraprasad\thanks{Supported by Microsoft Research India PhD Fellowship.}\\ % \small Department of Computer Science and Automation,\\[-0.8ex] % \small Indian Institute of Science,\\[-0.8ex] % \small Bangalore, India, 560012.\\[-0.8ex] % \small\tt deepakr@csa.iisc.ernet.in\\ % \and % Roohani Sharma % \small Department of Computer Science and Automation,\\[-0.8ex] % \small Indian Institute of Science,\\[-0.8ex] % \small Bangalore, India, 560012.\\[-0.8ex] % \small\tt roohani.sharma90@gmail.com\\ % } \date{\dateline{Sep 10, 2012}{Aug 18, 2013}\\ \small Mathematics Subject Classifications: 05C05, 05C62} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Main Content %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle \begin{abstract} The {\em product dimension} of a graph $G$ is defined as the minimum natural number $l$ such that $G$ is an induced subgraph of a direct product of $l$ complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and $k$-degenerate graphs. We show that every forest on $n$ vertices has product dimension at most $1.441 \log n + 3$. This improves the best known upper bound of $3 \log n$ for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a well-known result on the existence of orthogonal Latin squares to show that every graph on $n$ vertices with treewidth at most $t$ has product dimension at most $(t+2)(\log n + 1)$. We also show that every $k$-degenerate graph on $n$ vertices has product dimension at most $\lceil 5.545 k \log n \rceil + 1$. This improves the upper bound of $32 k \log n$ for the same by Eaton and R{\"o}dl. \bigskip\noindent \textbf{Keywords:} product dimension, representation number, forest, bounded treewidth graph, $k$-degenerate graph, orthogonal Latin squares. \end{abstract} \section{Introduction} For a graph $G(V,E)$ and an $l \in \mathbb{N}$, a function $\phi_{G} : V \rightarrow \mathbb{N}^{l}$ is called an {\em $l$-encoding} of $G$ if \begin{enumerate} \item $\phi_{G}$ is an injection, and \item $\forall u, v \in V, \{u,v\} \in E$ iff $\phi_{G}(u)$ and $\phi_{G}(v)$ differ in all $l$ coordinates. \end{enumerate} % For an $l$-encoding of $G$, $l$ is called the cost of encoding $G$ The minimum $l$ such that an $l$-encoding of $G$ exists is called the \emph{product dimension} of $G$ and is denoted by $pdim(G)$. Some authors refer to it as the {\em Prague dimension} \cite{furedi2000prague}. The product dimension of a graph $G$ was first defined in \cite{nesetril1978simple} by Ne\v{s}et\v{r}il and R\"{o}dl as the minimum $l$ such that $G$ is an induced subgraph of a direct product (see Section \ref{notDef}) of $l$ complete graphs. It is easy to see that the two definitions of product dimension are equivalent. Another equivalent definition of the product dimension of a graph is as the minimum number of proper colorings of $G$ such that any pair of non-adjacent vertices get the same color in at least one of the colorings and not in all of them. The concept of product dimension of a graph was first used to prove the Galvin-Ramsey property of the class of all finite graphs \cite{nesetril1978simple}. Thereafter, this area was separately explored by various people. In 1980, Lov\'{a}sz, Ne\v{s}et\v{r}il and Pultr showed that the product dimension of a path on $n+1$ vertices (length $n$) is $\lceil \log n \rceil$ \cite{lovasz1980product}. They also gave a lower bound for the product dimension of a graph (Theorem 5.3 \cite{lovasz1980product}) which in particular tells that the product dimension of a tree on $n$ vertices with $l$ leaves is at least $\log (n - l + 1)$. The authors also suggested that the idea used to encode paths could be extended to study the product dimension of trees. Immediately after this paper, Poljak and Pultr in \cite{poljak1981dimension} came up with bounds on product dimension of trees using the encoding for paths employed in \cite{lovasz1980product}. The results in this paper are $pdim(T) \leq 3 \lceil \log |T| \rceil $ and $\log |m(T)| -1 \leq pdim(T) \leq 3 \lceil \log |m(T)| \rceil + 1$ where, $T$ is a forest and $m(T)$ is the graph obtained from $T$ by recursively deleting a leaf vertex with one or more siblings. In this paper we improve the above upper bound to $1.441 \log |T| + 3$. More recently, in 2010, Ida Kantor in her doctoral thesis \cite{kantor10} determines another upper bound on the product dimension of trees viz. $2 + \lceil \log \delta_{r} \rceil + \sum_{i \in S, 2 \leq i < r} \lceil \log \delta_{i} \rceil + \sum_{i \not \in S, 3 \leq i< r} \lceil \log (\delta_{i}-1) \rceil$, where $r$ is the radius of the tree, $x$ is a central vertex, $\delta_{i}$ is the maximum degree among all vertices which are at a distance $r-i$ from $x$ and $S= \{2^{i} : i \in \mathbb{N}\}$. The technique used is a generalization of the technique used by Lov\'{a}sz, Ne\v{s}et\v{r}il and Pultr in \cite{lovasz1980product} for paths. The product dimension of graphs obtained by amalgamation of smaller graphs was studied in \cite{alles1986dimension}. The idea of using orthogonal Latin squares to encode a disjoint union of complete graphs is given by Evans, Isaak and Narayan in %Theorem 4.3 \cite{evans2000representations}. This idea is the motivation for our \emph{Amalgamation Lemma for General Graphs} (Lemma \ref{amalgamDegen}) which is a key ingredient for showing that the product dimension of a graph on $n$ vertices with treewidth at most $t$ is at most $(t+2)(\log n +1)$. Orthogonal Latin squares have been known for a long time. In the 1780s Euler demonstrated methods for constructing orthogonal Latin squares of order $t$ where $t$ is odd or a multiple of $4$ and later conjectured that orthogonal Latin squares of order $t \equiv 2$ mod $4$ do not exist. In 1960, Parker, Bose, and Shrikhande in \cite{bose1960further} disproved Euler's conjecture for all $t \geq 10$. Thus, orthogonal Latin squares exist for all orders $t \geq 3$ except $t = 6$. We use this result to prove Lemma \ref{amalgamDegen}. A parameter closely related to product dimension of a graph $G$ is the equivalence number of the complement of the graph $G$, $\bar{G}$. An \emph{equivalence} is a vertex disjoint union of cliques and the \emph{equivalence number} of a graph $H$ is the minimum number of equivalences required to cover the edges of $H$. In \cite{alon1986covering}, Alon came up with bounds on the equivalence number of a graph showing $\log n - \log d \leq eq(\bar{G}) \leq 2 e^{2} (d+1)^{2} \ln n$, where $G$ is a graph on $n$ vertices with maximum degree $d$. It is easy to see that $pdim(G) \leq eq(\bar{G}) + 1$ (\cite{cooper10}). Eaton and R\"{o}dl in \cite{eaton1996graphs} proved that $pdim(G) \leq 32 k \log n$ for a $k$-degenerate graph $G$ on $n$ vertices. Since degeneracy of a graph is at most its maximum degree, this result is a significant improvement over Alon's result. We use a probabilistic method to further improve this upper bound to $\lceil 5.545 k \log n \rceil + 1$. The product dimension of a graph is closely related to the representation number of a graph - a concept introduced by Erd\"{o}s in \cite{erdos1989representations}. A graph $G$ is representable modulo $r$ if there exists an injection $f : V(G) \rightarrow \{0, \ldots, r-1\}$ such that for all $u,v \in V(G)$, $gcd(f(u),f(v))=1$ if and only if $\{u,v\} \in E(G)$. The minimum $r$ modulo which $G$ is representable is called the representation number of $G$. The relationship between the two concepts viz. the product dimension of a graph and representation number of a graph is described in \cite{evans2007representations}. \subsection{Summary of Results} \begin{enumerate} \item For any forest $T$ on $n$ vertices, $pdim(T) \leq 1.441 \log n + 3$ (Theorem \ref{prodDimTrees}). \item[] This is an improvement over the upper bound for product dimension of trees and forests given by Poljak and Pultr in \cite{poljak1981dimension} viz. $3 \lceil \log n \rceil$. We use a technique of divide and conquer to prove the theorem. The divide operation corresponds to the operation described in our \emph{Splitting Lemma for Forests} (Lemma \ref{lem1}) while the conquer operation corresponds to our \emph{Amalgamation Lemma for Bipartite Graphs} (Lemma \ref{lem2}). \item For any graph $G$ on $n$ vertices and treewidth $t$, $pdim(G) \leq (t+2)(\log n +1)$ (Theorem \ref{thmTreeWidth}). \item[] The techniques used to prove Theorem \ref{prodDimTrees} for trees inspired us to work for graphs with bounded treewidth. Another key ingredient in proving this theorem is the \emph{Amalgamation Lemma for General Graphs} (Lemma \ref{amalgamDegen}) which is based on the existence of orthogonal Latin squares of different orders. Since treewidth $t$ graphs are $t$-degenerate (Section 4.2, \cite{koster02}), it follows from an upper bound on product dimension based on degeneracy of a graph \cite{eaton1996graphs} that $pdim(G) \leq 32 t \log n$. Our result is an improvement over that. \item For every $k$-degenerate graph $G$ on $n$ vertices, $pdim(G) \leq \lceil 5.545 k \log n \rceil + 1$ (Theorem \ref{thmDegenerate}). \item[] We derive this result as an improvement over Eaton's and R\"{o}dl's upper bound of $32 k \log n$ for product dimension of $k$-degenerate graphs \cite{eaton1996graphs}. We use a probabilistic argument to prove the theorem and we believe that our proof is shorter. \end{enumerate} \subsection{Notations and Definitions} \label{notDef} In this paper we consider only undirected, simple, finite graphs. For any graph $G$, $V(G)$ denotes its vertex set and $E(G)$ denotes its edge set. The \emph{cardinality} of a set $S$ is denoted by $|S|$. For a graph $G$, $|G|$ denotes the cardinality of $V(G)$. $N_{G}(u)$ denotes the open neighborhood of vertex $u$ in $G$, i.e. all the vertices adjacent to $u$ in $G$. The \emph{degree} of a vertex $u$, denoted by $d(u)$ is $|N(u)|$. A \emph{subgraph} $H$ of $G$ is a graph with vertex set $V(H) \subset V(G)$ and edge set $E(H) \subset E(G) \cap \{\{v, v'\}: v, v' \in V(H)\}$. If $H$ is a subgraph of $G$ then $G$ is called the supergraph of $H$. % A \emph{subgraph} $H$ of $G$, denoted by $H \subset G$, is a graph with vertex set $V(H) \subset V(G)$ and edge set $E(H) \subset E(G) \cap \{\{v, v'\}: v, v' \in V(H)\}$. If $E(H) = E(G) \cap \{\{v, v'\}: v, v' \in V(H)\}$, then $H$ is called an \emph{induced subgraph} of $G$, denoted by $H \preceq G$. For a graph $G$, the \emph{graph induced by a set $X \subset V(G)$}, denoted by $G[X]$, is the graph with $V(G[X]) = X$ and $ E(G[X]) = E(G) \cap \{\{v, v'\}: v, v' \in X\}$. If $G_{1}$ and $G_{2}$ are two graphs, then $G_{1} \setminus G_{2}$ is the graph $G_{1}[V(G_{1}) \setminus V(G_{2})]$. If $G$ is a graph and $S \subset V(G)$, then $G \setminus S$ is the graph $G[V(G) \setminus S]$. The \emph{union} of two graphs $G_{1}$ and $G_{2}$, denoted by $G_{1} \cup G_{2}$, is the graph with $V(G_{1} \cup G_{2})=V(G_{1}) \cup V(G_{2})$ and $E(G_{1} \cup G_{2})=E(G_{1}) \cup E(G_{2})$. Moreover, if $V(G_{1}) \cap V(G_{2}) = \emptyset $, then we call it a \emph{disjoint union} and denote it as $G_{1} \uplus G_{2}$. The \emph{intersection} of two graphs $G_{1}$ and $G_{2}$ is the graph $G_{1} \cap G_{2}$ with $V(G_{1} \cap G_{2}) = V(G_{1}) \cap V(G_{2})$ and $E(G_{1} \cap G_{2}) = E(G_{1}) \cap E(G_{2})$. The graph $G_{1} \times G_{2}$ is the \emph{direct product} of two graphs $G_{1}$ and $G_{2}$ with $V(G_{1} \times G_{2})=V(G_{1}) \times V(G_{2})$ and $E(G_{1} \times G_{2})= \{ \{u,v\} : u, v \in V(G_{1}) \times V(G_{2})$ and if $u=(x_{1}, x_{2})$, $v=(y_{1},y_{2})$, then $\{x_{1},y_{1}\} \in E(G_{1})$ and $\{x_{2} ,y_{2}\} \in E(G_{2})\}$. Let $[n]$ denote the set $\{1, \ldots , n\}$. The set of all natural numbers is denoted by $\mathbb{N}$. $\{a\}^{k}$ denotes the $k$-tuple $(a, \ldots , a)$. Throughout the paper, $\log n$ denotes $\log _{2} n$ and $\ln n$ denotes $\log _{e} n$. \section{Product Dimension of Forests} \begin{definition}[Split vertex] \label{splittingDefn} In a forest $F$ on $n$ vertices, a vertex $v$ is called \begin{enumerate} \item an \emph{$(\epsilon,2)$-split vertex} if $F \setminus \{v\} = F_{1} \uplus F_{2}$ such that $|F_{1}|, |F_{2}| \leq (\frac{1}{2} + \epsilon)n$, and \item an \emph{$(\epsilon,3)$-split vertex} if $F \setminus \{v\} = F_{1} \uplus F_{2} \uplus F_{3}$ such that $|F_{1}|, |F_{2}|, |F_{3}| \leq (\frac{1}{2} - \epsilon)n$, \end{enumerate} where $F_{1}, F_{2}$ and $F_{3}$ are subgraphs of $F$. \end{definition} \begin{lemma} [Splitting Lemma for Forests]\label{lem1} In every forest $F$, for every $\epsilon \geq 0$, there exists either an $(\epsilon,2)$-split vertex or an $(\epsilon,3)$-split vertex. \end{lemma} \begin{proof} Let $T$ be a tree such that $V(T)=V(F)$ and $T$ is a supergraph of $F$. It is easy to see that if $v \in V(T)$ is an $(\epsilon,2)$-split vertex of $T$ with $T \setminus \{v\} = T_{1} \uplus T_{2}$ and $|T_{1}|, |T_{2}| \leq (\frac{1}{2} + \epsilon)n$ then $v$ is also an $(\epsilon,2)$-split vertex of $F$ with $F \setminus \{v\} = F_{1} \uplus F_{2}$, $|F_{1}|, |F_{2}| \leq (\frac{1}{2} + \epsilon)n$ where each $F_{i}$ is a subgraph of $T_{i}$. Similarly any $(\epsilon,3)$-split vertex of $T$ is also an $(\epsilon,3)$-split vertex of $F$. Hence it suffices to show that either an $(\epsilon,2)$-split vertex or an $(\epsilon,3)$-split vertex exists in the tree $T$. %Similarly, if $v \in V(T)$ is an $(\epsilon,3)$-split vertex of $T$ such that $T \setminus \{v\} = T_{1} \uplus T_{2} \uplus T_{3}$ and $|T_{1}|, |T_{2}|, |T_{3}| \leq (\frac{1}{2} - \epsilon)n$ then $v$ is also an $(\epsilon,3)$-split vertex of $F$ such that $F \setminus \{v\} = F_{1} \uplus F_{2} \uplus F_{3}$, $|F_{1}|, |F_{2}|, |F_{3}| \leq (\frac{1}{2} - \epsilon)n$ and each $F_{i}$ is a subgraph of $T_{i}$. Let $n=|T|$. For any $v \in V(T)$, let $C_{1}(v), \ldots ,$ $C_{m}(v)$ denote the (connected) components of $T \setminus \{v\}$ such that $|C_{1}(v)| \geq \cdots \geq |C_{m}(v)|$. Choose $v \in V(T)$ such that $|C_{1}(v)|={\min}\{|C_{1}(u)| : u \in V(T)\}$. First we claim that $|C_{1}(v)| \leq (\frac{1}{2} + \epsilon)n$. For the sake of contradiction, let us assume that $|C_{1}(v)| > (\frac{1}{2} + \epsilon)n$. Let $w \in C_{1}(v) \cap N_{T}(v)$. If $C_{1}(w) \subset C_{1}(v)$, then $|C_{1}(w)|<|C_{1}(v)|$ (because $C_{1}(w) \subset C_{1}(v) \setminus \{v\}$) contradicting the choice of $v$. Hence, $C_{1}(w) \subset T \setminus C_{1}(v)$ and $|C_{1}(w)| \leq n-|C_{1}(v)| < (\frac{1}{2} - \epsilon)n < |C_{1}(v)|$. This again contradicts the choice of $v$. If $|C_{1}(v)| > (\frac{1}{2} - \epsilon)n$, then $v$ is an $(\epsilon,2)$-split vertex and $T_{1}=C_{1}(v)$, $T_{2}= T \setminus (T_{1} \cup \{v\})$. Otherwise, let $Q_{1}=C_{1}(v), \ldots , Q_{m}=C_{m}(v)$. Hence, $|Q_{i}| \leq (\frac{1}{2}- \epsilon)n$ for all $ i \in [m]$. If $ m \leq 3$, then $v$ is either an $(\epsilon,3)$-split vertex or an $(\epsilon,2)$-split vertex with $T_{i}=Q_{i}$. If $m \geq 4$, consider a partition $I_{1} \uplus \ldots \uplus I_{k}=[m]$ with minimum possible $k$ such that $|\cup_{j \in I_{l}}Q_{j}| \leq (\frac{1}{2} - \epsilon)n$ for all $l \in [k]$. For $k \leq 3$, $v$ is either an $(\epsilon,2)$-split vertex or an $(\epsilon,3)$-split vertex with $T_{l}=\cup_{j \in I_{l}}Q_{j}$. Suppose $k \geq 4$, define $Q_{l}'=\cup_{j \in I_{l}} Q_{j}$, $l \in [k]$ and let $Q'$ be the union of smallest two among $\{Q_{1}', \ldots , Q_{k}'\}$. Hence, $|Q'| \leq \frac{n}{2} \leq (\frac{1}{2} + \epsilon)n$ by the pigeonhole principle. By the minimality in the choice of the partition $I_{1} \uplus \ldots \uplus I_{k}$, $|Q'| > (\frac{1}{2} - \epsilon)n$. Thus, $v$ is an $(\epsilon,2)$-split vertex with $T_{1}=Q'$ and $T_{2}=T \setminus (Q' \cup\{ v\})$. \end{proof} \begin{definition} We call an $l$-encoding $\phi _{G}$ of a graph $G$, a \emph{well-begun $l$-encoding} if the first coordinate of $\phi_{G}$ is from $\{0, \ldots, \chi(G)-1\}$. \end{definition} \begin{observation} \label{extensionOfEncoding} For any $q > p$, if $\phi_{G}$ is a $p$-encoding of $G$, then $\psi_{G}$, obtained from $\phi_{G}$ by adding $q-p$ coordinates to $\phi_{G}$ such that for all $p < i \leq q$, the $i$-th coordinate of $\psi_{G}(x)$ is the $p$-th coordinate of $\phi_{G}$, is a $q$-encoding of $G$. \end{observation} \begin{lemma}[Amalgamation Lemma for Bipartite Graphs]\label{lem2} Let $G_{0},\ldots , G_{k-1}$ be bipartite graphs such that $G_{i} \cap G_{j} = \{g\}$ for all $i, j \in \{0, \ldots, k-1\}$, $i \neq j$. Let $G= \cup_{i=0}^{k-1} G_{i}$. For every $i \in \{0, \ldots , k-1\}$, let $\phi_{G_{i}}$ be a \emph{well-begun} $l_{i}$-encoding of $G_{i}$. Then we can construct a well-begun $l$-encoding $\phi_{G}$ of $G$, where $l=max_{0 \leq i \leq k-1}\{l_{i}\} + \lceil \log k \rceil$. \begin{figure}[ht] \begin{center} % \input{amalgam.pstex_t} \psset{xunit=0.1\textwidth} \psset{yunit=0.07\textwidth} \begin{pspicture}(2,2)(8,7) % Petals \rput{ 60}(5,3){\psbezier(0,0)(-1,4)(1,4)(0,0) \rput[u]{*0}(0,3.5){$G_0$}} \rput{ 20}(5,3){\psbezier(0,0)(-1,4)(1,4)(0,0) \rput[u]{*0}(0,3.5){$G_1$}} \rput{-60}(5,3){\psbezier(0,0)(-1,4)(1,4)(0,0) \rput[u]{*0}(0,3.5){$G_{k-1}$}} \rput{-10}(5,3){\psdot[dotstyle=Bo](0,2)} \rput{-20}(5,3){\psdot[dotstyle=Bo](0,2)} \rput{-30}(5,3){\psdot[dotstyle=Bo](0,2)} % Core \pscircle[fillstyle=solid, fillcolor=black](5,3){0.12} \uput[d](5,3){$g$} \end{pspicture} \caption{A graph $G= \cup_{i=0}^{k-1} G_{i}$ where $G_{i} \cap G_{j} = \{g\}$ for all $i, j \in \{0, \ldots, k-1\}$, $i \neq j$.} \label{Amalgam} \end{center} \end{figure} \end{lemma} \begin{proof} From Observation \ref{extensionOfEncoding}, without loss of generality we can assume that $l_{0} = \cdots = l_{k-1}= \max_{i}\{l_{i}\}$. Since we can rename the alphabets used in each coordinate of an encoding independently of the other coordinates, it is safe to assume that the vertex $g$ gets the encoding $\{0\}^{l_{0}}$ in every $\phi_{G_{i}}$. For all $ 0 \leq i \leq k-1$, let $b_{0}(i)$ denote the binary representation of $i$ using exactly $ \lceil \log k \rceil $ bits and $b_{1}(i)$ denote the bitwise complement of $b_{0}(i)$. The $l$-encoding $\phi _{G}$ of $G$ is as follows. For all $i$, $0 \leq i \leq k-1$, for every $x \in V(G_{i} \setminus \{g\})$ \begin{eqnarray} \label{eqn} \phi_{G}(x) &=& \begin{cases} \phi_{G_{i}}(x) b_{0}(i) & \textnormal{if $\phi_{G_{i}}(x)$ begins with $0$}\\ \phi_{G_{i}}(x) b_{1}(i) & \textnormal{if $\phi_{G_{i}}(x)$ begins with $1$}\\ \end{cases} \nonumber \\ \phi_{G}(g) &=& \{0\}^{l_{0}}\{2\}^{\lceil \log k \rceil} \end{eqnarray} We can verify that $\phi_{G}$ is a valid $l$-encoding of $G$ from the following argument. Let $x, y \in V(G_{i} \setminus \{g\})$. If $\{x,y\} \in E(G_{i})$ then the first coordinates of $\phi_{G_{i}}(x)$ and $\phi_{G_{i}}(y)$ are different. Thus, the extra coordinates added to $\phi_{G_{i}}(x)$ and $\phi_{G_{i}}(y)$ to get $\phi_{G}(x)$ and $\phi_{G}(y)$ are complements of each other (by Equation (\ref{eqn})). If $\{x,y\} \not \in E(G_{i})$, then $\phi_{G_{i}}(x)$ and $\phi_{G_{i}}(y)$ agreed in some coordinate, say $t$. Hence, $\phi_{G}(x)$ and $\phi_{G}(y)$ also agree in the $t$-th coordinate. Let $x \in V(G_{i} \setminus \{g\})$ and $y \in V(G_{j} \setminus \{g\})$ for some $i,j \in \{0, \ldots, k-1\}$, $i \neq j$. Note that, since $G_{i} \cap G_{j} = \{g\}$, $\{x,y\} \not \in E(G)$. If $\phi_{G_{i}}(x)$ and $\phi_{G_{i}}(y)$ agree in the first coordinate then $\phi_{G}(x)$ and $\phi_{G}(y)$ also agree in the first coordinate. If $\phi_{G_{i}}(x)$ begins with $0$ and $\phi_{G_{i}}(y)$ begins with $1$, then $\phi_{G}(x)=\phi_{G_{i}}(x) b_{0}(i)$ and $\phi_{G}(y)=\phi_{G_{j}}(y) b_{1}(j)$. Since $i \neq j$, $b_{0}(i)$ and $b_{1}(j)$ agree in some coordinate. For any $i$, let $x \in V(G_{i} \setminus\{g\})$. If $\{g,x\} \not \in E(G_{i})$, then $\phi_{G_{i}}(g)$ and $\phi_{G_{i}}(x)$ agreed in some coordinate, say $t$. Hence, $\phi_{G}(g)$ and $\phi_{G}(x)$ also agree in the $t$-th coordinate. In the other case, that is, when $\{g,x\} \in E(G_{i})$, since $\phi_{G_{0}}(g)$ begins with $0$, $\phi_{G_{i}}(x)$ must begin with $1$. Thus, the extra coordinates added to $\phi_{G_{i}(x)}$ to get $\phi_{G}(x)$ are $b_{1}(i)$ while the extra coordinates added to $\phi_{G_{0}}(g)$ to get $\phi_{G}(g)$ are $\{2\}^{\lceil \log k \rceil}$. Therefore, $\phi_{G}(x)$ and $\phi_{G}(g)$ disagree in all coordinates. It is easy to see from Equation \ref{eqn} that $\phi(G)$ is well-begun. \end{proof} \begin{theorem}\label{prodDimTrees} For any forest $T$ on $n$ vertices, $pdim(T) \leq 1.441 \log n + 3$. \end{theorem} \begin{proof} Let $V(T)=\{v_{0}, \ldots, v_{n-1}\}$, $f: V(T) \longrightarrow \{ 0, 1, \ldots , n-1\}$ be a bijection, and $f_{i}=f(v_{i})$. We use a divide and conquer strategy to prove the theorem. Let $C(T)$ denote the minimum $l$ such that there exists a \emph{well-begun} $l$-encoding of $T$. Let $C(n)=\max\{C(T) : T$ is a forest on at most n vertices$\}$. \inlineHeading{Base Case} All possible forests with $|V(T)| \leq 3$ with their well-begun $3$-encodings are shown in Figure \ref{Encodings}. Thus, $C(3) \leq 3$. \begin{figure}[ht] \begin{center} \psmatrix[colsep=2.5cm,rowsep=0cm] [mnode=circle]$v_i$ \\ $(0,0,f_i)$ \\ &\\ [mnode=circle]$v_i$ & [mnode=circle]$v_j$ \\ \ncline[linestyle=dotted]{4,1}{4,2} $(0,0,f_i)$ & $(0, 0, f_j)$ \\ &\\ [mnode=circle]$v_i$ & [mnode=circle]$v_j$ \\ \ncline{7,1}{7,2} $(0,0,f_i)$ & $(1, 1, f_j)$ \\ &\\ [mnode=circle]$v_i$ & [mnode=circle]$v_j$ & [mnode=circle]$v_k$ \\ \ncline[linestyle=dotted]{10,1}{10,2} \ncline[linestyle=dotted]{10,2}{10,3} $(0,0,f_i)$ & $(0, 0, f_j)$ & $(0,0,f_k)$ \\ &\\ [mnode=circle]$v_i$ & [mnode=circle]$v_j$ & [mnode=circle]$v_k$ \\ \ncline{13,1}{13,2} \ncline[linestyle=dotted]{13,2}{13,3} $(0,0,f_i)$ & $(1, 1, f_j)$ & $(0,1,f_k)$ \\ &\\ [mnode=circle]$v_i$ & [mnode=circle]$v_j$ & [mnode=circle]$v_k$ \\ \ncline{16,1}{16,2} \ncline{16,2}{16,3} $(0,0,f_i)$ & $(1, 1, f_j)$ & $(0,0,f_k)$ \\ &\\ \endpsmatrix \caption{Well-begun $3$-encodings of the six forests with at most $3$ vertices. Each row depicts a single forest and dotted lines are non-edges.} \label{Encodings} \end{center} \end{figure} Note that the third coordinate of each of the encodings is always a unique number associated with the vertex. This ensures injectivity of all the encodings that we get during the conquer steps. \inlineHeading{Divide and Conquer} In our divide and conquer strategy, the divide operation corresponds to the two splitting operations of Lemma \ref{lem1} viz. \emph{$(\epsilon,2)$-splitting} and \emph{$(\epsilon,3)$-splitting} and the conquer operation corresponds to the amalgamation operation of Lemma \ref{lem2}. Choose $\epsilon =\frac{\sqrt{5}}{2}-1$. Let $\alpha = \frac{1}{2} + \epsilon$ and $\beta =\frac{1}{2} - \epsilon$. Note that $\alpha^{2}=\beta$. By Lemma \ref{lem1}, there exists either an $(\epsilon,2)$-split vertex or an $(\epsilon,3)$-split vertex, say $v \in V(T)$. If $v$ is an $(\epsilon,2)$-split vertex, then from Definition \ref{splittingDefn}, $T \setminus \{v\} = T_{1} \uplus T_{2}$ such that $|T_{1}|, |T_{2}| \leq \alpha n$. Let $T_{i}'=T_{i} \cup \{v\}$, $i \in [2]$. Let $\phi_{T_{i}'}$ be a \emph{well-begun} $l_{i}$-encoding of $T_{i}'$, $i \in [2]$. Then by Lemma \ref{lem2}, there exists a \emph{well-begun} $l$-encoding $\phi_{T}$ of $T$ with $l=max\{l_{1},l_{2}\} + 1$. Similarly, if $v$ is an $(\epsilon,3)$-split vertex, then from Definition \ref{splittingDefn}, $T \setminus \{v\} = T_{1} \uplus T_{2} \uplus T_{3}$ such that $|T_{1}|, |T_{2}|, |T_{3}| \leq \beta n$. Let $T_{i}'=T_{i} \cup \{v\}$, $i \in [3]$. Let $\phi_{T_{i}'}$ be a \emph{well-begun} $l_{i}$-encoding of $T_{i}'$, $i \in [3]$. Then by Lemma \ref{lem2}, there exists a \emph{well-begun} $l$-encoding $\phi_{T}$ of $T$ with $l=max\{l_{1},l_{2},l_{3}\} + 2$. Therefore, the following recurrence relation holds. \begin{eqnarray} C(n) &\leq& \max \{C(\alpha n +1) + 1, C(\beta n +1) + 2 \} \nonumber \\ C(3) &\leq& 3 \end{eqnarray} \inlineHeading{Solving the recurrence} Let $X$ be an arbitrary leaf in the recurrence tree and let $P$ denote the path from the root to $X$. Let the number of \emph{$(\epsilon,2)$-split} operations and \emph{$(\epsilon,3)$-split} operations along $P$ be $k_{2}$ and $k_{3}$ respectively. Let $s_{i}$ be the size of the subgraph of $T$ to be conquered along $P$ after $i$ steps. Let $\gamma _{1},\ldots , \gamma _{k}$, $k=k_{2}+k_{3}$, be such that \begin{equation} \gamma _{i} = \begin{cases} \alpha & \textnormal{if the $i$-th divide operation along $P$ is an \emph{$(\epsilon,2)$-split} operation}\\ \beta & \textnormal{if the $i$-th divide operation along $P$ is an \emph{$(\epsilon,3)$-split} operation} \end{cases} \end{equation} Therefore, $s_{k} \leq (\prod_{j=1}^{k} \gamma _{j})n + \prod_{j=2}^{k} \gamma _{j} + \prod_{j=3}^{k} \gamma _{j} + \ldots + \prod_{j=k}^{k} \gamma _{j} +1$. Since $\gamma _{i} \leq \alpha$ for all $i$, $1 \leq i \leq k$, $s_{k} \leq (\prod_{j=1}^{k} \gamma _{j})n + \alpha ^{k-1} + \alpha ^{k-2} + \ldots + \alpha +1 \leq \alpha ^{k_{2}} \beta ^{k_{3}} n + \frac{1}{1- \alpha} \leq \alpha ^{k_{2}} \beta ^{k_{3}} n + 2.62$. Hence, $s_{k} \leq \lfloor \alpha^{k_{2}+2k_{3}}n + 2.62 \rfloor$. Note that $k_{2}+2k_{3}$ is the total cost of conquering (number of coordinates introduced by the amalgamation operation) incurred along $P$. Since $X$ is arbitrary, $C(n) \leq k_{2} + 2 k_{3} + C(s_{k})$. Let $k_{2}+2k_{3} \geq 1.441 \log n$. Then $s_{k} \leq 3$. Hence, $C(n) \leq 1.441 \log n + C(3) \leq 1.441 \log n +3$. Therefore, $pdim(T) \leq 1.441 \log n + 3$. \end{proof} \section{Product Dimension of Bounded Treewidth Graphs} \begin{definition} [Definition 1, \cite{chandran2007boxicity}] A \emph{tree decomposition} of $G$ is a pair $(\{X_{i} : i \in I \},T )$, where $I$ is an index set, $\{X_{i} : i \in I \}$ is a collection of subsets of $V(G)$ and $T$ is a tree whose node set is $I$, such that the following conditions are satisfied: \begin{enumerate} \item $\cup_{i \in I} X_{i}=V(G)$. \item $\forall \{u,v\} \in E(G), \exists i \in I$ such that $u,v \in X_{i}$. \item $\forall i,j,k \in I$ : if $j$ is on a path in $T$ from $i$ to $k$, then $X_{i} \cap X_{k} \subset X_{j}$. \end{enumerate} The \emph{width of a tree decomposition} $(\{ X_{i} : i \in I \},T)$ is $ \max \{|X_{i}| : i \in I\} -1$. The \emph{treewidth} of $G$, \emph{tw(G)}, is the minimum width over all tree decompositions of $G$. %A tree decomposition $(\{X_{i} : i \in I \},T )$ of $G$ where $T$ is a path is called a path decomposition of $G$ and pathwidth of $G$ is defined as the minimum width over all path decompositions of $G$. \end{definition} Note that by a {\em rooted tree} we mean a tree with a vertex designated as the {\em root vertex}. %The height($i$) of a node $i$ in a rooted tree $T$ with root $r$ is defined as usual: height($r$) of the root $r$ is $0$, and height($x$) for any other node %$x$ is exactly one more than the height of its parent. A node $i \neq j$ is the ancestor of node $j$ if $i$ is in the path from $j$ to $r$. A node $j$ is a %descendant of $i$ if either $i = j$ or $i$ is the ancestor of $j$. \begin{definition}[Definition 2, \cite{chandran2007boxicity}] A \emph{normalized tree decomposition} of a graph $G$ is a triple $(\{X_{i} : i \in I \},r \in I,T )$ where $(\{X_{i} : i \in I \},T )$ is a tree decomposition of $G$ that additionally satisfies the following two properties: \begin{enumerate} \setcounter{enumi}{3} \item It is a rooted tree where the subset $X_{r}$ that corresponds to the root node $r$ contains exactly one vertex. \item For any node $i$, if $i'$ is the child of $i$, then $|X_{i'} \sdiff X_{i}|=1$ where, $X_{i'} \sdiff X_{i}$ denoted the symmetric difference of $X_{i'}$ and $X_{i}$. \end{enumerate} \end{definition} \begin{lemma}[Lemma 3, \cite{chandran2007boxicity}] For any graph $G$ there is a normalized tree decomposition with width equal to $tw(G)$. \end{lemma} \begin{lemma}[Splitting Lemma for Bounded Treewidth Graphs]\label{splitDegen} Let $G$ be a graph on $n$ vertices with $tw(G)=t$ and a normalized tree decomposition $(\{X_{i}: i \in I\}, r \in I, T)$ of width $t$. Then there exists $l \in I$ such that $G \setminus X_{l} = G_{1} \uplus G_{2} \uplus G_{3}$ and $|G_{i}| \leq \frac{1}{2}(n-|X_{l}| + 1)$, $i \in [3]$, where $G_{1}, G_{2}$ and $G_{3}$ are subgraphs of $G$. \end{lemma} \begin{proof} For every $i$, let $D_{1}(i), \dots, D_{t}(i)$ be the components of $T \setminus \{i\}$ and let $C_{l}(i)$, $j \in [t]$, be the graphs induced by $(\cup_{j \in V(D_{l}(i))} X_{j}) \setminus X_{i}$. Without loss of generality assume that $|C_{1}(i)| \geq \cdots \geq |C_{t}(i)|$. Let $c= \min \{|C_{1}(j)| : j \in I \}$ and $I' = \{j \in I : |C_{1}(j)| =c\}$. Then choose $l \in I'$ such that $|X_{l}| = \min \{|X_{j}| : j \in I'\}$. We claim that, $|C_{1}(l)| \leq \frac{1}{2} (n-|X_{l}| + 1)$. For the sake of contradiction, assume that $|C_{1}(l)| > \frac{1}{2}(n - |X_{l}| + 1)$. Let $m \in N_{T}(l) \cap D_{1}(l)$. Then, since $T$ is a normalized tree decomposition $|X_{m} \sdiff X_{l}|=1$, therefore, the following two cases arise. \setcounter{case}{0} \begin{case}[$X_{m}=X_{l} \cup \{v\}$ where $v \in V(G)$] If $D_{1}(m) \subset D_{1}(l)$, then $|C_{1}(m)| < |C_{1}(l)|$ because $C_{1}(m) = C_{1}(l) \setminus \{v\}$. Otherwise, $D_{1}(m)=T \setminus D_{1}(l)$ in which case $|C_{1}(m)| = |G \setminus (C_{1}(l) \cup X_{l})| = n -|C_{1}(l)| -|X_{l}| < n - \frac{1}{2}(n - |X_{l}| +1) - |X_{l}| =\frac{1}{2}(n - |X_{l}| -1) < |C_{1}(l)|$. In either case, $|C_{1}(m)| < |C_{1}(l)|$, contradicting the choice of $l$. \end{case} \begin{case}[$X_{m}=X_{l} \setminus \{v\}$ where $v \in V(G)$] If $D_{1}(m) \subset D_{1}(l)$, then $|C_{1}(m)| \leq |C_{1}(l)|$. If $|C_{1}(m)| < |C_{1}(l)|$, then $|C_{1}(m)|$ is not the minimum amongst all $|C_{1}(j)|$, $j \in I$ and if $|C_{1}(m)| = |C_{1}(l)|$ then, since $|X_{m}| < |X_{l}|$, the choice of $l$ is contradicted. On the other hand, if $D_{1}(m) = T \setminus D_{1}(l)$, then $|C_{1}(m)|= |G \setminus (C_{1}(l) \cup X_{m})|=n - |C_{1}(l)| - |X_{m}| < n -\frac{1}{2}(n - |X_{l}| + 1) - |X_{l}| +1 =\frac{1}{2}(n - |X_{l}| +1)$ again contradicting the choice of $l$. \end{case} Hence $C_{1}(l) \leq \frac{1}{2}(n - |X_{l}| + 1)$ i.e., $G \setminus X_{l}= C_{1}(l) \uplus \cdots \uplus C_{t}(l)$ such that $|C_{j}(l)| \leq \frac{1}{2}(n- |X_{l}| + 1)$ for all $j \in [t]$. Consider a partition $I_{1} \uplus \cdots \uplus I_{r} = [t]$ with minimum possible $r$ such that $|\cup_{j \in I_{i}} C_{j}(l)| \leq \frac{1}{2}(n-|X_{l}| +1)$ for all $i \in [r]$. Let $\cup_{j \in I_{i}} C_{j}(l) = H_{i}$ for all $i \in [r]$. Rename all $H_{i}$'s such that $|H_{1}| \geq \cdots \geq |H_{r}|$. We claim that for such a partition $r \leq 3$ because if $r \geq 4$ then $|\cup_{j = \lceil \frac{r}{2} \rceil + 1}^{r} H_{j}| \leq \frac{1}{2}(n-|X_{l}|)$ by the pigeonhole principle contradicting the choice of the partition $I_{1} \uplus \cdots \uplus I_{r}$. Set $G_{i}=H_{i}$ for $i \in [3]$ and we are done. \end{proof} \begin{lemma}[Amalgamation Lemma for General Graphs]\label{amalgamDegen} Let $G=G_{1} \cup G_{2} \cup G_{3}$ where $G_{1}, G_{2}$ and $G_{3}$ are graphs such that $G_{i} \cap G_{j} = S$ for all $i,j \in [3]$ and $i \neq j$. Let $G_{1}', G_{2}'$ and $G_{3}'$ be graphs such that $V(G_{i}') = V(G_{i})$ and $E(G_{i}')=E(G_{i}) \cup \{\{v, v'\} : v, v' \in V(S)\}$ for all $i \in [3]$. Let $\phi_{G_{i}'}$ be an $l_{i}$-encoding of $G_{i}'$ for all $i \in [3]$ and $\phi_{S}$ be an $l_{s}$-encoding of $S$. Then we can construct an $l$-encoding of $G$, where \begin{eqnarray} l = \begin{cases} \max\{l_{1}, l_{2}, l_{3}\} + \max \{\chi(G \setminus S) + 1 , l_{s}\} & \textnormal{if $\chi(G \setminus S) =2$ or $6$} \\ \max\{l_{1}, l_{2}, l_{3}\} + \max \{\chi(G \setminus S), l_{s}\} & \textnormal{otherwise} \end{cases} \end{eqnarray} \begin{figure}[ht] \begin{center} % \input{amalgamGraphs.pstex_t} \psset{xunit=0.1\textwidth} \psset{yunit=0.1\textwidth} \begin{pspicture}(0,0.5)(10,3.5) % Petals \rput{90}(5,1){ \psframe[fillstyle=solid, opacity=0.2, fillcolor=gray](-0.3,-0.3)(0.3,2) \rput{*0}(0,2.3){$G_1$} } \rput{0}(5,1){ \psframe[fillstyle=solid, opacity=0.2, fillcolor=gray](-0.3,-0.3)(0.3,2) \rput{*0}(0,2.3){$G_2$} } \rput{-90}(5,1){ \psframe[fillstyle=solid, opacity=0.2, fillcolor=gray](-0.3,-0.3)(0.3,2) \rput{*0}(0,2.3){$G_3$} } % Core \rput(5,1){$S$} \end{pspicture} \caption{A graph $G= \cup_{i=1}^{3} G_{i}$ where $G_{i} \cap G_{j} = S$ for all $i,j \in [3]$ and $i \neq j$} \label{amalgamGraphs} \end{center} \end{figure} \end{lemma} \begin{proof} Without loss of generality we can assume that the alphabets used in $\phi_{S}$ are disjoint from the alphabets used in $\phi_{G_{i}'}$ for all $i \in [3]$ and greater than $\chi(G)$, and also from Observation \ref{extensionOfEncoding}, let $l_{1} = l_{2} = l_{3} = \max\{l_{1}, l_{2}, l_{3}\}$. Let $V(G)=\{v_{0}, \ldots , v_{n-1}\}$, $f: V(G) \rightarrow \{0, \ldots , n-1\}$ be a bijection, and $f_{i}=f(v_{i})$. Let us rename the alphabets in each coordinate of $\phi_{G_{i}'}$ such that all $v_{j} \in V(S)$ get the encoding as $(f_{j}, \ldots , f_{j})$ for all $i \in [3]$. Let $c : V(G \setminus S) \rightarrow \{0, \ldots, \chi(G \setminus S) - 1\}$ be an optimal proper coloring of the vertices $V(G \setminus S)$. %For any $i$, for every $x \in V(G_{i}')$, let $c(x)$ be the color that vertex $x$ gets when we do an optimal proper coloring of the vertices of $G \setminus S$ using colors from $\{ 0, \ldots, \chi(G \setminus S) - 1\}$. %Let $M$ be an alphabet such that $M$ is greater than all the alphabets used in the encodings $\phi_{S}$ and $\phi_{G_{i}'}$ for all $i \in [3]$. Let \begin{eqnarray} t= \begin{cases} \chi(G \setminus S) + 1 & \textnormal{if $\chi(G \setminus S) =2$ or $6$} \\ \chi(G \setminus S) & \textnormal{otherwise} \end{cases} \end{eqnarray} By Theorem 4.3 in \cite{evans2000representations}, if we have two orthogonal Latin squares of order $t$, we can have a $t$-encoding for $3K_{t}$ and hence, for $3 K_{\chi(G \setminus S)}$ as well. Let the $j$-th vertex in the $i$-th copy of $3 K_{\chi(G \setminus S)}$ get the encoding $\phi_{K}(i,j)$ for all $i \in [3]$ and $j \in [\chi(G \setminus S)]$. Note that $\phi_{K}(i,j)$ and $\phi_{K}(i,j')$, $j \neq j'$ disagree at all coordinates and $\phi_{K}(i,j)$ and $\phi_{K}(i',j')$, $i \neq i'$, agree in at least one coordinate, for all $i, i' \in [3]$ and $j,j' \in [\chi(G \setminus S)]$. Let $m = \max\{t, l_{s}\}$. From Observation \ref{extensionOfEncoding}, let $\phi_{S}$ and $\phi_{K}(i,j)$ be $m$-encodings of $S$ and $3K_{\chi(G \setminus S)}$ respectively. We construct an $l$-encoding of $G$, $\phi_{G}$, is as follows. %If $l_{s} \geq t$ % %\begin{equation} \label{encodeAmalGr1} % \phi _{G}(x) = \begin{cases} % \phi_{G_{i}'}(x) \phi_{K}(i,j) & \textnormal{if $x \in G_{i} \setminus S$ and $c(x)=j$} \\ % \phi_{G_{1}'}(x) \phi_{S}(x) & \textnormal{$x \in S$} % \end{cases} %\end{equation} % %If $l_{s} < t$ % %\begin{equation} \label{encodeAmalGr2} % \phi _{G}(x) = \begin{cases} % \phi_{G_{i}'}(x) \{c(x) + M\}^{l_{1}-l_{i}} \phi_{K}(i,j) & \textnormal{if $x \in G_{i} \setminus S$ and $c(x)=j$} \\ % \phi_{G_{1}'}(x) \{c(x) + M\}^{t - l_{s}} \phi_{S}(x) & \textnormal{$x \in S$} % \end{cases} %\end{equation} \begin{equation} \label{encodeAmal} \phi _{G}(x) = \begin{cases} \phi_{G_{i}'}(x) \phi_{K}(i,c(x)) & \textnormal{if $x \in G_{i} \setminus S$} \\ \phi_{G_{1}'}(x) \phi_{S}(x) & \textnormal{$x \in S$} \end{cases} \end{equation} We can verify that $\phi_{G}$ is a valid encoding of $G$ from the following argument. Let $x,y \in V(G_{i} \setminus S)$. If $\{x,y\} \not \in E(G)$, then $\{x,y\} \not \in E(G_{i}')$. Therefore, $\phi_{G_{i}'}(x)$ and $\phi_{G_{i}'}(y)$ agree in some coordinate, say $g$ and thus, $\phi_{G}(x)$ and $\phi_{G}(y)$ also agree in the $g$-th coordinate. If $\{x,y\} \in E(G)$, then $\{x,y\} \in E(G_{i}')$. Hence, $\phi_{G_{i}'}(x)$ and $\phi_{G_{i}'}(y)$ do not agree in any coordinate and since, $c$ is a proper coloring of $G \setminus S$, $c(x) \neq c(y)$. Thus, $\phi_{K}(i, c(x))$ and $\phi_{K}(i, c(y))$ do not agree in any coordinate. Therefore, $\phi_{G}(x)$ and $\phi_{G}(y)$ do not agree in any coordinate. Let $x \in V(G_{i} \setminus S)$ and $y \in V(G_{i'} \setminus S)$, $i\neq i'$. Note that $\{x,y\} \not \in E(G)$. Since $\phi_{K}(i,c(x))$ and $\phi_{K}(i', c(y))$, $i \neq i'$ agree in some coordinate, say $g$, $\phi_{G}(x)$ and $\phi_{G}(y)$ will agree in the $(l_{1} + g)$-th coordinate. For any $i$, let $x \in V(G_{i} \setminus S)$ and $y \in V(S)$. Since $\phi_{S}(y)$ uses new alphabets greater than $\chi_{G}$, $\phi_{G}(x)$ and $\phi_{G}(y)$ agree in some coordinate if and only if $\phi_{G_{i}'}(x)$ and $\phi_{G_{1}'} (y)$ ($= \phi_{G_{i}'}(y)$) agree in some coordinate. For $x,y \in V(S)$, if $\{x,y\} \in E(G)$, then since $\phi_{G_{1}'}(x)=(f(x), \ldots, f(x))$, $\phi_{G_{1}'}(y)=(f(y), \ldots, f(y))$ where $f$ is a bijection and $\phi_{S}(x)$ and $\phi_{S}(y)$ disagree in all coordinates, $\phi_{G}(x)$ and $\phi_{G}(y)$ disagree in all coordinates. If $\{x,y\} \not \in E(G)$, then $\{x,y\} \not \in E(S)$, Thus, $\phi_{S}(x)$ and $\phi_{S}(y)$ agree in some coordinate, say $g$ and therefore, $\phi_{G}(x)$ and $\phi_{G}(y)$ agree in the $(l_{1} + g)$-th coordinate. %Let $x,y \in V(G_{i} \setminus S)$. If $\{x,y\} \not \in E(G)$, then $\{x,y\} \not \in E(G_{i})$. Therefore, $\phi_{G_{i}'}(x)$ and $\phi_{G_{i}'}(y)$ agree in some coordinate, say $t$ and thus, $\phi_{G}(x)$ and $\phi_{G}(y)$ also agree in the $t$-th coordinate. If $\{x,y\} \in E(G)$, then since, $\phi_{K}(i,j)$ and $\phi_{K}(i,j')$, $j \neq j'$, do not agree in any coordinate and $c(x) \neq c(y)$, therefore, from Equations (\ref{encodeAmalGr1}) and (\ref{encodeAmalGr2}), $\phi_{G}(x)$ and $\phi_{G}(y)$ disagree in all coordinates. % %Let $x \in V(G_{i} \setminus S)$ and $y \in V(G_{k} \setminus S)$, $i\neq k$. Note that $\{x,y\} \not \in E(G)$. Since $\phi_{K}(i,j)$ and $\phi_{K}(k, j')$, $i \neq k$ agree in some coordinate, $\phi_{G}(x)$ and $\phi_{G}(y)$ will also agree in some coordinate. % %For any $i$, let $x \in V(G_{i} \setminus S)$ and $y \in V(S)$. Since $\phi_{S}(y)$ uses new alphabets, $M$ is sufficiently large and if $c(x) = c(y)$ then $\{x,y\} \not \in E(G)$, therefore, $\phi_{G}(x)$ and $\phi_{G}(y)$ agree in some coordinate if and only if $\phi_{G_{1}'}(x)$ and $\phi_{G_{i}'} (y)$ agree in some coordinate. % %For $x,y \in V(S)$, if $\{x,y\} \in E(G)$, then since $\phi_{S}(x)$ and $\phi_{S}(y)$ disagree in all coordinates and $\phi_{G_{1}'}(x)=(f(x), \ldots, f(x))$, $\phi_{G_{1}'}(y)=(f(y), \ldots, f(y))$ where $f$ is a bijection and $c(x) \neq c(y)$, therefore, $\phi_{G}(x)$ and $\phi_{G}(y)$ disagree in all coordinates. If $\{x,y\} \not \in E(G)$, then since $\phi_{S}(x)$ and $\phi_{S}(y)$ agree in some coordinate, then $\phi_{G}(x)$ and $\phi_{G}(y)$ will also agree in some coordinate. \end{proof} \begin{theorem} \label{thmTreeWidth} For any graph $G$ on $n$ vertices and $tw(G)=t$, $pdim(G) \leq (t+2)(\log n + 1)$. \end{theorem} \begin{proof} We use a divide and conquer strategy to prove the theorem. Let $\mathcal{G}_t(n)$ denote the set of all $n$-vertex graphs with treewidth at most $t$ and let $C_t(n) = \max \{ pdim(G) : G \in \mathcal{G}_t(n) \}$. \inlineHeading{Base case} By Theorem 4.3 in \cite{lovasz1980product}, $C_{t}(t+3) = t+2$. \inlineHeading{Divide and conquer} In our divide and conquer strategy, the divide operation corresponds to the splitting operation of Lemma \ref{splitDegen} and the conquer operation corresponds to the amalgamation operation of Lemma \ref{amalgamDegen}. By Lemma \ref{splitDegen}, for a graph $G$ on $n$ vertices with $tw(G)=t$ and a normalized tree decomposition $(\{X_{i} : i \in I\}, r \in I, T)$ of width $t$, there exists $l \in I$ such that $G \setminus X_{l} = G_{1} \uplus G_{2} \uplus G_{3}$, $|G_{i}| \leq \frac{1}{2}(n-|X_{l}| + 1)$, $i \in [3]$. Let $G_{i}'=G_{i} \cup G[X_{l}]$ for all $i \in [3]$. Therefore, $|G_{i}'| \leq \frac{1}{2}(n-|X_{l}|+1) + |X_{l}|=\frac{1}{2}(n+|X_{l}|+1)$ for all $i \in [3]$. Let $\alpha = \frac{1}{2}$ and $\beta = \frac{|X_{l}|+1}{2}$. Hence, $|G_{i}'| \leq \alpha n + \beta$ for all $i \in [3]$. Let $S = G[X_{l}]$.Note that $G_{i}' \cap G_{j}' =S$ for all $i,j \in [3]$ and $i \neq j$, and $G=G_{1}' \cup G_{2}' \cup G_{3}'$. Let $G_{1}^{''}, G_{2}^{''}, G_{3}^{''}$ be graphs such that $V(G_{i}^{''}) = V(G_{i}')$ and $E(G_{i}^{''})=E(G_{i}') \cup \{\{v, v'\}: v, v' \in V(S)\}$ for all $i \in [3]$ (note that $|G_{i}^{''}| \leq \alpha n + \beta,$ $i \in [3]$). Let $\phi_{G_{i}^{''}}$ is an $l_{i}$-encoding of $G_{i}^{''}$ for all $i \in[3]$ and $\phi_{S}$ be an $l_{s}$-encoding of $S$. Then, by Lemma \ref{amalgamDegen}, we can construct an $l$-encoding of $G$ where \begin{eqnarray} l = \begin{cases} \max\{l_{1}, l_{2}, l_{3}\} + \max\{\chi(G \setminus S) + 1 , l_{s}\} & \textnormal{if $\chi(G \setminus S) =2$ or $6$} \\ \max\{l_{1}, l_{2}, l_{3}\} + \max\{\chi(G \setminus S), l_{s}\} & \textnormal{otherwise}. \end{cases} \end{eqnarray} Since $G$ is a graph with $tw(G)=t$, $\chi(G) \leq t+1$(Theorem 6, \cite{lu2007note}), and hence $\chi(G \setminus S) \leq t+1$. Also, since $|V(S)| \leq t+1$, by Theorem 4.3 \cite{lovasz1980product}, $l_{s} \leq t+1$. Therefore, \begin{eqnarray} l \leq \begin{cases} \max\{l_{1}, l_{2}, l_{3}\} + \max\{t+2, t+1\} & \textnormal{if $\chi(G \setminus S) =2$ or $6$} \nonumber \\ \max\{l_{1}, l_{2}, l_{3}\} + \max\{t+1, t+1\} & \textnormal{otherwise} \nonumber \\ \end{cases} \end{eqnarray} Hence, \begin{eqnarray} l \leq \max\{l_{1}, l_{2}, l_{3}\} + t+2 \end{eqnarray} Let $G'$ be the graph such that $V(G') = V(G)$ and $E(G') = E(G) \cup \{\{v, v'\} : v , v' \in V(S)\}$. Note that $(\{X_{i} : i \in I\}, r \in I, T)$ is a tree decomposition for $G'$ too since all the new edges added are between the vertices of the same node. Also since $G \subset G'$, $tw(G) \leq tw(G')$. Hence, $tw(G') = t$ and thus, $tw(G_{i}^{''}) \leq t$ (since $G_{i}^{''} \subset G'$) for all $i \in [3]$. Therefore, the following recurrence relation holds. \begin{eqnarray} C_{t}(n) &\leq& C_{t}(\alpha n + \beta) + t+2 \nonumber \\ C_{t}(t+3) &\leq& t+2 \end{eqnarray} \inlineHeading{Solving the recurrence} Let $X$ be an arbitrary leaf in the recurrence tree and let $P$ denote the path from root to $X$. Let the number of divide operations along $P$ be $d$. Let $s_{j}$ be the size of the subgraph of $G$ to be conquered along $P$ after $j$ steps. Therefore, $s_{d} \leq \alpha^{d}n + \alpha^{d-1} \beta + \alpha^{d-2} \beta + \cdots + \alpha \beta + \beta \leq \alpha^{d}n + \frac{\beta}{1-\alpha} = \alpha^{d}n +|X_{l}|+1 \leq \alpha^{d}n +t+2$ (since $|X_{l}| \leq t+1$). Hence, $s_{d} \leq \lfloor \alpha^{d}n + t+2 \rfloor$. Note that the total cost of conquering incurred along $P$ is $(t+2)d$. %Since $X$ is arbitrary, %\begin{equation} %C(n) \leq (t+1)d + C(t+3) \nonumber \\ %\end{equation} Let $d \geq \log n$. Then $s_{d} \leq t+3$. Hence, $C_{t}(n) \leq (t+2)\log n + C_{t}(t+3) \leq (t+2) \log n + t+2 = (t+2)(\log n +1)$. Therefore, $pdim(G) \leq (t+2)(\log n + 1)$. \end{proof} \section{Product Dimension of $k$-degenerate Graphs} A graph $G$ is called $k$-degenerate if there exists an ordering $v_{1}, \ldots, v_{n}$ of $V(G)$ such that $|N(v_{i}) \cap \{v_{j} : j< i\}| \leq k, \, \forall i \in [n]$. Under an ordering $v_1, \ldots, v_n$ of $V(G)$, the set $N_{G}(v_{i}) \cap \{v_{j} : j< i\}$ is called the \emph{set of backward neighbors} of $v_{i}$. \begin{theorem} \label{thmDegenerate} For every $k$-degenerate graph $G$, $pdim(G) \leq \lceil 5.545 k \log n \rceil + 1$. \end{theorem} \begin{proof} Recall that the product dimension of a graph $G$ is the minimum number of proper colorings of $G$ such that any pair of non-adjacent vertices get the same color in at least one of the colorings and not in all of them. We use probabilistic arguments to prove the theorem. Let us describe a random coloring procedure using $3k$ colors for the vertices of $G$. Let $C=[3k]$ be the set of colors. Let $v_{1}, \ldots, v_{n}$ be an ordering of the vertex set of $G$ such that $|N(v_{i}) \cap \{v_{j} : j< i\}| \leq k$. We color the vertices starting from $v_{1}$ such that any vertex $v_{i}$ is assigned a color independently and uniformly at random from the set $C \setminus C_{i}$, where $C_{i}$ is the set of colors used by the backward neighbors of $v_{i}$. Note that $0 \leq |C_{i}| \leq k$. It is clear that the coloring thus obtained is proper. Repeat this procedure independently $r$ times to get $r$ random proper colorings of $G$. For $\{v_{i}, v_{j}\} \not \in E(G)$, let us calculate the probability that both $v_{i}$ and $v_{j}$ get the same color in a particular coloring. Let $C'=C \setminus (C_{i} \cup C_{j})$. Then the probability $p$ that both $v_{i}$ and $v_{j}$ get the same color in a particular coloring is equal to the probability that $v_{i}$ chooses a color from the set $C'$ and $v_{j}$ chooses the same color as chosen by $v_{i}$. Hence $p = \frac{|C'|}{|C \setminus C_{i}|} \frac{1}{|C \setminus C_{j}|} \geq \frac{3k - |C_i| - |C_j|}{(3k - |C_i|)(3k - |C_j|)}$. Let $f(x,y) = \frac{3k - x - y}{(3k - x)(3k - y)}$ for $x, y \in [0,k] \subset \mathbb{R}$. Since $\frac{\partial f(x,y)}{\partial x}, \frac{\partial f(x,y)}{\partial y} \leq 0$ for all $x, y \in [0,k]$, we infer that for any pair $x,y \in [0,k]$, $f(x,y) \geq f(x,k) \geq f(k,k) = 1/4k$. Hence $p \geq 1/4k$. So the probability that $v_{i}$ and $v_{j}$ get different colors in a particular coloring $ \leq (1-\frac{1}{4k})$ and the probability that $v_{i}$ and $v_{j}$ get different colors in all the $r$ colorings $ \leq (1-\frac{1}{4k})^{r} \leq e^{\frac{-r}{4k}}$. Hence, the probability that some pair of non-adjacent vertices get different colors in all the $r$ colorings $ < n^{2}e^{\frac{-r}{4k} }$. If $r \geq 8k \ln n = 5.545 k \log n$, $n^{2} e^{\frac{-r}{4k}} \leq 1$. Thus, if $r = \lceil 5.545 k \log n \rceil$, then every pair of non-adjacent vertices in the graph gets the same color in at least one of the $r$ colorings described above. To ensure that no pair of vertices get the same color in all colorings we also consider an $(r+1)$-th coloring where all vertices get a unique color. Thus $pdim(G) \leq \lceil 5.545 k \log n \rceil + 1$. \end{proof} \bibliographystyle{plain} \begin{thebibliography}{10} \bibitem{alles1986dimension} P.~Alles. \newblock Dimension of amalgamated graphs and trees. \newblock {\em Czechoslovak Mathematical Journal}, 36(3):393--416, 1986. \bibitem{alon1986covering} N.~Alon. \newblock Covering graphs by the minimum number of equivalence relations. \newblock {\em Combinatorica}, 6(3):201--206, 1986. \bibitem{bose1960further} R.C. Bose, S.S. Shrikhande, and E.T. Parker. \newblock Further results on the construction of mutually orthogonal {Latin} squares and the falsity of {Euler's} conjecture. \newblock {\em Canad. J. Math}, 12:189--203, 1960. \bibitem{chandran2007boxicity} L.S. Chandran and N.~Sivadasan. \newblock Boxicity and treewidth. \newblock {\em Journal of Combinatorial Theory, Series B}, 97(5):733--744, 2007. \bibitem{cooper10} Jeffery~R. Cooper. \newblock Product dimension of a random graph. \newblock Masters thesis, Miami University, Oxford, Ohio, 2010. \bibitem{eaton1996graphs} N.~Eaton and V.~R{\"o}dl. \newblock Graphs of small dimensions. \newblock {\em Combinatorica}, 16(1):59--85, 1996. \bibitem{erdos1989representations} P.~Erd{\"o}s and A.B. Evans. \newblock Representations of graphs and orthogonal {Latin} square graphs. \newblock {\em Journal of Graph Theory}, 13(5):593--595, 1989. \bibitem{evans2007representations} A.B. Evans. \newblock Representations of disjoint unions of complete graphs. \newblock {\em Discrete mathematics}, 307(9):1191--1198, 2007. \bibitem{evans2000representations} A.B. Evans, G.~Isaak, and D.A. Narayan. \newblock Representations of graphs modulo n. \newblock {\em Discrete Mathematics}, 223(1):109--123, 2000. \bibitem{furedi2000prague} Z.~F\"{u}redi. \newblock On the {Prague} dimension of {Kneser} graphs. \newblock {\em Numbers, information, and complexity}, page 125, 2000. \bibitem{kantor10} Ida Kantor. \newblock Graphs, codes, and colorings. \newblock {Ph.D} thesis, Graduate College of the University of Illinois at Urbana-Champaign, 2010. \bibitem{koster02} A.M.C.A. Koster, H.L. Bodlaender, and S.P.M. Van~Hoesel. \newblock Treewidth: computational experiments. \newblock Research Memoranda 0001, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization, 2001. \bibitem{lovasz1980product} L.~Lov{\'a}sz, J.~Ne\v{s}et\v{r}il, and A.~Pultr. \newblock On a product dimension of graphs. \newblock {\em Journal of Combinatorial Theory, Series B}, 29(1):47--67, 1980. \bibitem{lu2007note} C.~Lu. \newblock A note on lower bounds of treewidth for graphs. \newblock In {\em International Mathematical Forum}, volume~2, pages 2893--2898, 2007. \bibitem{nesetril1978simple} J.~Ne\v{s}et\v{r}il and V.~R{\"o}dl. \newblock A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph. \newblock {\em Discrete Mathematics}, 23(1):49--55, 1978. \bibitem{poljak1981dimension} S.~Poljak and A.~Pultr. \newblock On the dimension of trees. \newblock {\em Discrete Mathematics}, 34(2):165--171, 1981. \end{thebibliography} \end{document}