Source author record

Artem Govorov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity Discrete Mathematics math.DG

Catalog footprint

Research overview

5works

4topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

On a Theorem of Lovász that $\hom(\cdot, H)$ Determines the Isomorphism Type of $H$

Graph homomorphism has been an important research topic since its introduction [17]. Stated in the language of binary relational structures in that paper [17], Lovász proved a fundamental theorem that, for a graph $H$ given by its $0$ - $1$ valued adjacency matrix, the graph homomorphism function $G \mapsto \hom(G, H)$ determines the isomorphism type of $H$ . In the past 50 years various extensions have been proved by many researchers [18, 12, 1, 23, 21]. These extend the basic $0$ - $1$ case to admit vertex and edge weights; but these extensions all have some restrictions such as all vertex weights must be positive. In this paper we prove a general form of this theorem where H can have arbitrary vertex and edge weights. A noteworthy aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism effective in the following sense: it provides an algorithm that for any $H$ either outputs a P-time algorithm solving $\hom(\cdot, H)$ or a P-time reduction from a canonical #P-hard problem to $\hom(\cdot, H)$ .

preprint2020arXiv

A dichotomy for bounded degree graph homomorphisms with nonnegative weights

We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix $A$ . Each symmetric matrix $A$ defines a graph homomorphism function $Z_A(\cdot)$ , also known as the partition function. Dyer and Greenhill [10] established a complexity dichotomy of $Z_A(\cdot)$ for symmetric $\{0, 1\}$ -matrices $A$ , and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [4] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices $A$ . However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric $A$ , either $Z_A(G)$ is in polynomial time for all graphs $G$ , or it is #P-hard for bounded degree (and simple) graphs $G$ . We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [12] for $Z_A(\cdot)$ also holds for simple graphs, where $A$ is any real symmetric matrix.

preprint2020arXiv

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

The complexity of graph homomorphisms has been a subject of intense study [11, 12, 4, 42, 21, 17, 6, 20]. The partition function $Z_{\mathbf A}(\cdot)$ of graph homomorphism is defined by a symmetric matrix $\mathbf A$ over $\mathbb C$ . We prove that the complexity dichotomy of [6] extends to bounded degree graphs. More precisely, we prove that either $G \mapsto Z_{\mathbf A}(G)$ is computable in polynomial-time for every $G$ , or for some $Δ> 0$ it is #P-hard over (simple) graphs $G$ with maximum degree $Δ(G) \le Δ$ . The tractability criterion on $\mathbf A$ for this dichotomy is explicit, and can be decided in polynomial-time in the size of $\mathbf A$ . We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, $Z_{\mathbf A}(\cdot)$ can be constructed from $\mathbf A$ , in the respective cases.

preprint2020arXiv

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms

We develop a theory of graph algebras over general fields. This is modeled after the theory developed by Freedman, Lovász and Schrijver in [22] for connection matrices, in the study of graph homomorphism functions over real edge weight and positive vertex weight. We introduce connection tensors for graph properties. This notion naturally generalizes the concept of connection matrices. It is shown that counting perfect matchings, and a host of other graph properties naturally defined as Holant problems (edge models), cannot be expressed by graph homomorphism functions with both complex vertex and edge weights (or even from more general fields). Our necessary and sufficient condition in terms of connection tensors is a simple exponential rank bound. It shows that positive semidefiniteness is not needed in the more general setting.

preprint2013arXiv

A new example of a generic 2-distribution on a 5-manifold with large symmetry algebra

We discover a new example of a generic rank 2-distribution on a 5-manifold with a 6-dimensional transitive symmetry algebra, which is not present in Cartan's classical five variables paper. It corresponds to the Monge equation z' = y + (y'')^(1/3) with invariant quartic having root type [4], and a 6-dimensional non-solvable symmetry algebra isomorphic to the semidirect product of sl(2) and the 3-dimensional Heisenberg algebra.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Artem Govorov

Research overview

Is this your work?

5 publications

On a Theorem of Lovász that $\hom(\cdot, H)$ Determines the Isomorphism Type of $H$

A dichotomy for bounded degree graph homomorphisms with nonnegative weights

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms

A new example of a generic 2-distribution on a 5-manifold with large symmetry algebra

See the researcher in context

Building this map preview

Artem Govorov

Research overview

Is this your work?

5 publications

On a Theorem of Lovász that hom⁡(⋅,H)\hom(\cdot, H)hom(⋅,H) Determines the Isomorphism Type of HHH

A dichotomy for bounded degree graph homomorphisms with nonnegative weights

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms

A new example of a generic 2-distribution on a 5-manifold with large symmetry algebra

See the researcher in context

Building this map preview

On a Theorem of Lovász that $\hom(\cdot, H)$ Determines the Isomorphism Type of $H$