Search

A real number α∈[0,1) is a jump for an integer r≥2 if there exists a constant c>0 such that any number in (α,α+c] cannot be the Turán density of a family of r-uniform graphs. Erdős and Stone showed that every number in [0,1) is a jump for r=2. Erdős asked whether the same is true for r≥3. Frankl and Rödl gave a negative answer by showing the existence of non-jumps for r≥3. Recently, Baber and Talbot showed that every number in [0.2299,0.2316)⋃[0.2871,827) is a jump for r=3 using Razborov’s flag algebra method. Pikhurko showed that the set of non-jumps for every r≥3 has cardinality of the continuum. But, there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we show that 1+r-1lr-1-rlr-2 is a non-jump for r≥4 and l≥3 which generalizes some earlier results. We do not know whether the same result holds for r=3. In fact, when r=3 and l=3, 1+r-1lr-1-rlr-2=29, and determining whether 29 is a jump or not for r=3 is perhaps the most important unknown question regarding this subject. Erdős offered $500 for answering this question. [ABSTRACT FROM AUTHOR]

In 1965, Motzkin–Straus established the connection between the maximum cliques and the Lagrangian of a graph, the maximum value of a quadratic function determined by a graph in the standard simplex. This connection gave a proof of the Turán’s classical result on Turán densities of complete graphs. In 1980’s, Sidorenko and Frankl–Füredi further developed this method for hypergraph Turán problems. However, the connection between the Lagrangian and the maximum cliques of a graph cannot be extended to hypergraphs. In 2009, S. Rota Bulò and M. Pelillo defined a homogeneous polynomial function of degree r determined by an r -uniform hypergraph and gave the connection between the minimum value of this polynomial function and the maximum cliques of an r -uniform hypergraph. In this paper, we provide a connection between the local (global) minimizers of non-homogeneous polynomial functions to the maximal (maximum) cliques of hypergraphs whose edges containing r − 1 and r vertices. This connection can be applied to obtain an upper bound on the Turán densities of complete { r − 1 , r } -type hypergraphs. [ABSTRACT FROM AUTHOR]

A real number α ∈ [ 0 , 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that no number in (α , α + c) can be the Turán density of a family of r -uniform graphs. A classical result of Erdős and Stone [8] implies that every number in [ 0 , 1) is a jump for r = 2. Erdős [6] also showed that every number in [ 0 , r ! / r r) is a jump for r ≥ 3 and asked whether every number in [ 0 , 1) is a jump for r ≥ 3. Frankl and Rödl [9] gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. After this, Erdős modified the question to be whether r ! r r is a jump for r ≥ 3 ? What's the smallest non-jump? Frankl, Peng, Rödl and Talbot [10] showed that 5 r ! 2 r r is a non-jump for r ≥ 3. However, Baber and Talbot [1] showed that there are more jumps by proving that every α ∈ [ 0.2299 , 0.2316) ∪ [ 0.2871 , 8 27) is a jump for r = 3. However, whether r ! r r is a jump for r ≥ 3 remains open, and 5 r ! 2 r r has remained the known smallest non-jump for r ≥ 3. In this paper, we give a smaller non-jump by showing that 54 r ! 25 r r is a non-jump for r ≥ 3. Furthermore, we give infinitely many irrational non-jumps for every r ≥ 3. [ABSTRACT FROM AUTHOR]

In 1965, Motzkin and Straus established a remarkable connection between the order of a maximum clique and the Lagrangian of a graph and provided a new proof of Turán’s theorem using the connection. The connection of Lagrangians and Turán densities can be also used to prove the fundamental theorem of Erdős–Stone–Simonovits on Turán densities of graphs. Very recently, the study of Turán densities of non-uniform hypergraphs has been motivated by extremal poset problems and suggested by Johnston and Lu. In this paper, we attempt to explore the applications of Lagrangian method in determining Turán densities of non-uniform hypergraphs. We first give a definition of the Lagrangian of a non-uniform hypergraph, then give an extension of the Motzkin–Straus theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Applying it, we give an extension of the Erdős–Stone–Simonovits theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Our approach follows from the approach in Keevash’s paper Keevash (2011). [ABSTRACT FROM AUTHOR]

Abstract: Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number is a jump for -uniform graphs if there exists a constant such that for any family of -uniform graphs, if the Turán density of is greater than , then the Turán density of is at least . A fundamental result in extremal graph theory due to Erdős and Stone implies that every number in is a jump for graphs. Erdős also showed that every number in is a jump for -uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in for -uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept–strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps. [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]