5
$\begingroup$

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)$.

$\endgroup$
5
  • 1
    $\begingroup$ What is the definition of homomorphism density? (Or else each of ignorant readers like me has to google and such). $\endgroup$ – Włodzimierz Holsztyński Apr 16 '14 at 18:13
  • 1
    $\begingroup$ 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)$. $\endgroup$ – user48339 Apr 16 '14 at 18:17
  • 1
    $\begingroup$ 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). $\endgroup$ – Włodzimierz Holsztyński Apr 16 '14 at 18:23
  • 1
    $\begingroup$ Yes, that's correct! $\endgroup$ – user48339 Apr 16 '14 at 18:58
  • 1
    $\begingroup$ 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.) $\endgroup$ – Ben Barber Apr 17 '14 at 11:00
3
$\begingroup$

Look into the work of Razborov on such questions using his "flag algebras" machine. For a directed graph example see his paper On the Caccetta-Haggkvist conjecture with forbidden subgraphs.

$\endgroup$
1
$\begingroup$

Very relevant to your question:

J. Hladký , D. Král, S. Norin: Counting flags in triangle-free digraphs.

Combinatorica 37 (2017), volume 37, issue 1, p. 49-76

arXiv-Version

Talk

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.