论文标题
在有限程度的图表上，反刺性和同态性不可分化
Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree
论文作者
论文摘要
我们引入了图形的（弱）反态性，这些图形是同构的，具有基于平等的其他约束。这些地图证明具有有趣的特性（例如，它们保持平面度），特别是与同态性不可区分有关。 图形$ g $和$ h $是 *同构属于家庭$ \ mathcal {f} $如果$ \ hom（f，g）= \ hom（f，h）$ in \ mathcal {f，f，h）$ in \ mathcal {f，f，f，h）$ in \ nathcal {f} $，where $ \ hom（f，g）$（f，g）$是$ f $ f $ f $ f $ f $ f $ f，洛瓦斯（Lovász）的经典结果说，同构等于所有图表的同构性不可区分。近年来，已经表明，许多同态性关系不可分性的关系具有自然的代数和/或逻辑表述。目前，该领域的许多研究都集中在寻找此类重新审计上。我们旨在通过引入新的概念/构造并提出几种猜想/问题来扩大目前关于同态研究的范围。特别是，我们猜想每个家庭都在脱节工会下关闭，未成年人产生了独特的同态性关系。 我们还表明，如果$ \ nathcal {f} $是在不相交的工会下关闭的一系列图表，对连接组件的限制和弱的异态，则$ \ nathcal {f} $满足一定的最大或闭合属性：$ \ nathcal {$ \ g $ g $ g $ g $ g $ gon $ h. $ \ hom（f，g）= \ hom（f，h）$对于任何$ f \ notin \ mathcal {f} $。这使我们能够回答十多年前提出的一个问题，表明在界图上的同态性格不可区分性不等于同构。
We introduce (weak) oddomorphisms of graphs which are homomorphisms with additional constraints based on parity. These maps turn out to have interesting properties (e.g., they preserve planarity), particularly in relation to homomorphism indistinguishability. Graphs $G$ and $H$ are *homomorphism indistinguishable* over a family $\mathcal{F}$ if $\hom(F,G) = \hom(F,H)$ for all $F \in \mathcal{F}$, where $\hom(F,G)$ is the number of homomorphisms from $F$ to $G$. A classical result of Lovász says that isomorphism is equivalent to homomorphism indistinguishability over the class of all graphs. In recent years it has been shown that many homomorphism indistinguishability relations have natural algebraic and/or logical formulations. Currently, much research in this area is focused on finding such reformulations. We aim to broaden the scope of current research on homomorphism indistinguishability by introducing new concepts/constructions and proposing several conjectures/questions. In particular, we conjecture that every family closed under disjoint unions and minors gives rise to a distinct homomorphism indistinguishability relation. We also show that if $\mathcal{F}$ is a family of graphs closed under disjoint unions, restrictions to connected components, and weak oddomorphisms, then $\mathcal{F}$ satisfies a certain maximality or closure property: homomorphism indistinguishability over $\mathcal{F}$ of $G$ and $H$ does not imply $\hom(F,G) = \hom(F,H)$ for any $F \notin \mathcal{F}$. This allows us to answer a question raised over ten years ago, showing that homomorphism indistinguishability over graphs of bounded degree is not equivalent to isomorphism.
