Ordered and colored subgraph density problems

Abstract

We consider three extremal problems about the number of copies of a fixed graph in another larger graph. First, we correct an error in a result of Reiher and Wagner and prove that the number of $k$-edge stars in a graph with density $x\in [0,1]$ is asymptotically maximized by a clique and isolated vertices or its complement. Next, among ordered $n$-vertex graphs with $m$ edges, we determine the maximum and minimum number of copies of a $k$-edge star whose nonleaf vertex is minimum among all vertices of the star. Finally, for $s\ge 2$, we define a particular $3$-edge-colored complete graph $F$ on $2s$ vertices with colors blue, green and red, and determine, for each $(x_b,x_g)$ with $x_b+x_g\le 1$ and $x_b,x_g\ge 0$, the maximum density of $F$ in a large graph whose blue, green and red edge sets have densities $x_b,x_g$ and $1-x_b-x_g$, respectively. These are the first nontrivial examples of colored graphs for which such complete results are proved.

17 pages, 6 figures