Back to Search
Start Over
[formula omitted]-perfect hypergraphs and Lagrangian densities of hypergraph cycles.
- Source :
-
Discrete Mathematics . Jul2019, Vol. 342 Issue 7, p2048-2059. 12p. - Publication Year :
- 2019
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *HYPERGRAPHS
*DENSITY
*CYCLES
*TRIANGLES
*LOGICAL prediction
*GEOMETRIC vertices
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 342
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 136462638
- Full Text :
- https://doi.org/10.1016/j.disc.2019.03.024