论文标题
有限度图的局部结构
The Local Structure of Bounded Degree Graphs
论文作者
论文摘要
令$ g =（v，e）$是一个简单的图形，具有最高度$ D $。对于\ Mathbb {n} $的整数$ k \，v $ in V $的$ k $ -disc定义为所有顶点所引起的$ g $的扎根子图，其距离$ v $的距离最多为$ k $。 $ k $ disc频率分布向量为$ g $，由$ \ text {freq} _ {k}（g）$表示，是由所有同构类型的drog $ k $ discess的向量索引。对于每个这样的同构类型$γ$，$ \ text {freq} _ {k}（g）中的相应条目计数$ v $中具有$ k $ disc同构为$γ$的$ v $中的顶点分数。从某种意义上说，$ \ text {freq} _ {k}（g）$是表示$ g $的“本地结构”的一种方法。图$ g $可以任意大，因此一个自然的问题是给定$ \ text {freq} _ {k}（g）$是否可以构造一个小图$ h $，其大小独立于$ | v | $，因此$ h $具有相似的本地结构。 N. Alon证明，对于任何$ε> 0 $，总是存在一个图$ h $，其大小独立于$ | v | $，其频率向量满足$ || \ text {freq} _ {k} _ {k}（g） - \ text {freq {freq} _ {k} _ {k}（k}（k}（k}（k）|| _ {1} {1} {1} {1} \ lelleε$。但是，他的证明只是存在的，并不意味着有一种确定性算法来构建此类图$ H $。他给出了一个公开的问题，即找到一种发现$ h $的明确确定性算法，或证明不存在这种算法。我们的主要结果是，当且仅当一个更普遍的问题（涉及有向边和边缘颜色）是不可确定的时，Alon的问题是不可决定的。我们还证明，当$ g $是一条路径时，对于特殊情况，这两个问题都是可决定的。我们表明，任何有向边的路径$ g $的本地结构都可以通过合适的固定尺寸的有向边色路径$ h $近似，我们给出了$ h $的大小。
Let $G=(V,E)$ be a simple graph with maximum degree $d$. For an integer $k\in\mathbb{N}$, the $k$-disc of a vertex $v\in V$ is defined as the rooted subgraph of $G$ that is induced by all vertices whose distance to $v$ is at most $k$. The $k$-disc frequency distribution vector of $G$, denoted by $\text{freq}_{k}(G)$, is a vector indexed by all isomorphism types of rooted $k$-discs. For each such isomorphism type $Γ$, the corresponding entry in $\text{freq}_{k}(G)$ counts the fraction of vertices in $V$ that have a $k$-disc isomorphic to $Γ$. In a sense, $\text{freq}_{k}(G)$ is one way to represent the "local structure" of $G$. The graph $G$ can be arbitrarily large, and so a natural question is whether given $\text{freq}_{k}(G)$ it is possible to construct a small graph $H$, whose size is independent of $|V|$, such that $H$ has a similar local structure. N. Alon proved that for any $ε>0$ there always exists a graph $H$ whose size is independent of $|V|$ and whose frequency vector satisfies $||\text{freq}_{k}(G)-\text{freq}_{k}(H)||_{1}\leε$. However, his proof is only existential and does not imply that there is a deterministic algorithm to construct such a graph $H$. He gave the open problem of finding an explicit deterministic algorithm that finds $H$, or proving that no such algorithm exists. Our main result is that Alon's problem is undecidable if and only if a much more general problem (involving directed edges and edge colors) is undecidable. We also prove that both problems are decidable for the special case when $G$ is a path. We show that the local structure of any directed edge-colored path $G$ can be approximated by a suitable fixed-size directed edge-colored path $H$ and we give explicit bound on the size of $H$.
