極值問題

姚宇萍++彭岳建??

摘 要 設G=（[t]，E）是一個有m條邊的左壓的3一致超圖，其中（t-13）+（t-22）+1≤m≤（t3），并設[t-2]（3）G.本文證明，如果按同余字典序排列Ect中最小元素是（t-p-i）（t-p）并且t≥（p-1）3（p-2）38（p-1）2-40+2p-1，則有λ（G）≤λ（C3，m）.

關鍵詞 拉格朗日；Frankl and Füredi 猜想；同余字典序

For a set V and a positive integer r， let V（r） denote the family of all rsubsets of V. An runiform graph or rgraph G consists of a set V（G） of vertices and a set E（G）V（G）（r） of edges. An edge e={a1，a2，…，ar} will be simply denoted by a1a2…ar. An rgraph H is a subgraph of an rgraph G， denoted by HG if V（H）V（G） and E（H）E（G）. The complement of an rgraph G is denoted by Gc. A complete rgraph on t vertices is also called a clique of order t. Let N be the set of all positive integers. For any integer n∈N， we denote the set {1， 2， 3， …，n} by [n]. Let [n]（r） represent the complete runiform graph on the vertex set [n].

Definition 1 For an runiform graph G with the vertex set [n]， edge set E（G） and a vector.x=（x1，…，xn）∈Rn， define

λ（G，x）=∑i1i2…ir∈E（G）xi1xi2…xir.

Let S={x=（x1， x2，…，xn）：∑ni=1xi=1，xi≥0 for i=1，2，…，n}. The Lagrangian of G， denote by λ（G）， is defined as

λ（G）=max{λ（G，x）：x∈S}.

A vector y∈S is called an optimal weighting for G if λ（G，y）=λ（G）.

In [1]， Motzkin and Straus provided the following simple expression for the Lagrangian of a 2graph.

Theorem 1（Motzkin and Straus[1]） If G is a 2graph in which a largest clique has order t then λ（G）=λ（[t]（2））=12（1-1t）.

The obvious generalization of Motzkin and Straus result to hypergraphs is false because there are many examples of hypergraphs that do not achieve their Lagrangian on any proper subhypergraph. Indeed， estimating the Lagrangian of a hypergraph is much difficult. Lagrangians of hypergraphs has been proved to be a useful tool in hypergraph extremal problems. In most applications， an upper bound of the Lagrangians of certain class of hypergraphs is needed. Frankl and Füredi [2] asked the following question. Given r≥3 and m∈N， how large can the Lagrangian of an rgraph with m edges be？ For distinct A，B∈N（r） we say that A is less than B in the colex order if max（AΔB）∈B， where AΔB=（A＼B）∪（B＼A）. Let Cr，m be the runiform hypergraph with m edges formed by taking the first m sets in the colex order of N（r）. The following conjecture of Frankl and Füredi （if it is true） provides a solution to the question mentioned at the beginning.

Conjecture 1 （Frankl and Füredi[2]） If G is a rgraph with m edges， then λ（G）≤λ（Cr，m）.

This conjecture is true when r=2 by Theorem 1. For the case r=3， Talbot in [3] first confirmed Frankl and Füredis conjecture for r=3 and （t-13）-2≤m≤（t-13）+（t-22）-（t-1）. Later， Tang et.al. [46] extended Talbots result to （t-13）-7≤m≤（t-13）+（t-22）-t-22 for r=3. It seems to be very challenging to confirm this conjecture even for r=3.

Definition 2 An rgraph G=（[n]，E） is leftcompressed if j1j2…jr∈E implies i1i2…ir∈E provided ip≤jp for every p，1≤p≤r.

Talbot in [3] showed that to verify this conjecture for r=3， it is sufficient to show that for a leftcompressed 3graph G on the vertex set [t] with m edges， where （t-13）≤m≤（t3）， the inequality λ（G）≤λ（C3，m） holds. Peng and Zhao[4] showed that a leftcompressed 3graph with t vertices and m edge， say G， where （t-13） ≤m<（t3） and the maximun clique is t-1， has λ（G）≤λ（C3，m） hold. Yao and Peng also proved if the triple with the minimum colex ordering in Gc is （t-p-i）（t-p）t and t≥（p-1）3（p-2）38（p-1）2-40+2p-1， then λ（G）≤λ（C3，m）.

