The Connection Between The Graph-Lagrangian And Maximum Cliques Of A 3-uniform Hypergraph

In combinatorics, there is a rich history of studying Graph-Lagrangian of hypergraph and its applications. In 1941, Turan answered the following question: What is the maximum number of edges in a graph on n vertices without containing a complete subgraph of order t, for a given t? This is the famous Turan theorem. In 1965, Motzkin and Straus established a remarkable connection between the Graph-Lagrangian of a graph and the order of its maximum cliques. It also provided a new proof of Turan’s theorem. This new proof aroused interests in the study of Graph-Lagrangians of r-uniform hypergraphs.In most applications, we need an upper bound for the Graph-Lagrangian of a hypergraph. In the process of estimating Turan densities of some hypergraphs, Frankl and Furedi asked the following question:Given r≥ 3 and m E N, how large can the Graph-Lagrangian of an r-graph with m edges be? They conjectured that Cr,m (the r-graph with m edges formed by taking the first m sets in the colex ordering of the collection of all subsets of N of size r) has the largest Graph-Lagrangian of all r-graphs with m edges, that is, the Graph-Lagrangian of a r-uniform hypergraph G is less than or equal to the Graph-Lagrangian of the Cr,m. This dissertation proves that Frankl and Fiiredi’s conjecture holds under some conditions.The Moztkin-Straus result implies that this conjecture is true for r= 2. For r≥3, this conjecture is very challenging. Talbot first confirmed this conjecture for some cases. Later Peng, Zhao, Tang etc. confirmed this conjecture for some more cases.Since the obvious generalization of Motzkin and Straus’ result to r-uniform hypergraphs is false, Peng and Zhao attempted to explore the relationship be-tween the Graph-Lagrangian of a hypergraph and the size of maximum cliques of hypergraphs when the number of edges is in certain range. They proposed a pair of conjectures. This pair of conjectures refined Frankl and Fiiredi’s conjec-ture for this range of edges numbers. They also confirmed one of the conjectures for 3-uniform hypergraph, that is, the Graph-Lagrangian of a 3-uniform hyper-graph is the Graph-Lagrangian of its maximum cliques when the number of edges is in certain range. This dissertation shows that for that range of the number of edges, if a 3-uniform hypergraph does not contain a clique of such a size, then the Graph-Lagrangian of such a 3-uniform hypergraph is strictly less than the Graph-Lagrangian of a complete 3-uniform hypergraph of such a size under some conditions. It also provides some evidence for the above speculation.Based on the known results, this dissertation continues to study the rela-tionship between the Graph-Lagrangian of a 3-uniform hypergraph G and the Graph-Lagrangian of the C3,m.Since it is very difficult to obtain their relationship directly, some conditions are added to explore their relationship, for example, the number of the symmetric difference between the edge of G and the edge of C3,m is less than or equal to a specific value, or the number of edges is a function of t. Under the premise of satisfying left-compressed, through flexible substitution, this dissertation proves that the Graph-Lagrangian of a 3-uniform hypergraph is less than or equal to the Graph-Lagrangian of C3,m, and improves the previous results.This dissertation also studies the relationship between the Graph-Lagrangian and maximum cliques of a 3-graph with the conditions that m is in a certain range, G does not contain a clique of order t - 1, and the number of edges containing vertices t - 1 and t is not greater than a specific value. By using the iterative method and substitution method, we conclude that the Graph-Lagrangian of G is strictly smaller than the Graph-Lagrangian of a complete 3-graph of order t - 1.This dissertation continues to explore the relationship between the Graph-Lagrangian and maximum cliques of a 3-graph. Some conditions are added in the process of the research, such as removing a specified p edges from the clique of t - 1, and t is not less than a polynomial of p, then the Graph-Lagrangian of G is strictly less than the Graph-Lagrangian of a complete 3-graph of order t - 1. Due to the generality of p, so the conclusion has relatively good generality, and wide coverage.Based on the known research results, as long as the conclusion holds for left-compressed 3-uniform hypergraphs, then it holds for 3-uniform hypergraphs. This greatly reduces the computational complexity. Based on this, let G be a left-compressed 3-graph on the vertex set [t] with m edges, if p edges are removed from the clique of order t - 1, and t is greater than or equal to a polynomial of p, then the Graph-Lagrangian of G is strictly less than the Graph-Lagrangian of a complete 3-graph of order t - 1. This improves the previous research in the aspect of computational complexity and the generality, and partially verifies the conjecture of Peng-Zhao proposed.In conclusion, through the research of the specific situation, the original pur-pose is to prove the Frankl-Furedi conjecture. But there are some limitation by the current method. Since there are many cases and each case has different substitu-tion method, it is relatively difficult to sum them up. However, if some difficulties can be overcomed, then the method of this dissertation might be generalized and a proof of Frankl-Furedi conjecture might be obtained. This dissertation provides more evidence for the Frankl-Furedi conjecture.