comparable-box-dimension.tex 63.6 KB
 Daniel Gonçalves committed Nov 30, 2021 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 \newtheorem*{corollary-C}{Corollary~\ref{cor-tw}} \begin{corollary-C} Every graph $G$ satisfies $\cbdim(G)\le\tw(G)+1$. \end{corollary-C} \begin{proof} Let $k=\tw(G)$. Observe that there exists a $k$-tree $T$ with the root clique $C^\star$ such that $G\subseteq T-V(C^\star)$. Inspection of the proof of Theorem~\ref{thm-ktree} (and Lemma~\ref{lem-cs}) shows that we obtain a representation $h$ of $T-V(C^\star)$ in $\mathbb{R}^{k+1}$ such that \begin{itemize} \item the vertices are represented by hypercubes of pairwise different sizes, \item if $uv\in E(T-V(C^\star))$ and $h(u)\sqsubseteq h(v)$, then $h(u)\cap h(v)$ is a facet of $h(u)$ incident with its point with minimum coordinates, and \item for each vertex $u$ and each facet of $h(u)$ incident with its point with minimum coordinates, there exists at most one vertex $v$ such that $uv\in E(T-V(C^\star))$ and $h(u)\sqsubseteq h(v)$. \end{itemize} If for some $u,v\in V(G)$, we have $uv\in E(T)\setminus E(G)$, where without loss of generality $h(u)\sqsubseteq h(v)$,  Torsten Ueckerdt committed Dec 01, 2021 1017 we now alter the representation by shrinking $h(u)$ slightly away from $h(v)$ (so that all other touchings are preserved).  Daniel Gonçalves committed Nov 30, 2021 1018 1019 1020 Since the hypercubes of $h$ have pairwise different sizes, the resulting touching representation of $G$ is by comparable boxes. \end{proof}  Zdenek Dvorak committed Sep 06, 2021 1021 \end{document}