Extremal problems concerning transformations of the set of edges of the complete graph (Q1088678)

Let \(E_ m\) be the set of all edges in a complete graph \(K_ m\) on m vertices. The authors investigate for given finite graphs \(G\), \(H\) the following functions: \(m(G,H) =\) the greatest integer \(m\), for which there exists such a function \(f: E_ m\mapsto E_ m\) that in no copy of G in \(K_ m\) is \(f(e)=e\) for all \(e\in E(G)\) and in no copy of \(H\) in \(K_ m\) is \(f(e)\not\in E(H)\) for all \(e\in E(H).\) \(\ell (m,H) =\) the greatest integer \(\ell\) for which there exists such a function \(f: E_ m\mapsto E_ m\) that f(e)\(\neq e\) for all \(e\in E_ m\) and in no copy of \(H\) in \(K_ m\) is \(f(e)\in E(H)\) for all \(e\in E(H).\) Some results are generalized for complete n-hypergraphs \(K_ m^{(n)}\) \((=hypergraphs\) on m vertices the edge sets \(E_ m^{(n)}\) of which are all n-subsets of the vertex set). The authors deal e.g. with the function: \(g(p,n) =\) the greatest integer \(g\) for which there exists such a function \(f: E_ m^{(n)}\mapsto E_ m^{(n)}\) that f(e)\(\neq e\) for all \(e\in E_ m^{(n)}\) and in no copy of \(K_ p^{(n)}\) in \(K_ m^{(n)}\) is \(f(e)\in E_ m^{(n)}-E_ p^{(n)}\) for all \(e\in E_ p^{(n)}.\) Some results concern the functions from n-subsets of a set to its r- subset. The main results are the following: Theorem 2.2. Let \(p\), \(n\), \(r\) be three positive integers, \(p\geq n,r\). There exists a smallest integer \(m=m(n,r,p)\) such that if \(M\) is a set of cardinality \(>m\) then for every function \(f\) from \([M]^ n\) \((=\) the family of all n-subsets of M) into \([M]^ r\) there exists a subset A of cardinality p of M such that: (a) If \(n>r\) then either \(f(v)\subset v\) for all \(v\in [A]^ n\) or \(f(v)\not\in [A]^ r\) for all \(v\in [A]^ n.\) (b) If \(n=r\) then either \(f(v)=v\) for all \(v\in [A]^ n\) or \(f(v)\not\in [A]^ r\) for all \(v\in [A]^ n.\) (c) If \(n<r\) then \(f(v)\not\in [A]^ r\) for all \(v\in [A]^ r.\) Theorem 3.1. Let \(K_{1,k}\) denote a star with k edges. For all \(r,t\geq 1\) \[ m(K_{1,t},K_{1,r})=2r+t-2. \] Theorem 4.1. For every \(p>n\geq 2\) \[ g(p,n)\leq n+\frac{r(r-1)...(r-n)}{n!(r-p+1)} \] for all \(r\geq p.\) Theorem 5.4. If H is a graph with chromatic number \(r\geq 2\) then \[ \lim_{m\to \infty}\ell (m,H)/m^ 2=\lim_{m\to \infty}ex(m,H)/m^ 2=(1-1/(r-1))/2, \] where \(ex(m,H)\) denotes the maximal number of edges in a graph on m vertices that contains no copy of H.