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

Improve this question
$\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
    Commented Apr 16, 2014 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
    Commented Apr 16, 2014 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
    Commented Apr 16, 2014 at 18:23
  • 1
    $\begingroup$ Yes, that's correct! $\endgroup$
    – user48339
    Commented Apr 16, 2014 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
    Commented Apr 17, 2014 at 11:00

2 Answers 2

Reset to default
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.

Improve this answer
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .