The density Turán Problem

Let H be a graph on n vertices and let the blown-up graph G[H] be defined as follows. We replace each vertex vi of H by a cluster Ai and connect some pairs of vertices of Ai and Aj if (vi, vj) was an edge of the graph H. As usual, we define the edge density between Ai and Aj as d(Ai, Aj) = e(Ai,Aj) |Ai||Aj |. We study the following problem. Given densities γij for each edge (i, j) ∈ E(H). Then one has to decide whether there exists a blown-up graph G[H] with edge densities at least γij such that one cannot choose a vertex from each cluster so that the obtained graph is isomorphic to H, i.e, no H appears as a transversal in G[H]. We call dcrit(H) the maximal value for which there exists a blown-up graph G[H] with edge densities d(Ai, Aj) = dcrit(H) ((vi, vj) ∈ E(H)) not containing H in the above sense. Our main goal is to determine the critical edge density and to characterize the extremal graphs. First in the case of tree T we give an efficient algorithm to decide whether a given set of edge densities ensures the existence of a transversal T in the blown up graph. Then we give general bounds on d(H) in terms of the maximal degree. In connection with the extremal structure, the so-called star decomposition is proven to give the best construction for H-transversal-free blown-up graphs for several graph classes. Our approach applies algebraic graph theoretical, combinatorial and probabilistic tools