On two Turan numbers

Let H(3, 1) denote the complete bipartite graph K-3,K-3 with an edge deleted. For given graphs G and F, the Turan numbers ex(G, F) denote the maximum number of edges in a subgraph of G containing no copy of F. We prove that ex(K-n,(n), H(3, 1)) <= (4/root 7-n(3/2) + O(n) approximate to 1.5119n(3/2) + O(n) and that ex(K-n, H(3, 1)) <= (1/5)root 15n(3/2) + O(n) approximate to 0.7746n(3/2) + 0(n), which improve earlier results of Mubayi-West [13] and Furedi-West [10], respectively. The generalized Ramsey parameter r(G, F, q) denotes the minimum number of colors needed to edge-color G such that every copy of F in G receives at least q colors. As an immediate consequence, the above results imply that r(K-n,(n), K-3,(3),3) > (root 7/4-o(1))root n approximate to (0.6614 - o(1))root n and that r(K-n, K-3,K-3,3) > (root 15/6 - o(1)) root n approximate to (0.6455 - o(1))root n, respectively. These improve the corresponding bounds given by Mubayi [121 recently. (c) 2005 Wiley Periodicals, Inc.