Skip to content
Snippets Groups Projects

Update comparable-box-dimension.tex

Merged Daniel Gonçalves requested to merge daniel.goncalves-main-patch-09954 into main
1 file
+ 4
4
Compare changes
  • Side-by-side
  • Inline
@@ -436,7 +436,7 @@ behave well with respect to full clique-sums.
sum extendable representation $h$ by comparable boxes in
$\mathbb{R}^{\max(d_1,d_2)}$.
\end{lemma}
The proof is in the appendix, but the idea is to translate (allowing
The proof is omitted, but the idea is to translate (allowing
also exchanges of dimensions) and scale $h_2$ to fit in
$h_1^\varepsilon(C_1)$.
The following lemma enables us to pick the root clique at the expense of increasing
@@ -446,7 +446,7 @@ the dimension by $\omega(G)$.
$C^\star$-clique-sum extendable touching representation by comparable
boxes in $\mathbb{R}^d$, for $d = |V(C^\star)| + \ecbdim(G\setminus V(C^\star))$.
\end{lemma}
The proof is also in the appendix, but it essentially the same as the one of
The proof is also omitted, but it is essentially the same as the one of
Lemma~\ref{lemma-apex}.
The following lemma provides an upper bound on $\ecbdim(G)$ in terms
of $\cbdim(G)$ and $\chi(G)$.
@@ -618,7 +618,7 @@ $h(v_i)[j] \cap h^\varepsilon(C)[j] = [p(C)[j],p(C)[j]+\varepsilon]$ for suffici
\end{proof}
The \emph{treewidth} $\tw(G)$ of a graph $G$ is the minimum $k$ such that $G$ is a subgraph of a $k$-tree.
Note that actually the bound on the comparable box dimension of Theorem~\ref{thm-ktree}
extends to graphs of treewidth at most $k$ (see the proof in the appendix).
extends to graphs of treewidth at most $k$ (proof omitted).
\begin{corollary}\label{cor-tw}
Every graph $G$ satisfies $\cbdim(G)\le\tw(G)+1$.
\end{corollary}
@@ -815,4 +815,4 @@ has a sublinear separator of size $O_{t,s,d}\bigl(|V(G)|^{\tfrac{d}{d+1}}\bigr).
\end{corollary}
\bibliography{data}
\end{document}
\ No newline at end of file
\end{document}
Loading