3一致超图的拉格朗日和最大团之间的关系的研究

发布时间：2018-05-12 13:29

本文选题：图拉格朗日 + 左压缩　；参考：《湖南大学》2016年博士论文

【摘要】：在组合数学史上,有一段丰富的研究历史是关于超图的图拉格朗日及其应用的。1941年,Turan回答了下面的问题：一个有n个顶点的图,它不包含阶为t(t给定)的完全子图的最大边数是多少?这就是著名的Turan定理。1965年,Motzkin和Straus在一个图的图拉格朗日和其最大团的阶之间建立了一个显著的联系。它也提供了一个新的证明Turan定理的方法。这个新的证明方法激起了对r一致超图的图拉格朗日的研究兴趣。在很多应用中,需要用到超图的图拉格朗日的一个上限。在估计一些超图的Turan密度的过程中,Frankl和Furedi提出了下面的问题：给定r≥3,m∈N,一个有m条边的r图的图拉格朗日最大能有多大?他们猜想在所有的有m条边的r图中,Gr,m(由N的r子集的集合的colex序中的前m个集合所形成的m条边的r图)有最大的图拉格朗日,也就是说,r一致超图G的图拉格朗日小于等于Gr,m的图拉格朗日。本文证明了Frankl和Furedi的猜想在某些条件下成立。Moztkin和Straus的结果暗含着以上猜想对于r=2是对的。对于r≥3,这个猜想非常具有挑战性。Talbot首先在某些情况下证实了这个猜想。随后,Peng, Zhao, Tang等在更多的情况下证实了这个猜想。Motzkin和Straus的结果不能直接推广到r一致超图,所以Peng和Zhao试图探索当边数在一定范围内,一个超图的图拉格朗日和超图的最大团数之间的关系,并提出了与之相关的两个猜想。这两个猜想细化了当边数在这个范围内的Frankl-Fiiredi猜想。他们还证明了猜想中的一个关于3一致超图的,即当边数在某个范围内时,3一致超图的图拉格朗日是它的最大团的图拉格朗日。本文证明了当边数在那个范围内时,如果一个3一致超图不包含这样的阶的一个团,那么在某些条件下,这个3一致超图的图拉格朗日严格地小于这样的阶的一个完全3一致超图的图拉格朗日。这也为以上猜测提供了一些依据。基于已有的结果,本文继续对3一致超图G的图拉格朗日与G3,m的图拉格朗日之间的关系进行研究。由于直接得出它们之间的联系比较困难,所以附加了一些条件,如在满足G的边与G3,m的边的对称差的个数小于等于某个具体数值的情况下,或者在满足边数等于某个与t有关的式子的情况下,来探讨它们之间的联系。在满足左压缩的前提下,灵活替换,证明出了3一致超图的图拉格朗日小于等于G3,m的图拉格朗日,改进了研究结果。接着研究了在一些条件下,3一致超图的图拉格朗日和最大团之间的关系。本文是在m在某个范围内,G不包含t-1阶团,且同时包含顶点t-1和t的边数不大于某个具体数值的情况下研究的。通过运用迭代法和替换法,得出了G的图拉格朗日严格地小于t-1阶的完全3图的图拉格朗日。本文继续探索了3一致超图的图拉格朗日和最大团之间的关系。在研究的过程中加入了一些条件,如从t-1阶的团中移去了指定的p条边,t大于等于一p的多项式,获得了G的图拉格朗日严格地小于t-1阶的完全3图的图拉格朗日。这里由于p的任意性,所以结论有较好的一般性,以及较广的覆盖面。基于已有的研究成果,只要证明了左压缩3一致超图,也就证明了3一致超图。这大大降低了计算复杂度。在此基础上,令G是在顶点集[t]上有m条边的一个左压缩3图,如果从t-1阶的团中移去p条边,t大于等于p的一个一次多项式,那么G的图拉格朗日严格地小于t-1阶的完全3图的图拉格朗日。这在计算复杂度和一般性上改进了以往的研究结果,并且部分地验证了Peng-Zhao提出的猜想。总之,通过对具体情况的研究,起初的目的是证明Frankl-Furedi猜想。但是目前的方法有一定的局限性。由于有很多种情况,每种情况的替换方法又不一样,所以总结出来比较困难。然而,如果可以克服一些困难,那么本文的方法可能得到推广,Frankl-Furedi猜想也许能够得到证明。本文为Frankl-Furedi猜想提供了更多的依据。
[Abstract]:In the history of combinatorial mathematics, there is a rich history of research history on Hypergraph Lagrange and its application.1941 years. Turan answered the following question: a graph with n vertices, which does not contain the maximum number of complete subgraphs of the order t (t given)? This is the famous Turan theorem.1965, Motzkin and Straus in one Graph Lagrange has a significant relationship with the order of its largest group. It also provides a new method to prove the Turan theorem. This new proof method arouses the interest in the study of graph Lagrange of the uniform hypergraph of R. In many applications, we need to use a upper limit of graph Lagrange of hypergraph. In the process of Turan density of some hypergraphs, Frankl and Furedi put forward the following questions: how big is the maximum of a graph of a R diagram with a given r equal to 3, m N, a r graph with a m edge? They conjecture that in all r diagrams with m edges, Gr, M. Figure Lagrange, that is to say, R unanimous hypergraph G's graph Lagrange is less than equal to Gr, M's graph Lagrange. This paper proves that the conjecture that Frankl and Furedi conjectures of.Moztkin and Straus under certain conditions implies that the above conjecture is right for r=2. For R > 3, this guess is very challenging first in some cases. Then, this conjecture is confirmed. Then, Peng, Zhao, Tang and so on in more cases confirm that the conjecture that the results of.Motzkin and Straus can not be extended directly to the R uniform hypergraph, so Peng and Zhao try to explore the relationship between the graph Lagrange and the maximum number of hypergraphs of a hypergraph in a certain range. The two conjectures. The two conjectures refine the Frankl-Fiiredi conjecture that the number of sides are in this range. They also prove that one of the conjectures on the 3 uniform hypergraph, that is, when the number of sides is in a certain range, the graph Lagrange of the 3 unanimous hypergraph is its largest group of Tulag Lang days. This paper proves that the number of sides is in that range. If a 3 uniform hypergraph does not contain a regiment of such a order, in some conditions, the graph Lagrange of the 3 uniform hypergraph is strictly less than a graph Lagrange of a fully 3 uniform hypergraph of the order of this order. This provides some basis for the above guess. Based on the existing results, this article continues to the 3 uniform hypergraph G. The relationship between graph Lagrange and G3, M's graph Lagrange is studied. As it is difficult to get a direct connection between them, some conditions are added, such as if the number of symmetric differences between the edges of G and G3, M is less than a specific value, or the number of sides equal to a t related formula. The relationship between them is discussed. Under the premise of satisfying the left compression, a flexible replacement is given to prove that the graph Lagrange of 3 uniform hypergraph is less than G3 or equal to that of M, and the results of the study are improved. Then, the relationship between the graph Lagrangian day and the maximum group of 3 uniform hypergraphs is studied under some conditions. This article is in a certain M In a range, G does not contain T-1 orders, and the number of vertices T-1 and t is not more than a certain number. By using the iterative method and replacement method, the graph Lagrange of G is strictly less than the complete 3 graph of the T-1 order. This paper continues to explore the 3 consistent hypergraph of graph Lagrange and the largest group. The relationship between them. In the course of the study, some conditions are added, such as removing the specified P edge from the T-1 order group, t greater than the polynomial of a P, and obtaining graph Lagrange of G's graph Lagrange strictly less than the complete 3 graph of the T-1 order. Here, the conclusion has better generality and wider coverage because of the arbitrariness of P. Surface. Based on the existing research results, as long as the left compression 3 uniform hypergraph is proved, the 3 uniform hypergraph is proved. This greatly reduces the computational complexity. On this basis, G is a left compression 3 graph with m edges on the vertex set [t]. If the P edge is removed from the T-1 order group, t is greater than a single polynomial of P, then the graph of G Lagrange is strictly less than the graph Lagrange of the complete 3 graph of the T-1 order. This improves the previous research results in computational complexity and generality, and partly verifies the conjecture proposed by Peng-Zhao. In a word, the original purpose is to prove the Frankl-Furedi conjecture through the study of the specific circumstances. But the present method has a certain situation. Limited. Because there are many cases, the substitution method of each case is different, so it is difficult to sum up. However, if some difficulties can be overcome, the method of this paper may be popularized, and the Frankl-Furedi conjecture may be proved. This article provides more basis for the Frankl-Furedi conjecture.

【学位授予单位】：湖南大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】