Hyperfinite graph limits
Hyperfinite graph limits
复制标题
超有限图极限
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
O. Schramm
中科院分区：
文献类型：
--
作者：
O. Schramm
G'abor Elek引入了超有限图族的概念：如果对于每个$epsilon> $存在一些有限的$k$，使得集合中的每个图$G$可以通过移除一组最大为$epsilon|V(G)|$的边而被分解成最大为$k$的连通分量，那么图集合就是超有限的。我们将这一概念推广到有限有界度图的某种紧化，并证明了如果一个有限图序列收敛于一个超有限极限，那么这个序列本身就是超有限的。
G'abor Elek introduced the notion of a hyperfinite graph family: a collection of graphs is hypefinite if for every $epsilon>0$ there is some finite $k$ such that each graph $G$ in the collection can be broken into connected components of size at most $k$ by removing a set of edges of size at most $epsilon|V(G)|$. We presently extend this notion to a certain compactification of finite bounded-degree graphs, and show that if a sequence of finite graphs converges to a hyperfinite limit, then the sequence itself is hyperfinite.