# Extremal graph theory for directed graphs

In extremal graph theory, there are results such as $$t(C_4,G)\geq t(K_2,G)^4,$$ where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and $t(\cdot,G)$ denotes homomorphism density in $G$. Are the similar results for directed graphs, e.g. if $C_4$ is a directed cycle and $G$ is a directed graph?

The homomorphism density $t(F,G)$ of a graph F in G is $\frac{hom(F,G)}{|V(G)|^{|V(F)|}}$, where $hom(F,G)$ is the number of homomorphisms (adjacency-preserving maps) from $V(F)$ to $V(G)$.

• What is the definition of homomorphism density? (Or else each of ignorant readers like me has to google and such). Commented Apr 16, 2014 at 18:13
• The homomorphism density $t(F,G)$ of a graph $F$ in $G$ is $\frac{hom(F,G)}{|V(G)|^{|V(F)|}}$, where $hom(F,G)$ is the number of homomorphisms (adjacency-preserving maps) from $V(F)$ to $V(G)$. Commented Apr 16, 2014 at 18:17
• Thank you. Thus if there are no loops (edges which have the same vertex as both ends) then these homomorphisms are injective, right? -- just to make sure. Also, you could append your question with your definition (you know how lazy the ignorant readers can be--they may miss your comment). Commented Apr 16, 2014 at 18:23
• Yes, that's correct! Commented Apr 16, 2014 at 18:58
• Usually homomorphisms are not taken to be injective: that's exactly why they're easier to count than subgraphs. So you can map two vertices to the same point, but only if there is no edge between them. All odd cycles have a homomorphism onto the triangle, for example. (Even cycles do too, but in a boring way.) Commented Apr 17, 2014 at 11:00