For an rgraph G=（V，E）， denote the （r-1）neighborhood of a vertex i∈V by Ei={A∈V（r-1）： A∪{i}∈E}. Similarly， denote the （r-2）neighborhood of a pair of vertices i， j∈V by Eij={B∈V（r-2）：B∪{i， j}∈E}. Denote the complement of Ei by Eci={A∈V（r-1）：A∪{i}∈V （r）＼E}. Also， denote the complement of Eij by Ecij={B∈V（r-2）：B∪{i，j}∈V（r）＼E}. Denote Ei＼j=Ei∩Ecj .

We are going to prove the following result.

Theorem 2 Let G=（[t]，E） be a leftcompressed 3graph with m edges， where （t-13）+（t-22）+1≤m≤（t3）. Let [t-2]（3）G. If the triple with the minimum colex order in Ect， the complement of Et， is （t-p-i）（t-p） and t≥（p-1）3（p-2）38（p-1）2-40+2p-1， then λ（G）≤λ（C3，m）.

The remaining proof of this paper is organized as follows. In Section 1， we give some premilinary results. In Section 2， we give the proof of Theorem 2.

1 Preliminaries

We will impose one additional condition on any optimal weighting. x=（x1，x2，…，xn） for an rgraph G：

|{i：xi>0}| is minimal， i.e. if y is a legal weighting for G satisfying |{i：yi>0}|<|{i：xi>0}|， then λ（G，y）<λ（G）.（1）

Remark 1 An rgraph G=（[n]，E） is leftcompressed if and only if Ej＼i= for any 1≤i

The following lemma gives some necessary conditions of an optimal weighting for G.

Lemma 1（Frankl and Rdl [5]） Let G=（V，E） be an rgraph on the vertex set [n] and x=（x1，x2，…，xn） be an optimal weighting for G with k（≤n） nonzero weights x1，x2，…，xk satisfying condition （1）. Then for every {i，j}∈[k]（2）， （I）λ（Ei，x）=λ（Ej，x）=rλ（G）， （Ⅱ） there is an edge in E containing both i and j.

Remark 2 Let G=（V，E） be an rgraph on the vertex set [n] and x=（x1，x2，…，xn） be an optimal weighting for G with k（≤n） nonzero weights x1，x2，…，xk satisfying condition （1）.

（a） In Lemma 1， part （Ⅰ） implies that

xjλ（Eij，x）+λ（Ei＼j，x）=xiλ（Eij，x）+λ（Ej＼i，x）.

In particular， if G is leftcompressed， then

（xi-xj）λ（Eij，x）=λ（Ei＼j，x）

for any i， j satisfying 1≤i

（b） If G is leftcompressed， then for any i， j satisfying 1≤i

xi-xj=λ（Ei＼j，x）λ（Eij，x）（2）

holds. If G is leftcompressed and Ei＼j= for i， j satisfying 1≤i

（c） By （2）， if G is leftcompressed， then an optimal legal weighting x=（x1，x2，…，xn） for G must satisfy

x1≥x2≥…≥xn≥0.（3）

We will also give some useful results to apply the following results in the proof.

Lemma 2（Tang et al[6]） Let m， i and t be positive integers satisfying （t-13）+（t-22）+1≤m≤（t3）-1. Let G=（[t]，E） be a leftcompressed 3graph with m edges and [t-1]（3）G. If the triple with the minimum colex order in Gc is （t-2-i）（t-2）t， then λ（G）≤λ（C3，m）.

Lemma 3（Sun et al[7]） Let m， i and t be positive integers satisfying （t-13）+（t-22）+1≤m≤（t3）-1. Let G=（[t]，E） be a leftcompressed 3graph with m edges and [t-1]（3）G. If the minimum colex order in Gc is （t-3-i）（t-3）t， then λ（G）≤λ（C3，m）.

Theorem 3（Sun et al） Let m， i and t be positive integers satisfying （t-13）+（t-22）+1≤m≤（t3）-1. Let G=（[t]，E） be a leftcompressed 3graph with m edges and [t-1]（3）G. If |EΔE″|≤14， then λ（G）≤λ（C3，m）.

