An extremal problem on v-partite graphs (Q789407)

Let r, t, and v be positive integers with 2\(\leq t\leq v\). For a fixed graph G with t vertices, denote by \(\Gamma\) (r,v,G) the set of all v- partite graphs H with vertex classes \(V_ i\), \(| V_ i| =r (i=1,2,...,v)\) satisfying the following condition: for every t-subset \(\{i_ 1,i_ 2,...,i_ t\}\) of \(\{\) 1,2,...,\(v\}\) there exists a subgraph of H isomorphic to G having exactly one vertex in each of the classes \(V_{i_{\tau}}\), \(\tau =1,2,...,t\). Let cl(H) denote the clique number of H. We are interested in determining the value of the class parameter \(D(r,v,G)=\min_{H\in \Gamma(r,v,G)}cl(H)\). The main result is given in the form of a Ramsey-type theorem: Theorem 2.2: Let \(q\geq 2\) and r be positive integers and G a graph with t vertices satisfying \(\chi(G)>r\). Then there exists a smallest integer W(r,q,G) such that for \(w\geq W(r,q,G)\) every graph \(H\in \Gamma(r,w,G)\) has the following property: Assume that the vertices of H are coloured with colours 1,2,...,r in such a way that any two distinct vertices of the same vertex class \(V_ i (i=1,2,...,w)\) have distinct colours (as for the rest, the coloration is arbitrary). Then H contains a monochromatic complete subgraph with q vertices. We shall show that for fixed r and G, D(r,v,G) tends to infinity when v tends to infinity. The authors define D(r,v,t) to be \(D(r,v,K_ t)\), where \(K_ r\) is the complete r-graph. After providing ''some easily obtainable results'' concerning lower bounds, they prove Theorem 3.1. For \(2\leq r<v\), \(D(r,v,r+1)\leq \min \{d\in {\mathbb{N}}:v\leq \left[ \begin{matrix} d\\ r\end{matrix} \right]r\}.\) Theorem 3.2. For \(2\leq r<t\leq r+g(r)\leq v, D(r,v,t)\leq r\lceil v^{1/r}\rceil\).