<p>I'm trying to tackle the following problem: given two graphs <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, if there exists a graph <span class="math-container">$D$</span> such that <span class="math-container">$\hom(A, D) &gt; \hom(B, D)$</span> (i.e. there is more homomorphisms from <span class="math-container">$A$</span> to <span class="math-container">$D$</span> than from <span class="math-container">$B$</span> to <span class="math-container">$D$</span>), then for any <span class="math-container">$c &gt; 0$</span> there is a graph <span class="math-container">$D_c$</span> such that <span class="math-container">$\hom(A, D_c) &gt; c\cdot\hom(B, D_c)$</span>.</p>
<p>The motivation for this comes from the query containment problem for the bag (multiset) semantics, <a href="https://ceur-ws.org/Vol-1087/keynote2slides.pdf" rel="nofollow noreferrer">whose decidability is an open problem</a>. The antecedent of the implication is exactly the fact that <span class="math-container">$A$</span> is not contained in <span class="math-container">$B$</span> as conjunctive queries. The problem could be colloquially described with <em>if ever <span class="math-container">$A$</span> is bigger than <span class="math-container">$B$</span>, then we can explode <span class="math-container">$A$</span> relatively to <span class="math-container">$B$</span></em>, hence the title.</p>
<p>I don't know if it is true in general, however, for any two <span class="math-container">$A$</span> and <span class="math-container">$B$</span> I could've thought, it is true. Also, there're some cases, where the problem can be easily proven, e.g. when <span class="math-container">$A$</span> has more vertices than <span class="math-container">$B$</span>, or when there's no homomorphism from <span class="math-container">$B$</span> to <span class="math-container">$A$</span>.</p>
<p>Do you know a solution to this problem? Or a counter-example? Or maybe any paper that may relate?</p>

CC BY-SA 4.0
2023-06-23T04:47:34.683Z
Can't you square $\mathrm{hom}(A,D)$ by taking the tensor product $D\times D$?
Wei Zhan
CC BY-SA 4.0
2023-06-23T06:17:28.490Z
Or disjoint union of two copies of $D$
holf
CC BY-SA 4.0
2023-06-23T06:55:24.803Z
Indeed, the tensor product is the categorial product in the category of graph homomorphisms, hence it works.
Emil Jeřábek
CC BY-SA 4.0
2023-06-23T10:27:09.120Z
@WeiZhan Yes, it seems like it is the case. Thanks.
Franciszek Malinka
CC BY-SA 4.0
2023-06-23T10:27:15.537Z
@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$.
Franciszek Malinka
CC BY-SA 4.0
2023-06-23T11:40:23.040Z
indeed, I was too quick to answer!
holf
<graph-theory><co.combinatorics><open-problem><db.databases><finite-model-theory>
Exploding number of homomorphisms
Franciszek Malinka
# Exploding number of homomorphisms

(Asked by: username_0 on 2023-06-22)

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](https://ceur-ws.org/Vol-1087/keynote2slides.pdf). 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?

**Tags:** graph-theory, co.combinatorics, open-problem, db.databases, finite-model-theory
> **Comments:**
> **username_1**: Can't you square $\mathrm{hom}(A,D)$ by taking the tensor product $D\times D$?  
> **username_2**: Or disjoint union of two copies of $D$  
> **username_3**: Indeed, the tensor product is the categorial product in the category of graph homomorphisms, hence it works.  
> **username_0**: @WeiZhan Yes, it seems like it is the case. Thanks.  
> **username_0**: @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$.  
> **username_2**: indeed, I was too quick to answer!  

---

## 0 answers

