Bandwidth theorem for sparse graphs
Bandwidth theorem for sparse graphs
复制标题
稀疏图的带宽定理
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Hao;Choongbum Lee;B. Sudakov
一个图$G$被认为有 extit{bandwidth}至多$B$，如果存在由$1，2，.标记的顶点，n$，所以$|I - J| leq B$，只要${i，j}$是$G$的边。最近，Bottcher，Schacht和Taraz验证了Bollobas和Komlos的一个猜想，即对于每个正的r，Delta，gamma，存在eta$使得如果H$是一个最大度不超过$Delta$的n$-顶点r$-色图，它的带宽不超过$eta n$，则对于足够大的n$，任何n$顶点上最小度至少为（1 - 1/r + gamma）n$的图G$包含H$的一个拷贝。在本文中，我们将这个定理推广到稠密随机图。对于二分的$H$，这回答了Bottcher，Kohayakawa和Taraz的一个开放问题。看来，对于非二分的$H$的直接延伸是不可能的，并且需要另外的一些顶点的$H$有独立的邻域。我们还得到了G（n，p）的最小度为（1-1/r + gamma）np的生成子图中固定r-色图H 0的最大点不相交副本数的渐近紧界.
A graph $G$ is said to have extit{bandwidth} at most $b$, if there exists a labeling of the vertices by $1,2,..., n$, so that $|i - j| leq b$ whenever ${i,j}$ is an edge of $G$. Recently, Bottcher, Schacht, and Taraz verified a conjecture of Bollobas and Komlos which says that for every positive $r,Delta,gamma$, there exists $eta$ such that if $H$ is an $n$-vertex $r$-chromatic graph with maximum degree at most $Delta$ which has bandwidth at most $eta n$, then any graph $G$ on $n$ vertices with minimum degree at least $(1 - 1/r + gamma)n$ contains a copy of $H$ for large enough $n$. In this paper, we extend this theorem to dense random graphs. For bipartite $H$, this answers an open question of Bottcher, Kohayakawa, and Taraz. It appears that for non-bipartite $H$ the direct extension is not possible, and one needs in addition that some vertices of $H$ have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed $r$-chromatic graph $H_0$ which one can find in a spanning subgraph of $G(n,p)$ with minimum degree $(1-1/r + gamma)np$.