A Note on Generalized Lagrangians of Non-uniform Hypergraphs
A Note on Generalized Lagrangians of Non-uniform Hypergraphs
复制标题
DOI：
10.1007/s11083-016-9385-0
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
Yuejian Peng;Biao Wu;Yuping Yao
中科院分区：
文献类型：
--
作者：
Yuejian Peng;Biao Wu;Yuping Yao
在1980年的S中，∈和Füredi猜想，在所有具有边序的一致图中，具有由第一集组成的第一集的一致图具有最大的拉格朗日。Motzkin和Straus的一个结果表明，对于r=2，这个猜想是正确的。即使对于r=3，这个猜想似乎也是有挑战性的。对于超图H=(V，E)，集合(H)={|e|：E∈E}称为边型H。本文研究了非一致超图，定义了非一致超图的广义拉格朗日量L(H)，其中不同类型的边具有不同的权重。我们研究了以下两个问题：1.设T是一个边型为T的边图。设Cm，T表示在联序中取第一个基数集形成的边型为T的超图。L(H)≤L(厘米，T)坚持住吗？如果t={r}，那么这个问题就是Frankl和Füredi提出的问题。2.给定一个超图H，求出一个最小子超图GofHf，使得L(G)=L(H)。Motzkin和Straus的一个结果给出了这两个问题的完整答案，如果他是图的话。在这篇文章中，我们对{1，2}-超图的这两个问题给出了完整的回答。对于第一个问题，我们给出了{1，r1，r2，…，rl}-超图。关于第二个问题，我们还证明了{1，r1，r2，⋯，rl}-超图的广义拉格朗日与{r1，R2，⋯，rl}-超图之间的联系。
Setis less thanin thecolex orderingifmax(A△B)∈B. In 1980’s, Frankl and Füredi conjectured that ther-uniform graph withmedges consisting of the firstmsets ofin the colex ordering has the largest Lagrangian among allr-uniform graphs withmedges. A result of Motzkin and Straus implies that this conjecture is true forr=2. This conjecture seems to be challenging even forr=3. For a hypergraphH=(V,E), the setT(H)={|e|:e∈E} is called theedge typeofH. In this paper, we study non-uniform hypergraphs and defineL(H) a generalized Lagrangian of a non-uniform hypergraphHin which edges of different types have different weights. We study the following two questions: 1. LetHbe a hypergraph withmedges and edge typeT. LetCm,Tdenote the hypergraph with edge typeTandmedges formed by taking the firstmsets with cardinality inTin the colex ordering. DoesL(H)≤L(Cm,T) hold? IfT={r}, then this question is the question by Frankl and Füredi. 2. Given a hypergraphH, find a minimum subhypergraphGofHsuch thatL(G) =L(H). A result of Motzkin and Straus gave a complete answer to both questions ifHis a graph. In this paper, we give a complete answer to both questions for {1,2}-hypergraphs. Regarding the first question, we give a result for {1,r1,r2,…,rl}-hypergraph. We also show the connection between the generalized Lagrangian of {1,r1,r2,⋯ ,rl}-hypergraphs and {r1,r2,⋯ ,rl}-hypergraphs concerning the second question.