Paper Info
Title
Lagrangian Densities Of Short 3-Uniform Linear Paths And Turan Numbers Of Their Extensions
Abstract
For a fixed positive integer n and an r-uniform hypergraph H, the Turan number ex(n, H) is the maximum number of edges in an H-free r-uniform hypergraph on n vertices, and the Lagrangian density of H is defined as pi(lambda)(H) = sup{r!lambda(G) : G is an H-free r-uniform hypergraphg, where lambda(G) = max{Sigma(e is an element of G) Pi(i is an element of e) x(i) : x(i) >= 0 and Sigma(i is an element of V(G)) x(i) = 1} is the Lagrangian of G. For an runiform hypergraph H on t vertices, it is clear that pi(lambda)(H) >= r!lambda((r)(Kt-1)). Let us say that an r-uniform hypergraph H on t vertices is lambda-perfect if pi(lambda)(H) = r!lambda(K-t-1(r)). A result of Motzkin and Straus implies that all graphs are lambda-perfect. It is interesting to explore what kind of hypergraphs are lambda-perfect. A conjecture in [22] proposes that every sufficiently large r-uniform linear hypergraph is lambda-perfect. In this paper, we investigate whether the conjecture holds for linear 3-uniform paths. Let P-t = {e(1), e(2), ..., e(t)} be the linear 3-uniform path of length t, that is, |e(i)| = 3, |e(i) boolean AND e(i+1)| = 1 and e(i) boolean AND e(j) = empty set if |i - j| >= 2. We show that P-3 and P-4 are lambda-perfect. Applying the results on Lagrangian densities, we determine the Tura ' n numbers of their extensions.
Year
DOI
Venue
2021
10.1007/s00373-020-02270-w
GRAPHS AND COMBINATORICS
Keywords
DocType
Volume
Lagrangian of hypegraphs, Turan number
Journal
37
Issue
ISSN
Citations 
3
0911-0119
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Biao Wu100.34
Yuejian Peng223.46