4
$\begingroup$

I'm trying to tackle the following problem: given two graphs $A$ and $B$, if there exists a graph $D$ such that $\hom(A, D) > \hom(B, D)$ (i.e. there is more homomorphisms from $A$ to $D$ than from $B$ to $D$), then for any $c > 0$ there is a graph $D_c$ such that $\hom(A, D_c) > c\cdot\hom(B, D_c)$.

The motivation for this comes from the query containment problem for the bag (multiset) semantics, whose decidability is an open problem. The antecedent of the implication is exactly the fact that $A$ is not contained in $B$ as conjunctive queries. The problem could be colloquially described with if ever $A$ is bigger than $B$, then we can explode $A$ relatively to $B$, hence the title.

I don't know if it is true in general, however, for any two $A$ and $B$ I could've thought, it is true. Also, there're some cases, where the problem can be easily proven, e.g. when $A$ has more vertices than $B$, or when there's no homomorphism from $B$ to $A$.

Do you know a solution to this problem? Or a counter-example? Or maybe any paper that may relate?

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ Can't you square $\mathrm{hom}(A,D)$ by taking the tensor product $D\times D$? $\endgroup$
    – Wei Zhan
    Jun 23 at 4:47
  • $\begingroup$ Or disjoint union of two copies of $D$ $\endgroup$
    – holf
    Jun 23 at 6:17
  • 2
    $\begingroup$ Indeed, the tensor product is the categorial product in the category of graph homomorphisms, hence it works. $\endgroup$
    – Emil Jeřábek
    Jun 23 at 6:55
  • $\begingroup$ @WeiZhan Yes, it seems like it is the case. Thanks. $\endgroup$
    – Franciszek Malinka
    Jun 23 at 10:27
  • $\begingroup$ @holf Unfortunately, it is not the case. Consider $A$ to be 1-2-3-4, and $B$ to be a 4-cycle. Then $A(A) = 16, B(A) = 14$, so we can take $D = A$. But for $D\sqcup\ldots\sqcup D$ the number of homomorphisms scales linearly for both $A$ and $B$. $\endgroup$
    – Franciszek Malinka
    Jun 23 at 10:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.