solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3613次
A bandwidth theorem for approximate decompositions. (arXiv:1712.04562v1 [math.CO])
来源于:arXiv
We provide a degree condition on a regular $n$-vertex graph $G$ which ensures
the existence of a near optimal packing of any family $\mathcal H$ of bounded
degree $n$-vertex $k$-chromatic separable graphs into $G$. In general, this
degree condition is best possible.
Here a graph is separable if it has a sublinear separator whose removal
results in a set of components of sublinear size. Equivalently, the
separability condition can be replaced by that of having small bandwidth. Thus
our result can be viewed as a version of the bandwidth theorem of B\"ottcher,
Taraz and Schacht in the setting of approximate decompositions.
More precisely, let $\delta_k$ be the infimum over all $\delta\ge 1/2$
ensuring an approximate $K_k$-decomposition of any sufficiently large regular
$n$-vertex graph $G$ of degree at least $\delta n$. Now suppose that $G$ is an
$n$-vertex graph which is close to $r$-regular for some $r \ge
(\delta_k+o(1))n$ and suppose that $H_1,\dots,H_t$ is a sequence of bounded
degre 查看全文>>