同性恋数数树
Homomorphism Counts to Trees
Anuj Dawar
arXiv
2024年5月29日
我们构造一对非同构的双体图,这些图形不是通过计算任何树的同态数来区分的。 这回答了由Atserias等人激励的问题。 (LICS 2021 ) 。 为了建立结构,我们分析通过计算直径为2和3的树木的同态性而引起的等价关系,并获得必要和足够的条件,使两个图形等效。 我们证明三是我们施工的最佳直径。
We construct a pair of non-isomorphic, bipartite graphs which are not distinguished by counting the number of homomorphisms to any tree. This answers a question motivated by Atserias et al. (LICS 2021). In order to establish the construction, we analyse the equivalence relations induced by counting homomorphisms to trees of diameter two and three and obtain necessary and sufficient conditions for two graphs to be equivalent. We show that three is the optimal diameter for our construction.