Back to Search
Start Over
Lagrangian densities of short 3-uniform linear paths and Turán numbers of their extensions
- 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.
- Subjects :
- Path (topology)
Hypergraph
Mathematics::Combinatorics
Conjecture
0211 other engineering and technologies
021107 urban & regional planning
0102 computer and information sciences
02 engineering and technology
Lambda
01 natural sciences
Theoretical Computer Science
Turán number
Combinatorics
symbols.namesake
Integer
010201 computation theory & mathematics
symbols
Discrete Mathematics and Combinatorics
Lagrangian
Mathematics
Subjects
Details
- ISSN :
- 14355914 and 09110119
- Volume :
- 37
- Database :
- OpenAIRE
- Journal :
- Graphs and Combinatorics
- Accession number :
- edsair.doi...........6c75c35104a875aa32d5a0064ef9f4cc