Ramsey And Turán Problems Of R-uniform Hypergraphs

Determining Ramsey numbers has been attracting a lot of attention in the study of graph theory.Burr[10]showed that for a connected graph G and a graph H with v(G)?s(H),the Ramsey number R(G,H)?(v(G)-1)(?(H)-1)+s(H),where v(G)is the order of G,?(H)is the chromatic number of H and s(H)is the chromatic surplus of H.A connected graph G of order n is called H-good if R(G,H)=(n-1)(?(H)-1)+s(H).Chvátal[17]showed that any tree is K_m-good and Chvátal-Harary[18]showed that any tree is 2K₂-good.In this paper,we give the exact value of R(T_n,2K_m)and show that any tree T_nwith n vertices is2K_m-good,which confirms a conjecture in Sudarsana-Adiwijaya-Musdalifah[87].Determining the Turán number and Turán density of an r-uniform hypergraph is a central and challenging problem in extremal graph theory.We know very few about the Turán densities of hypergraphs.Even the conjecture given by Turán on the Turán density of K₄³,the smallest complete hypergraph remains open.The hy-pergraph Lagrangian method is a powerful tool to solve the Turán problems.The Lagrangian density is closely related to the Turán density.Sidorenko[75]showed that the Lagrangian density of an r-graph F is the Turán density of the extension of F,and obtained the Turán density of a series of infinite hypergraphs by deter-mining the Lagrangian density of a series of infinite hypergraphs.Determining the Lagrangian densities of K₄³and K₄^3-are equivalent to obtain the Turán density of K₄³(a long-standing conjecture given by Turán)and K₄^3-(a well-known conjec-ture of Frankl and Füredi)respectively.So researching on Lagrangian densities of hypergraphs is helpful to better understand the behavior of the Turán densities of hypergraphs.For positive integer t,let P_3,tbe the disjoint union of a 3-uniform linear path of length 3 and t pairwise disjoint edges.We determine the Lagrangian density of P_3,tfor any t.Applying a modified version of Pikhurko's transference argument used by Brandt-Irwin-Jiang[9],we obtain the Turán numbers of its ex-tension.Let H_t^r,sdenote the(r-s)-fold enlargement of the s-uniform matching of size t.Sidorenko[77]determined the Lagrangian density of H_t^r,2,where r=3or 4 and t?2,or r=5 and t?4,or r=6 and t?6.By using the so-called generalised Lagrangian of hypergraphs,Jenssen[51]determined the Lagrangian density of H₂^r,2,where r?{3,4,5,6,7}.So there are still some gaps between the results of Jenssen and Sidorenko.In this paper we fill the gaps for r=5 or 6.We also determine the Lagrangian densities of H_t^r,2,H₂^5,3,H_t^r,3,where t?3 and r=5or 6.Given r graphs F₁,F₂,...,F_r,the Turán-type Ramsey number,denoted by T(n;F₁,F₂,...,F_r),is defined as the maximum number of edges in an r-colored graph G with n?R(F₁,F₂,...,F_r)vertices such that it does not contain an F_iin the ith color for each 1?i?r.Sós[81]solved this question when every F_iis a complete graph.Erd?s-Hajnal-Simonovits-Sós-Szemerédi[28]gave the asymptotic value of T(n;F₁,...,F_r)if there is some i?[r],such that F_iis not bipartite.It's interesting to determine T(n;F₁,...,F_r)if all F_i's are bipartite graphs.In this paper,we give the exact value of T(n;C₄,K_1,3)and obtain the asymptotic value of T(n;C₄,K_1,t)for all t?4.