Smaller universal targets for homomorphisms of edge-colored graphs

For a graph G, the density of G, denoted D(G), is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class $$\mathcal {F}$$ F of graphs, the value $$D(\mathcal {F})$$ D ( F ) is the supremum of densities of graphs in $$\mathcal {F}$$ F . A k-edge-colored graph is a finite, simple graph with edges labeled by numbers $$1,\ldots ,k$$ 1 , … , k . A function from the vertex set of one k-edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class $$\mathcal {F}$$ F of graphs, a k-edge-colored graph $$\mathbb {H}$$ H (not necessarily with the underlying graph in $$\mathcal {F}$$ F ) is k-universal for $$\mathcal {F}$$ F when any k-edge-colored graph with the underlying graph in $$\mathcal {F}$$ F admits a homomorphism to $$\mathbb {H}$$ H . Such graphs are known to exist exactly for classes $$\mathcal {F}$$ F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a k-uniform graph for a class $$\mathcal {F}$$ F is known to be $$\Omega (k^{D(\mathcal {F})})$$ Ω ( k D ( F ) ) and $$O(k^{{\left\lceil D(\mathcal {F}) \right\rceil }})$$ O ( k D ( F ) ) . In this paper we close the gap by improving the upper bound to $$O(k^{D(\mathcal {F})})$$ O ( k D ( F ) ) for any rational $$D(\mathcal {F})$$ D ( F ) .