Search

Hypergraph Lagrangian function has been a helpful tool in several celebrated results in extremal combinatorics. Let G be an r-uniform graph on [n] and let x = (x 1 , ... , x n) ∈ [ 0 , ∞) n. The graph Lagrangian function is defined to be λ (G , x) = ∑ e ∈ E (G) ∏ i ∈ e x i. The graph Lagrangian is defined as λ (G) = max { λ (G , x) : x ∈ Δ } , where Δ = { x = (x 1 , x 2 , ... , x n) ∈ [ 0 , 1 ] n : x 1 + x 2 + ⋯ + x n = 1 }. The Lagrangian density π λ (F) of an r-graph F is defined to be π λ (F) = sup { r ! λ (G) : G does not contain F }. Sidorenko (Combinatorica 9:207–215, 1989) showed that the Lagrangian density of an r-uniform hypergraph F is the same as the Turán density of the extension of F. Therefore, determining the Lagrangian density of a hypergraph will add a result to the very few known results on Turán densities of hypergraphs. For an r-uniform graph H with t vertices, π λ (H) ≥ r ! λ (K t - 1 r) since K t - 1 r (the complete r-uniform graph with t - 1 vertices) does not contain a copy of H. We say that an r-uniform hypergraph H with t vertices is λ -perfect if the equality π λ (H) = r ! λ (K t - 1 r) holds. A fundamental theorem of Motzkin and Straus implies that all 2-uniform graphs are λ -perfect. It is interesting to understand the λ -perfect property for r ≥ 3. Our first result is to show that the disjoint union of a λ -perfect 3-graph and S 2 , t = { 123 , 124 , 125 , 126 , ... , 12 (t + 2) } is λ -perfect, this result implies several previous results: Taking H to be the 3-graph spanned by one edge and t = 1 , we obtain the result by Hefetz and Keevash (J Comb Theory Ser A 120:2020–2038, 2013) that a 3-uniform matching of size 2 is λ -perfect. Doing it repeatedly, we obtain the result in Jiang et al. (Eur J Comb 73:20–36, 2018) that any 3-uniform matching is λ -perfect. Taking H to be the 3-uniform linear path of length 2 or 3 and t = 1 repeatedly, we obtain the results in Hu et al. (J Comb Des 28:207–223, 2020). Earlier results indicate that K 4 3 - = { 123 , 124 , 134 } and F 5 = { 123 , 124 , 345 } are not λ -perfect, we show that the disjoint union of K 4 3 - (or F 5 ) and S 2 , t are λ -perfect. Furthermore, we show the disjoint union of a 3-uniform hypergraph H and S 2 , t is λ -perfect if t is large. We also give an irrational Lagrangian density of a family of four 3-uniform hypergraphs. [ABSTRACT FROM AUTHOR]

A number $${\alpha\in [0, 1)}$$ is a jump for an integer r ≥ 2 if there exists a constant c > 0 such that for any family $${{\mathcal F}}$$ of r-uniform graphs, if the Turán density of $${{\mathcal F}}$$ is greater than α, then the Turán density of $${{\mathcal F}}$$ is at least α + c. A fundamental result in extremal graph theory due to Erdős and Stone implies that every number in [0, 1) is a jump for r = 2. Erdős also showed that every number in [0, r!/ r r) is a jump for r ≥ 3. However, not every number in [0, 1) is a jump for r ≥ 3. In fact, Frankl and Rödl showed the existence of non-jumps for r ≥ 3. By a similar approach, more non-jumps were found for some r ≥ 3 recently. But there are still a lot of unknowns regarding jumps for hypergraphs. In this note, we show that if $${c\cdot{\frac{r!}{r^r}}}$$ is a non-jump for r ≥ 3, then for every p ≥ r, $${c\cdot{\frac{p!}{p^p}}}$$ is a non-jump for p. [ABSTRACT FROM AUTHOR]

Abstract: Let be an integer. The real number is a jump for r if there exists such that for every positive ϵ and every integer , every r-uniform graph with vertices and at least edges contains a subgraph with m vertices and at least edges. A result of Erdős, Stone and Simonovits implies that every is a jump for . For , Erdős asked whether the same is true and showed that every is a jump. Frankl and Rödl gave a negative answer by showing that is not a jump for r if and . Another well-known question of Erdős is whether is a jump for and what is the smallest non-jumping number. In this paper we prove that is not a jump for . We also describe an infinite sequence of non-jumping numbers for . [Copyright &y& Elsevier]

Determining the Turán density of a hypergraph is a central and challenging question in extremal combinatorics. We know very few about the Turán densities of hypergraphs. Even the conjecture given by Turán on the Turán density of K 4 3 , the smallest complete hypergraph remains open. It turns out that the hypergraph Lagrangian method, a continuous optimization method has been helpful in hypergraph extremal problems. In this paper, we intend to explore this method further, and try to understand the Turán densities of hypergraphs via Lagrangian densities. Given an integer n and an r -uniform graph H , the Turán number of H , denoted by ex (n, H), is the maximum number of edges in an n -vertex r -uniform graph without containing a copy of H. The Turán density of H , denoted by π (H), is the limit of the function e x (n , H) (n r) as n → ∞. The Lagrangian density of H is π λ (H) = sup { r ! λ (F) : H i s n o t c o n t a i n e d i n F } , where λ (F) is the Lagrangian of F. For any r -uniform graph H , Sidorenko showed that π λ (H) equals the Turán density of the extension of H. So researching on Lagrangian densities of hypergraphs is helpful to better understand the behavior of the Turán densities of hypergraphs. For a t -vertex r -uniform graph H , π λ (H) ≥ r ! λ (K t − 1 r) since K t − 1 r doesn't contain H , where K t − 1 r is the (t − 1) -vertex complete r -uniform graph. We say that H is λ -perfect if the equality holds, i.e., π λ (H) = r ! λ (K t − 1 r). A result given by Motzkin and Straus shows that every graph is λ -perfect. It is natural and fundamental to explore which hypergraphs are λ -perfect. Sidorenko (1989) showed that the (r − 2) -fold enlargement of a tree satisfying the Erdős-Sós conjecture with order at least A r is λ -perfect, where A r is the last maximum of the function g r (x) = (r + x − 3) − r ∏ i = 1 r − 1 (i + x − 2) as x ≥ 2. By using the so-called generalised Lagrangian of hypergraphs, Jenssen (2017) showed that the (r − 2) -fold enlargement of M 2 2 for r = 5 , 6 or 7 is λ -perfect, where M s r is the r -uniform matching of size s. The result given by Sidorenko (1989) implies that the (r − 2) -fold enlargement of M t 2 for r = 5 and t ≥ 4, or r = 6 and t ≥ 6, or r = 7 and t ≥ 8 is λ -perfect. So there are still some gaps between the results of Jenssen and Sidorenko. In this paper we fill the gaps for r = 5 or 6. We also determine the Lagrangian densities for the (r − 3) -fold enlargement of M t 3 for r = 5 or 6. [ABSTRACT FROM AUTHOR]