Sun et al. in [7] proved that λ（G）≤λ（C3，m） if |EΔE″|≤8. Later， Sun et al extended the results， which is Theorem 3.

Theorem 4（Peng et al） Let m， i， p and t be positive integers satisfying （t-13）+（t-22）+1≤m≤（t3）-1. Let G=（[t]，E） be a leftcompressed 3graph with m edges and [t-1]（3）G. If the triple with the minimum colex order in Gc is （t-p-i）（t-p）t and t≥（p-1）3（p-2）38（p-1）2-40+2p-1. Then λ（G）≤λ（C3，m）.

2 Proof of Theorem 2

Proof of Theorem 2 Let G be the 3graph satisfying conditions of Theorem 5. If [t-1]（3）G， then by Theorem 4， we have λ（G）≤λ（C3，m）. Otherwise， we will prove the following lemmas which imply Theorem 2.

Lemma 4 Let m， t， s and i be positive integers satisfying m=（t3）-s and s≤t-2. Let G=（[t]，E） be a leftcompressed 3graph with m edges. If the triple with the minimum colex order in Gc， the complement of G， is （t-2-i）（t-2）（t-1） and the triple with the minimum colex order in Ect is （t-2-j）（t-2）， then λ（G）≤（C3，m）.

Lemma 5 Let m， t， s and i be positive integers satisfying m=（t3）-s and s≤t-2. Let G=（[t]，E） be a leftcompressed 3graph with m edges. If the triple with the minimum colex order in Gc is （t-2-i）（t-2）（t-1） and the triple with the minimum colex order in Ect is （t-p-j）（t-p）， where p>2， and t≥（p-1）3（p-2）38（p-1）2-40+2p-1. Then we have λ（G）≤λ（C3，m）.

Lemma 6 Let m， t， s and i be positive integers satisfying m=（t3）-s and s≤t-2. Let G=（[t]，E） be a leftcompressed 3graph with m edges. If the triple with the minimum colex order in Gc is （t-3-i）（t-3）（t-1） and the triple with the minimum colex order in Ect is （t-p-j）（t-p）， where p≥3， then we have λ（G）≤λ（C3，m） if t≥（p-1）3（p-2）38（p-1）2-40+2p-1.

Lemma 7 Let m， t， s and i be positive integers satisfying m=（t3）-s and s≤t-2. Let G=（[t]，E） be a leftcompressed 3graph with m edges. If the triple with the minimum colex order in Gc is （t-p′-i）（t-p′）（t-1） and the triple with the minimum colex order in Ect is （t-p-j）（t-p）， where p≥ p′>3， then we have λ（G）≤λ（C3，m） if t≥（p-1）3（p-2）38（p-1）2-40+2p-1.

Next， we will give the proof of Lemma 47. In fact， the proofs of other three lemmas are similar to the proof of Lemma 4. We omit the details of the proof of other lemmas and will give only an outline of the proofs. In Section 2.1， we give the proof of Lemma 4. In Section 2.22.4， we give the outline of the proof of Lemma 47， respectively.

2.1 Proof of Lemma 4

Let G be a leftcompresseded 3graph with m edges and the triple with minimum colex order in Gc is （t-2-i）（t-2）（t-1）. Let t-2-i-a=min{Ec（t-1）t}， where a≥0， and x=（x1，x2，…， xt） be an optimal weighting for G satisfying x1≥x2≥…≥xt≥0. By Remark 2， we have x1=x2=…=xt-2-i-a-1， and xt-2-i=…=xt-3. We first point out that

λ（E1（t-2-i），x）-λ（E（t-2）t，x）≥（1-x1-xt-2-i）-（1-xt-xt-1-xt-2-…-xt-2-i）=

xt+xt-1+xt-2+…+xt-2-i+1-x1≥0.（4）

To verify （4）， we have

x1=xt-1+λ（E1＼（t-1），x）λ（E1（t-1），x）=xt-1+（xt-2+…+xt-2-i-a）（xt-1+xt）x2+…+xt-2+xt≤2xt-1+xt.（5）

So， （4） is true. This implies that λ（E1（t-2-i），x）≥λ（E（t-2）t，x）.

