The Study Of Lagrangians Of Hypergraphs

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Motzkin and Straus established a remarkable connection between the maximum clique and the Lagrangian of a graph in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique problem in graphs and it has also been applied in extremal problems in graph theory. However,the obvious generalization of Motzkin and Straus' result is false. Let Cm,T be the hypergraph with the set of edge types T and m edges formed by taking the first m sets with cardinality in T in the colex ordering.When T={r},we simply write Cm,{r} as Cm,r.In most applications,we need a good upper bound of the Lagrangian of a hypergraph. In 1980's,Frankl-Furedi conjectured that a r-graph G with m edges has L(G)?L(Cr,m),where L(G)is the Lagrangian of hypergraph G.In 2002,Talbot first gives some partial results about this conjecture.Later,Tang et al also comfirmed Frankl and Furedi's conjecture under some conditions.In Chapter 3,we show the following results:1.Let G=([t],E)be a left-compressed 3-graph with m edges and[t-1](3)(?) G,where(t-13)+(t-22)?m?(t3). Let(t—p—i)(t—p)t be the triple with the minimum colex ordering in Gc,the complement of G,and t—p—i—a min{Ec(t-1)t},where Ec(t-1)t={b?V:b?{t—1,t}?V(3)\E}.If i?p—a—1, then L(G)?L(G3,m).2.Let G=([t],E)be a left-compressed 3-graph with m edges and[t—1](3)(?) G,where (t-13)+(t-22)+1?m?(t3).If the triple with the minimum colex ordering in Gc,the complement of G,is(t—p—i)(t—p)t and t?(P-1)3(P-2)3/8(P-1)2-40+2p-1,then L(G)?L(G3,m).In Chapter 2,we also study a generalized Lagrangian of a non-uniform hy-pergraph H in which edges of differenct types have different 'weights'.For a non-uniform hypergraph H with edge type T and m edges,we ask whether L(H)? L(Cm,T). We give a complete answer to the question for{1,2}-hypergraphs in Section 2.1 and also give the connection between the generalized Lagrangian of {1,r1,r2,...,rl}-hypergraphs and{r1,r2,...,rl}-hypergraphs in Section 2.3.