Lagrangian densities of short 3-uniform linear paths and Turán numbers of their extensions
| Autor: | Biao Wu, Yuejian Peng |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
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 |
| Zdroj: | Graphs and Combinatorics. 37:711-729 |
| ISSN: | 1435-5914 0911-0119 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|