Let us continue our proof. We divide the proof into two cases： a=0 and a≥1.

Case 1 a=0. In this case， G is a leftcompressed 3graph with m edges and the triple with minimum colex ordering in Gc is （t-2-i）（t-2）（t-1）， where i≥1， and min{Ec（t-1）t}=t-2-i. Let x=（x1，x2，…，xt） be an optimal weighting for G satisfying x1≥x2≥…≥xt≥0. By Remark 2， we have x1=x2=…=xt-2-i-1， xt-2-i=…=xt-3 and xt-2=xt-1=xt. Next we prove λ（G）≤λ（C3，m）. By Theorem 3， |EΔE″|≤8 have been solved， we can assume that i≥2. Let G″=G∪{（t-2-i）（t-2）（t-1），…， （t-3）（t-2）（t-1）}＼{（t-2-i-1）（t-1）t，…，（t-2-2i）（t-1）t}. By Lemma 2， we have λ（C3，m）≥λ（G″）. So we just need to prove λ（G″）≥λ（G）. We make a number of complex proper adjustments to produce a better legal weghting， say z for G″ such that λ（G″，x）≥λ（G，x）=λ（G）. We call this way to change edges and weights for Channel 1.

By Remark 2，

x1-xt-2-i=λ（E1＼（t-2-i），x）λ（E1（t-2-i），x）=xt-1xt+xt-2xt+xt-1xt-2λ（E1（t-2-i），x）=

3x2tλ（E1（t-2-i），x），（6）

So

λ（G′，x）-λ（G，x）=ixt-2-ixt-2xt-1-ix1xt-1xt=-3ix4tλ（E1（t-2-i），x）.（7）

Let 1≤k≤i. Consider a new weighting y（k）=（y（k）1，…，y（k）t）， y（k）j=y（k-1）j， j≠t-2-2i+（k-1）， t-2-i+（k-1）， y（k）t-2-2i+（k-1） =y（k-1）t-2-2i+（k-1）-δk， y（k）t-2-i+（k-1）=y（k-1）t-2-i+（k-1）+δk. And let y（0）=x. Then

λ（G′，y（k））-λ（G′，y（k-1））=δk[λ（E′t-2-i+（k-1），y（k-1））-λ（E′t-2-2i+（k-1），y（k-1））]-

δ2kλ（E′（t-2-2i+（k-1））（t-2-i+（k-1）），y（k-1）=δk（xt-1xt+xt-1xt-2）-δ2kλ（E1（t-2-i），x）.（8）

Let δk=xt-1xt+xt-1xt-22λ（E1（t-2-i），x）≤xt-1=xt， then y（k）∈S. So

λ（G′，y（k））-λ（G′，y（k-1））=（xt-1xt+xt-1xt-2）24λ（E1（t-2-i），x）.（9）

Then

λ（G′，y（k））-λ（G′，y（0））=i（xt-1xt+xt-1xt-2）24λ（E1（t-2-i），x）=ix4tλ（E1（t-2-i），x） .（10）

Consider a new weighting z=（z1，…，zt）， zj=y（i）j， j≠t-2， t，zt-2=y（i）t-2-η， zt=y（i）t+η. Then

λ（G′，z）-λ（G′，y（i））=η[λ（E′t，y（i））-λ（E′t-2，y（i））]-η2λ（E′（t-2）t，y（i））=

-η（xt-2-i-1xt-1+…+xt-2-2ixt-1+xt-3xt-1+…+xt-2-ixt-1）-η2λ（E（t-2）t，x）-iδη=

-η（ix1xt-1+ixt-2-ixt-1）-η2λ（E（t-2）t，x）-iδη.（11）

Let η=-ix1xt-1+ixt-2-ixt-12λ（E（t-2）t，x）. Since t≥3i+2， then we have η≥-xt. So z∈S. And

λ（G′，z）-λ（G，x）=-3ix4tλ（E1（t-2-i），x）+ix4tλ（E1（t-2-i），x）+（ix1xt-1+ixt-2-ixt-1）24λ（E（t-2）t，x），（13）

Since i≥3 and λ（E1（t-2-i），x）≥λ（E（t-2）t，x）， then we have λ（C3，m）≥λ（G′）≥λ（G）.

