Lagrangian densities of enlargements of matchings in hypergraphs. (English) Zbl 1433.05238
Summary: 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 \(\operatorname{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 \(\pi (H)\), is the limit of the function \(\frac{ e x ( n , H )}{ \binom{n}{r}}\) as \(n \rightarrow \infty \). The Lagrangian density of \(H\) is \(\pi_\lambda ( H ) = \sup \{ r ! \lambda ( F ) : H\text{ is not contained in }F \}\), where \(\lambda (F)\) is the Lagrangian of \(F\). For any \(r\)-uniform graph \(H\), A. F. Sidorenko [Math. Notes 41, 247–259 (1987; Zbl 0677.05064); translation from Mat. Zametki 41, No. 3, 433–455 (1987)] showed that \( \pi_\lambda (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, \pi_\lambda ( H ) \geq r ! \lambda ( 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 \(\lambda \)-perfect if the equality holds, i.e., \( \pi_\lambda ( H ) = r ! \lambda ( K_{t - 1}^r )\). A result given by T. S. Motzkin and E. G. Straus [Can. J. Math. 17, 533–540 (1965; Zbl 0129.39902)] shows that every graph is \(\lambda \)-perfect. It is natural and fundamental to explore which hypergraphs are \(\lambda \)-perfect. In [Combinatorica 9, No. 2, 207–215 (1989; Zbl 0732.05031)], A. F. Sidorenko showed that the \(( r - 2 )\)-fold enlargement of a tree satisfying the Erdős-Sós conjecture with order at least \(A_r\) is \(\lambda \)-perfect, where \(A_r\) is the last maximum of the function \(g_r ( x ) = ( r + x - 3 )^{-r} \prod_{i = 1}^{r - 1} ( i + x - 2 )\) as \(x \geq 2\). By using the so-called generalised Lagrangian of hypergraphs, M. Jenssen [Continuous optimisation in extremal combinatorics. London: London School of Economics and Political Science (PhD Thesis) (2017)] showed that the \(( r - 2 )\)-fold enlargement of \(M_2^2\) for \(r = 5\), 6 or 7 is \(\lambda\)-perfect, where \(M_s^r\) is the \(r\)-uniform matching of size \(s\). The result given by Sidorenko [1989, loc. cit.] implies that the \(( r - 2 )\)-fold enlargement of \(M_t^2\) for \(r = 5\) and \(t \geq 4\), or \(r = 6\) and \(t \geq 6\), or \(r = 7\) and \(t \geq 8\) is \(\lambda \)-perfect. So there are still some gaps between the results of Jenssen [loc. cit.] and Sidorenko [loc. cit.]. 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.
Given an integer \(n\) and an \(r\)-uniform graph \(H\), the Turán number of \(H\), denoted by \(\operatorname{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 \(\pi (H)\), is the limit of the function \(\frac{ e x ( n , H )}{ \binom{n}{r}}\) as \(n \rightarrow \infty \). The Lagrangian density of \(H\) is \(\pi_\lambda ( H ) = \sup \{ r ! \lambda ( F ) : H\text{ is not contained in }F \}\), where \(\lambda (F)\) is the Lagrangian of \(F\). For any \(r\)-uniform graph \(H\), A. F. Sidorenko [Math. Notes 41, 247–259 (1987; Zbl 0677.05064); translation from Mat. Zametki 41, No. 3, 433–455 (1987)] showed that \( \pi_\lambda (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, \pi_\lambda ( H ) \geq r ! \lambda ( 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 \(\lambda \)-perfect if the equality holds, i.e., \( \pi_\lambda ( H ) = r ! \lambda ( K_{t - 1}^r )\). A result given by T. S. Motzkin and E. G. Straus [Can. J. Math. 17, 533–540 (1965; Zbl 0129.39902)] shows that every graph is \(\lambda \)-perfect. It is natural and fundamental to explore which hypergraphs are \(\lambda \)-perfect. In [Combinatorica 9, No. 2, 207–215 (1989; Zbl 0732.05031)], A. F. Sidorenko showed that the \(( r - 2 )\)-fold enlargement of a tree satisfying the Erdős-Sós conjecture with order at least \(A_r\) is \(\lambda \)-perfect, where \(A_r\) is the last maximum of the function \(g_r ( x ) = ( r + x - 3 )^{-r} \prod_{i = 1}^{r - 1} ( i + x - 2 )\) as \(x \geq 2\). By using the so-called generalised Lagrangian of hypergraphs, M. Jenssen [Continuous optimisation in extremal combinatorics. London: London School of Economics and Political Science (PhD Thesis) (2017)] showed that the \(( r - 2 )\)-fold enlargement of \(M_2^2\) for \(r = 5\), 6 or 7 is \(\lambda\)-perfect, where \(M_s^r\) is the \(r\)-uniform matching of size \(s\). The result given by Sidorenko [1989, loc. cit.] implies that the \(( r - 2 )\)-fold enlargement of \(M_t^2\) for \(r = 5\) and \(t \geq 4\), or \(r = 6\) and \(t \geq 6\), or \(r = 7\) and \(t \geq 8\) is \(\lambda \)-perfect. So there are still some gaps between the results of Jenssen [loc. cit.] and Sidorenko [loc. cit.]. 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.
MSC:
| 05C65 | Hypergraphs |
| 05D05 | Extremal set theory |
| 05C35 | Extremal problems in graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Brandt, A.; Irwin, D.; Jiang, T., Stability and Turán numbers of a class of hypergraphs via Lagrangians, Combin. Probab. Comput., 26, 3, 367-405 (2017) · Zbl 1371.05198 |
| [2] | Chen, P.; Liang, J.; Peng, Y., The lagrangian density of {123, 234, 456} and the Turán number of its extensions, Discuss. Math. Graph Theory (2019) |
| [3] | Erdős, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Mathematica Academiae Scientiarum Hungarica, 10, 337-356 (1959) · Zbl 0090.39401 |
| [4] | Frankl, P., Extremal set systems, Handbook of Combinatorics, 1293-1329 (1995), Elsevier: Elsevier Amsterdam · Zbl 0844.05094 |
| [5] | Frankl, P., On the maximum number of edges in a hypergraph with given matching number, Discret. Appl. Math., 216, 562-581 (2017) · Zbl 1358.05202 |
| [6] | Frankl, P.; Füredi, Z., Extremal problems whose solutions are the blow-ups of the small Witt-designs, J. Combin. Theory Ser. A., 52, 129-147 (1989) · Zbl 0731.05030 |
| [7] | Frankl, P.; Rödl, V., Hypergraphs do not jump, Combinatorica, 4, 149-159 (1984) · Zbl 0663.05047 |
| [8] | V. Gruslys, S. Letzter, N. Morrison, Hypergraph Lagrangians: the Frankl-Füredi conjecture is false, 2019, Preprint. arXiv:1807.00793v3, · Zbl 1435.05152 |
| [9] | Hefetz, D.; Keevash, P., A hypergraph Turán theorem via Lagrangians of intersecting families, J. Combin. Theory Ser. A, 120, 2020-2038 (2013) · Zbl 1278.05162 |
| [10] | Hu, S.; Peng, Y.; Wu, B., Lagrangian densities of linear forests and Turán numbers of their extensions, J. Comb. Des., 28, 207-223 (2020) · Zbl 1536.05247 |
| [11] | Ph.D. Dissertation |
| [12] | Jiang, T.; Peng, Y.; Wu, B., Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions, Eur. J. Comb., 73, 20-36 (2018) · Zbl 1393.05169 |
| [13] | H. Lei, L. Lu, Y. Peng, On Lagrangians of 3-uniform hypergraphs, 2018, Preprint. arXiv:1806.10846v1, |
| [14] | Liu, S.; Peng, Y., Generating non-jumping numbers of hypergraphs, Bull. Korean Math. Soc., 56, 1027-1039 (2019) · Zbl 1423.05112 |
| [15] | Motzkin, T. S.; Straus, E. G., Maxima for graphs and a new proof of a theorem of turán, Canad. J. Math, 17, 533-540 (1965) · Zbl 0129.39902 |
| [16] | Norin, S.; Yepremyan, L., Turán numbers of extensions, J. Combin. Theory Ser. A, 155, 476-492 (2018) · Zbl 1377.05129 |
| [17] | Peng, Y.; Zhao, C., A Motzkin-Straus type result for 3-uniform hypergraphs, Graphs Combin., 29, 681-694 (2013) · Zbl 1267.05185 |
| [18] | Pikhurko, O., An exact Turán result for the generalized triangle, Combinatorica, 28, 187-208 (2008) · Zbl 1175.05137 |
| [19] | Sidorenko, A. F., On the maximal number of edges in a homogeneous hypergraph that does not contain prohibited subgraphs, Mat. Zametki, 41, 433-455 (1987) · Zbl 0677.05064 |
| [20] | Sidorenko, A. F., Asymptotic solution for a new class of forbidden r-graphs, Combinatorica, 9, 207-215 (1989) · Zbl 0732.05031 |
| [21] | Talbot, J., Lagrangians of hypergraphs, Combin., Probab. & Comput., 11, 199-216 (2002) · Zbl 0998.05049 |
| [22] | Tang, Q. S.; Peng, Y.; Zhang, X. D.; Zhao, C., Connection between the clique number and the lagrangian of 3-uniform hypergraphs, Optim. Lett., 10.4, 685-697 (2016) · Zbl 1368.90164 |
| [23] | Tyomkyn, M., Lagrangians of hypergraphs: the Frankl-Füredi conjecture holds almost everywhere, J. Lond. Math. Soc., 96, 584-600 (2017) · Zbl 1378.05149 |
| [24] | Yan, Z.; Peng, Y., Lagrangian densities of hypergraph cycles, Discret. Math., 342, 2048-2059 (2019) · Zbl 1420.05124 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
