Back to Search Start Over

Lagrangian densities of short 3-uniform linear paths and Turán numbers of their extensions

Authors :
Biao Wu
Yuejian Peng
Source :
Graphs and Combinatorics. 37:711-729
Publication Year :
2021
Publisher :
Springer Science and Business Media LLC, 2021.

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 \;\text {is an}\; H\text {-free} \;r\text {-uniform hypergraph}\}$$ , where $$\lambda (G)=\max \{\sum _{e \in G}\prod \limits _{i\in e}x_{i}: x_i\ge 0 \;\text {and}\; \sum _{i\in V(G)} x_i=1\}$$ is the Lagrangian of G. For an r-uniform hypergraph H on t vertices, it is clear that $$\pi _{\lambda }(H)\ge r!\lambda {(K_{t-1}^r)}$$ . 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, \dots , e_t\}$$ be the linear 3-uniform path of length t, that is, $$|e_i|=3$$ , $$|e_i \cap e_{i+1}|=1$$ and $$e_i \cap e_j=\emptyset $$ if $$|i-j|\ge 2$$ . We show that $$P_3$$ and $$P_4$$ are $$\lambda $$ -perfect. Applying the results on Lagrangian densities, we determine the Turan numbers of their extensions.

Details

ISSN :
14355914 and 09110119
Volume :
37
Database :
OpenAIRE
Journal :
Graphs and Combinatorics
Accession number :
edsair.doi...........6c75c35104a875aa32d5a0064ef9f4cc