English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We show that feasibility of the $t^\text{th}$ level of the Lasserresemidefinite programming hierarchy for graph isomorphism can be expressed as ahomomorphism indistinguishability relation. In other words, we define a class$\mathcal{L}_t$ of graphs such that graphs $G$ and $H$ are not distinguished bythe $t^\text{th}$ level of the Lasserre hierarchy if and only if they admit thesame number of homomorphisms from any graph in $\mathcal{L}_t$. By analysingthe treewidth of graphs in $\mathcal{L}_t$ we prove that the $3t^\text{th}$level of Sherali--Adams linear programming hierarchy is as strong as the$t^\text{th}$ level of Lasserre. Moreover, we show that this is best possiblein the sense that $3t$ cannot be lowered to $3t-1$ for any $t$. The same resultholds for the Lasserre hierarchy with non-negativity constraints, which wesimilarly characterise in terms of homomorphism indistinguishability over afamily $\mathcal{L}_t^+$ of graphs. Additionally, we give characterisations oflevel-$t$ Lasserre with non-negativity constraints in terms of logicalequivalence and via a graph colouring algorithm akin to the Weisfeiler--Lemanalgorithm. This provides a polynomial time algorithm for determining if twogiven graphs are distinguished by the $t^\text{th}$ level of the Lasserrehierarchy with non-negativity constraints.

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability