{"ID":2892859,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.14669","arxiv_id":"2507.14669","title":"Dvorak-Dell-Grohe-Rattan theorem via an asymptotic argument","abstract":"Two graphs $G_1,G_2$ are distinguished by the Weisfeiler--Leman isomorphism test if and only if there is a tree $T$ that has a different number of homomorphisms to $G_1$ and to $G_2$. There are two known proofs of this fact -- a logical proof by Dvorak and a linear-algebraic proof by Dell, Grohe, and Rattan. We give another simple proof, based on ordering WL-labels and asymptotic arguments.","short_abstract":"Two graphs $G_1,G_2$ are distinguished by the Weisfeiler--Leman isomorphism test if and only if there is a tree $T$ that has a different number of homomorphisms to $G_1$ and to $G_2$. There are two known proofs of this fact -- a logical proof by Dvorak and a linear-algebraic proof by Dell, Grohe, and Rattan. We give an...","url_abs":"https://arxiv.org/abs/2507.14669","url_pdf":"https://arxiv.org/pdf/2507.14669v1","authors":"[\"Alexander Kozachinskiy\"]","published":"2025-07-19T15:40:28Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}