论文标题
局部WL不变性和隐藏的规律性阴影
Local WL Invariance and Hidden Shades of Regularity
论文作者
论文摘要
$ k $二维WEISFEILER-LEMAN算法是图同构测试中的强大工具。对于输入图$ g $，该算法确定了$ s $ thutices $ g $的规范着色，每$ g $ 1 $ g $在1至$ k $之间。我们说，如果由元组颜色确定，则$ s $ tuples的数值参数为$ k $ -wl-invariant。作为Dvočhk的应用程序的应用，在同构的$ K $ -WL不变性上，我们发现了一些非常规则的图形和相关图形家族的一些不明确的规律性属性。例如，如果$ g $是一个强烈的规则图，则顶点$ x $ x $和$ y $ in $ g $之间的长度6的路径数仅取决于$ x $和$ y $是否相邻（而长度为6则最佳）。或者，通过$ g $中的顶点$ x $的长度7的循环数对于每$ x $都是相同的（其中长度7也是最佳的）。
The $k$-dimensional Weisfeiler-Leman algorithm is a powerful tool in graph isomorphism testing. For an input graph $G$, the algorithm determines a canonical coloring of $s$-tuples of vertices of $G$ for each $s$ between 1 and $k$. We say that a numerical parameter of $s$-tuples is $k$-WL-invariant if it is determined by the tuple color. As an application of Dvořák's result on $k$-WL-invariance of homomorphism counts, we spot some non-obvious regularity properties of strongly regular graphs and related graph families. For example, if $G$ is a strongly regular graph, then the number of paths of length 6 between vertices $x$ and $y$ in $G$ depends only on whether or not $x$ and $y$ are adjacent (and the length 6 is here optimal). Or, the number of cycles of length 7 passing through a vertex $x$ in $G$ is the same for every $x$ (where the length 7 is also optimal).
