The number of homomorphisms and independent sets I got this question from my Graph Theory professor.
Prove that there exists a graph $H$ (not necessarily simple) such that for every simple graph $G$, the number of independent sets in $G$ is equal to the number of homomorphisms from $G$ to $H$.
An independent set is a subset of the vertices of a graph such that no two vertices in the subset are connected by an edge. A homomorphism from a graph $G$ to a graph $H$ is a function $f$ that maps the vertices of $G$ to the vertices of $H$ and preserves the edges of the graphs. This means that, if $(u,v)$ is an edge in $G$, then $(f(u), f(v))$ is an edge in $H$.
I have no visualization of the problem and don't know where to start.
 A: The answer is Example 2.1 in this paper. The graph $H$ has two vertices $\{1,2\}$ and the edges $11,12$. A map $f$ is a homomorphism if and only if the vertices mapped to $2$ form an independent set.
A: To prove that such a graph H exists, we can use the probabilistic method. This means that we will assume that the graph H is randomly chosen, and then we will show that the probability that H has the desired properties is positive.
First, let's consider a simple graph G with n vertices and m edges. The number of independent sets in G is equal to the sum of the weights of all vertices in the independent set complex of G, where the weight of a vertex is 1 if it is in the independent set and 0 if it is not. The independent set complex of G is a simplicial complex whose vertices are the independent sets of G, and whose simplices are collections of independent sets that can be obtained by taking the union of any number of independent sets.
Now, let's consider a randomly chosen graph H with n vertices and m edges. The probability that a given independent set S in G is mapped to an independent set in H by a homomorphism from G to H is equal to the probability that the vertices in S are mapped to an independent set in H. This probability is equal to the ratio of the number of independent sets in H to the total number of subsets of the vertices of H. Since H has n vertices, there are 2^n possible subsets of its vertices.
Therefore, the probability that a given independent set S in G is mapped to an independent set in H is equal to 1/2^n. Since there are a total of 2^n independent sets in G, the probability that all independent sets in G are mapped to independent sets in H is equal to (1/2^n)^(2^n) = 1/2^(n*2^n).
Since this probability is positive, there must exist at least one graph H that has the desired property. Therefore, there exists a graph H such that for every simple graph G, the number of independent sets in G is equal to the number of homomorphisms from G to H.