Case 2 a≥1. We apply induction on the colex order of the triple with the minimum colex order in Gc. The base case is that G satisfies the condition of Theorem 1.4， then we have λ（C3，m）≥λ（G）. Let G′=G∪{（t-2-i）（t-2）（t-1）}＼ {（t-2-i-a-1）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So we just need to prove λ（G′）≥λ（G）. We make a number of complex proper adjustments to produce a better legal weghting， say z for G′ such that λ（G′，z）≥λ（G，x）=λ（G）. We call this way to change edges and weights for Channel 2.

Note that

λ（G′，x）-λ（G，x）=xt-2-ixt-2xt-1-xt-2-i-a-1xt-1xt=

λ（Et-2＼t，x）λ（E（t-2）t，x）xt-2-ixt-1-λ（E1＼t-2-i，x）λ（E1（t-2-i），x）xt-1xt，

（14）

where

λ（Et-2＼t，x）λ（E（t-2）t，x）=xt-2-i-a+…+xt-2-i-1λ（E（t-2）t，x）xt-1，（15）

and

λ（E1＼t-2-i，x）λ（E1（t-2-i），x）=xt-1xt+xt-2xt+xt-1xt-2λ（E1（t-2-i），x）xt-1.（16）

Consider a new weighting y=（y1，…，yt），yj=xj，j≠t-2-i-a-1，t-2-i，yt-2-i-a-1=xt-2-i-a-1-δ，yt-2-i=xt-2-i+δ，

λ（G′，y）-λ（G′，x）=δ[λ（E′t-2-i，x）-λ（E′t-2-i-a-1，x）]-δ2λ（E′（t-2-i-a-1）（t-2-i），x）=

δ（xt-1xt+xt-1xt-2）-δ2λ（E1（t-2-i），x）.（17）

Let δ=xt-1xt+xt-1xt-22λ（E1（t-2-i），x）≤xt-12≤xt. So y∈S. Then

λ（G′，y）-λ（G′，x）=（xt-1xt+xt-1xt-2）24λ（E1（t-2-i），x）.（18）

Consider a new weighting z=（z1，…，zt），zj=yj，j≠t-2，t，zt-2=yt-2-η，zt=yt+η. Then

λ（G′，z）-λ（G′，y）=η[λ（E′t，y）-λ（E′t-2，y）]-η2λ（E′（t-2）t，y）=

η（-xt-2-ixt-1-xt-2-i-a-1xt-1）-η2λ（E（t-2）t，x）-ηδ（xt-2-xt）+δη2.（19）

Let η=-xt-2-ixt-1+xt-2-i-a-1xt-12λ（E（t-2）t，x）， then

λ（G′，z）-λ（G′，y）≥（xt-2-ixt-1+xt-2-i-a-1xt-1）24λ（E（t-2）t，x）.（20）

By （4） （14）， （18） and （20）， we have

λ（G′，z）-λ（G，x）≥λ（Et-2＼t，x）λ（E（t-2）t，x）xt-2-ixt-1-λ（E1＼t-2-i，x）λ（E（1（t-2-i）），x）xt-1xt+

（xt-1xt+xt-1xt-2）24λ（E1（t-2-i），x）+（xt-2-ixt-1+xt-2-i-a-1xt-1）24λ（E（t-2）t，x）≥0.（21）

Therefore， λ（C3，m）≥λ（G′）≥λ（G）.

2.2 Outline of the proof of Lemma 5

Let t-p-j-a=min{Ec（t-1）t} and x=（x1，x2，…，xt） be an optimal weighting for G satisfying x1≥x2≥…≥xt≥0.

We divide the prove into two parts： p=3 and p>3.

Part Ⅰ p=3， then we have j+1≥i. We divide the prove into two cases： j≥2 and j=1.

Case 1 j≥2. We apply induction on the colex order of the triple with minimum colex order in Gc. The base case is that G satisfies the condition of Theorem 4. To continue the proof， we construct an auxiliary graph G′=G∪{（t-2-i）（t-2）（t-1）}＼{（t-3-j-a-1）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So its sufficient to prove that λ（G′）≥λ（G）. To do this， we apply Channel 2 similar to the proof of Case 2 in Lemma 4 and make a number of complex proper adjustments to produce a better legal weighting， say z for G′ such that λ（G′， z）≥λ（G， x）=λ（G）.

Case 2 j=1. Let t-4-a=min{Ec（t-1）t}， where a≥0. When a=0， since G is leftcompressed， then |EΔE″|=10. By Theorem 3， we have λ（C3，m）≥λ（G）. So we can assume that a≥1. Let G′=G∪{（t-4）（t-3）t}＼{（t-4-a-1）（t-1）t}. By Lemma 4， we have λ（C3，m）≥λ（G′）. So its sufficient to prove λ（G′）≥λ（G）. We make a number of complex proper adjustments to produce a better legal weighting， say z for G′ such that λ（G′， z）=（G， x）=λ（G）.

Part Ⅱ p>3. We apply induction on the colex order of the triple with the minimum colex order in Gc. The base case is that G satisfies the condition of Theorem 4. To continue the proof， we construct an auxiliary graph G′=G∪{（t-2-i）（t-2）（t-1）}＼{（t-p-j-a-1）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So we just need to prove λ（G′）≥λ（G）. To do this， we apply Channel 2 and make a number of complex proper adjustments which is similar to the proof of Case 2 in Lemma 4 to produce a better legal weighting， say z for G′ such that λ（G′， z）≥λ（G， x）=λ（G）.

2.3 Outline of the Proof of Lemma 6

Let x=（x1，x2，…，xt） be an optimal weighting for G satisfying x1≥x2≥…≥xt≥0. We divide the prove into three parts： p=3 and p≥4.

Part Ⅰ p=3. We divide this prove into two cases： i=1 and i≥2.

Case 1 i=1. Let min{Ec（t-2）t}=t-3-j-b and min{Ec（t-1）t}=t-3-j-a. If b=0， then |EΔE″|=12. By Theorem 3， we can get λ（C3，m）≥λ（G）. So we can assume that b≥1. Since G is leftcompressed， a≥1. We apply induction on the colex order of the triple with the minimum colex order in Gc. The base case is that G satisfies the condition of Theorem 4. To continue our proof， we construct an auxiliary graph G′=G∪{（t-4）（t-3）（t-1）}＼{（t-3-j-a）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So its sufficient to prove λ（G′）≥λ（G）. To do this， we apply Channel 2 and make a number of complex proper adjustments to produce a better legal weighting， say z for G′ such that λ（G′， z）≥λ（G， x）=λ（G）.

Case 2 i≥2. Obviously， j≥2. Let min{Ec（t-2）t}=t-3-j-b and min{Ec（t-1）t}=t-3-j-a. We divide the prove into next two subcases： a=0 and a≥1.

Subcase 1 a=0. We apply induction on the colex order of the triple with the minimum colex order in Gc. The base case is that G satisfies the condition of Theorem 4， then λ（C3，m）≥λ（G）. To continue our proof， we construct an auxiliary graph G′=G∪{（t-3-i）（t-3）（t-1），…， （t-4）（t-3）（t-1）}＼{（t-3-j-1）（t-1）t，…，（t-3-j-i）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So we just need to prove λ（G′）≥λ（G）. To do this， we apply Channel 1 and make a number of complex proper adjustments to produce a better legal weighting， say z for G′ such that λ（G′， z） ≥λ（G， x）=λ（G）.

Subcase 2 a≥1. Let min{Ec（t-2）t}=t-3-j-b and min{Ec（t-1）t}=t-3-j-a. Again， we apply induction on the colex order of the triple with the minimum colex order in Gc. The base case is that G satisfies the condition of Theorem 4， then λ（C3，m）≥λ（G）. To continue the proof， we construct an auxiliary graph G′=G∪{（t-3-i）（t-3）（t-1）}＼{（t-3-j-a-1）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So we just need to prove λ（G′）≥λ（G）. To do this， we apply Channel 2 and make a number of complex proper adjustments to produce a better legal weighting， say z for G′ such that λ（G′， z）≥λ（G， x）=λ（G）.

Part Ⅱ p≥4. We divide our proof into two cases： p=4， a=0 and p≥5 or a≥1.

Case 1 p=4， a=0. If j=1， then we have i=1 or i=2. We divide this prove into three subcases： j≥2； j=1， i=1； j=1， i=2.

Subcase 1 and subcase 2 j≥2 or j=1， i=1. Again， we apply induction on the colex order of the triple with the minimum colex order in Gc. The base case is that G satisfies the condition of Theorem 4， then λ（C3，m）≥λ（G）. To continue our proof， we construct an auxiliary graph G′=G∪{（t-3-i）（t-3）（t-1）}＼{（t-4-j-1）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So we just need to prove λ（G′）≥λ（G）. To do this， we apply Channel 2 and make a number of complex proper adjustments to produce a better legal weighting， say z for G′ such that λ（G′， z）≥λ（G， x）=λ（G）.

Subcases 3 j=1， i=2. Again， we apply induction on the colex order of the triple with the minimum colex order in Gc. The base case is that G satisfies the condition of Theorem 4， then λ（C3，m）≥λ（G）. To continue our proof， we construct an auxiliary graph G′=G∪{（t-4）（t-3）（t-1）， （t-5）（t-3）（t-1）}＼{（t-6）（t-1）t， （t-7）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So we just need to prove λ（G′）≥λ（G）. To do this， we apply Channel 1 and make a number of complex proper adjustments to produce a better legal weighting， say z for G′ such that λ（G′， z）≥λ（G， x）=λ（G）.

Case 2 p≥5 or a≥1. We apply induction on the minimum colexing ordering in Gc. The base case is that G satisfies the condition of Theorem 4， then λ（C3，m）≥λ（G）. To continue our proof， we construct an auxiliary graph G′=G∪{（t-3-i）（t-3）（t-1）}＼{（t-p-j-a-1）（t-1）t}. By the induction hypothesis， λ（C3，m）≥λ（G′）. So we just need to prove λ（G′）≥λ（G）. To do this， we apply Channel 2 and make a number of complex proper adjustments to produce a better legal weighting， say z for G′ such that λ（G′， z）≥λ（G， x）=λ（G）.

2.4 Outline of proof Lemma 7

Let t-p-j-a=min{Ec（t-1）t} and x=（x1， x2， …， xt） be an optimal weighting for G satisfying x1≥x2≥…≥xt≥0. We divide the proof into two cases： j=1， p′≤p≤4 and t-p-j-a=t-p′-i； j≥2， p≥5 or t-p-j-a>t-p′-i.

Case 1 j=1， p′=p=4 and t-p-j-a=t-p′-i. By Remark 2（b）， we have x1=x2=…=xt-6， xt-5=…=xt-2， and xt-1=xt. We compare the Lagrangian of C3，m and G directly. To do this， we apply Channel 1 and make a number of complex proper adjustments which is similar to the proof of Case 1 in Lemma 4 to produce a better legal weighting， say z for C3，m such that λ（G′， z）≥λ（G， x）=λ（G）.

Case 2 j≥2， p≥5 or t-p-j-a

References：

[1] MOTZKIN T S， STRAUS E G. Maxima for graphs and a new proof of a theorem of Turán[J]. Canad J Math， 1965，17（1）：533540.

[2] FRANKL P， FREDI Z. Extremal problems whose solutions are the blowups of the small Wittdesigns [J]. J Combin Theor Ser A， 1989，52（5）：129147.

[3] TALBOT J. Lagrangians of hypergraphs [J]. Combin Probab Comput， 2002，11（2）：199216.

[4] PENG Y， ZHAO C. A MotzkinStraus type result for 3uniform hypergraphs [J]. J Graphs Comb， 2013，29（3）：681694.

[5] FRANKL P， RDL V. Hypergraphs do not jump [J]. Combinatory， 1989，4（23）：149159.

[6] TANG Q S， PENG Y， ZHANG X D， et al. Some results on lagrangians of hypergraphs[J]. Disc App Math， 2013，166（3）：222238.

[7] SUN Y P， TANG Q S， ZHAO C， et al. On the largest graphlagrangian of 3graphs with fixed number of edges [J]. J Optimiz Theor Appl， 2013，163（1）：5779.

（編輯 HWJ）