The Density Turan Problem

Let H be a graph on n vertices and let the blow-up graph G[H] be defined as follows. We replace each vertex (nu i) of H by a cluster A(i) and connect some pairs of vertices of A(i) and A(j) if (v(i), v(j)) is an edge of the graph H. As usual, we define the edge density between A(i) and A(j) as d(A(i), A(j)) = e(A(i), A(j))/vertical bar A(i)vertical bar vertical bar A(j)|. We study the following problem. Given densities gamma(ij) for each edge (i, j) is an element of E(H), one has to decide whether there exists a blow-up graph G[H], with edge densities at least gamma(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 d(crit)(H) the maximal value for which there exists a blow-up graph G[H] with edge densities d(A(i), A(j)) = d(crit)(H) ((nu(i), nu(j)). 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 blow-up graph. Then we give general bounds on d(crit)(H) in terms of the maximal degree. In connection with the extremal structure, the so-called star decomposition is proved to give the best construction for H-transversal-free blow-up graphs for several graph classes. Our approach applies algebraic graph-theoretical, combinatorial and probabilistic tools.