lambda-perfect hypergraphs and Lagrangian densities of hypergraph cycles
lambda-perfect hypergraphs and Lagrangian densities of hypergraph cycles
复制标题
lambda 完美超图和超图循环的拉格朗日密度
DOI：
10.1016/j.disc.2019.03.024
复制
发表时间：
2019
影响因子：
0.8
通讯作者：
Peng Yuejian
中科院分区：
文献类型：
--
作者：
Yan Zilong;Peng Yuejian
r-一致超图F的拉格朗日密度是r！乘以所有F-自由r-一致超图的拉格朗日量的上确界。对于一个有t个顶点的r-图H，π λ（H）≥ r！λ（K t− 1 r）.我们说一个有t个顶点的r-一致超图H是λ-完美的，如果π λ（H）= r！λ（K t-1 r）。Motzkin-Straus的一个定理表明所有2-一致图都是λ-完美图。探索什么样的超图是λ-完美的是一个有趣的问题。一个超图是线性的，如果任意两条边至多有一个公共顶点。我们提出了如下猜想：（1）对于r≥ 3，存在n使得至少有n个顶点的线性r-一致超图是λ-完美的. (2)对于r≥ 3，存在n使得如果G，H是至少有n个顶点的λ-完美r-图，则G <$H是λ-完美的.关于这个猜想，我们得到了一个部分结果：设S2，t={123，124，125，126，..，12（t+ 2）}. (An Sidorenko的早期结果指出S2，t是λ-完美的（Sidorenko，1989）。设H是s个顶点的λ-完美3-图。则F= S2，t <$H是λ-完美的，如果s≥ 3且t≥ 3.关于超图圈的拉格朗日密度，目前还没有已知的结果，对于3-一致图，有3种未解决的情况：长度为3的线性圈：C33 ={123，345，561}，广义三角形：F5 ={123，124，345}和K43 −={123，124，134}。本文给出了一类非λ-完美3-一致图F5的拉格朗日密度.我们证明了C33是λ-完美的，并且在所有的C33-free 3-图G中，只有那些包含K53的超图才能达到Lagrangian λ（K53）.利用Pikhurko的转移技巧，可以得到上述超图扩张的Turán密度.
The Lagrangian density of an r-uniform hypergraph F is r! multiplying the supremum of the Lagrangians of all F-free r-uniform hypergraphs. For an r-graph H with t vertices, it is clear that π λ (H)≥ r! λ (K t− 1 r). We say that an r-uniform hypergraph H with t vertices is λ-perfect if π λ (H)= r! λ (K t− 1 r). A theorem of Motzkin–Straus implies that all 2-uniform graphs are λ-perfect. It is interesting to explore what kind of hypergraphs are λ-perfect. A hypergraph is linear if any 2 edges have at most 1 vertex in common. We propose the following conjecture:(1) For r≥ 3, there exists n such that a linear r-uniform hypergraph with at least n vertices is λ-perfect.(2) For r≥ 3, there exists n such that if G, H are λ-perfect r-graphs with at least n vertices, then G⨆ H is λ-perfect. Regarding this conjecture, we obtain a partial result: Let S 2, t={123, 124, 125, 126,…, 12 (t+ 2)}.(An earlier result of Sidorenko states that S 2, t is λ-perfect (Sidorenko, 1989).) Let H be a λ-perfect 3-graph with s vertices. Then F= S 2, t⨆ H is λ-perfect if s≥ 3 and t≥ 3. There was no known result on Lagrangian densities of hypergraph cycles and there were 3 unsolved cases for 3-uniform graphs spanned by 3 edges: a linear cycle of length 3: C 3 3={123, 345, 561}, the generalized triangle: F 5={123, 124, 345} and K 4 3−={123, 124, 134}. In this paper, we obtain the Lagrangian density of F 5 which is an example of non-λ-perfect 3-uniform graph. We show that C 3 3 is λ-perfect, and among all C 3 3-free 3-graphs G, only those hypergraphs containing K 5 3 achieve the Lagrangian λ (K 5 3). The Turán densities of extensions of the above hypergraphs can be obtained by applying a transference technique of Pikhurko.