×

On the algebraic and topological structure of the set of Turán densities. (English) Zbl 1332.05103

Summary: The present paper is concerned with the various algebraic structures supported by the set of Turán densities. We prove that the set of Turán densities of finite families of \(r\)-graphs is a non-trivial commutative semigroup, and as a consequence we construct explicit irrational densities for any \(r \geq 3\). The proof relies on a technique recently developed by O. Pikhurko [Isr. J. Math. 201, Part A, 415–454 (2014; Zbl 1302.05097)]. We also show that the set of all Turán densities forms a graded ring, and from this we obtain a short proof of a theorem of Y. Peng [Graphs Comb. 25, No. 5, 759–766 (2009; Zbl 1205.05164)] on jumps of hypergraphs. Finally, we prove that the set of Turán densities of families of \(r\)-graphs has positive Lebesgue measure if and only if it contains an open interval. This is a simple consequence of Steinhaus’s theorem.

MSC:

05C65 Hypergraphs
05C42 Density (toughness, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C35 Extremal problems in graph theory

Software:

Flagmatic
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baber, R.; Talbot, J., Hypergraphs do jump, Combin. Probab. Comput., 20, 2, 161-171 (2011) · Zbl 1213.05184
[2] Baber, R.; Talbot, J., New Turán densities for 3-graphs, Electron. J. Combin., 19 (2012), 21 pp · Zbl 1244.05122
[3] Baber, R.; Talbot, J., A solution to the 2/3 conjecture, SIAM J. Discrete Math., 28, 2, 756-766 (2014) · Zbl 1298.05099
[4] Bollobás, B.; Leader, I.; Malvenuto, C., Daisies and other Turán problems, Combin. Probab. Comput., 20, 5, 743-747 (2011) · Zbl 1293.05381
[5] Bourgain, J., On the Erdős-Volkmann and Katz-Tao ring conjectures, Geom. Funct. Anal., 13, 2, 334-365 (2003) · Zbl 1115.11049
[6] Brown, W. G.; Simonovits, M., Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures, Discrete Math., 48, 147-162 (1984) · Zbl 0541.05035
[7] Carr, R.; O’Sullivan, C., On the linear independence of roots, Int. J. Number Theory, 5, 1, 161-171 (2009) · Zbl 1195.12004
[8] Cheon, G.-S.; Wanless, I. M., Some results towards the Dittert conjecture on permanents, Linear Algebra Appl., 436, 791-801 (2012) · Zbl 1239.15004
[9] Cheon, G.-S.; Yoon, H.-W., A note on the Dittert conjecture for permanents, Int. Math. Forum, 1, 39, 1943-1949 (2006) · Zbl 1306.15008
[10] Chung, F.; Graham, R., Erdős on Graphs: His Legacy of Unsolved Problems (1998), A. K. Peters: A. K. Peters Wellesley, Massachusetts · Zbl 0890.05049
[11] Edgar, G. A.; Miller, C., Borel subrings of the reals, Proc. Amer. Math. Soc., 131, 1121-1129 (2003) · Zbl 1043.28003
[12] Emtander, E., Betti numbers of hypergraphs, Comm. Algebra, 37, 5, 1545-1571 (2009) · Zbl 1191.13015
[13] Erdős, P., On extremal problems of graphs and generalized graphs, Israel J. Math., 2, 183-190 (1964) · Zbl 0129.39905
[14] Erdős, P., On some extremal problems on \(r\)-graphs, Discrete Math., 1, 1, 1-6 (1971) · Zbl 0211.27003
[15] Erdős, P., On some of my conjectures in number theory and combinatorics, (Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing. Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, vol. 39 (1983)), 3-19
[16] Erdős, P.; Simonovits, M., A limit theorem in graph theory, Studia Sci. Math. Hungar., 1, 51-57 (1966) · Zbl 0178.27301
[17] Erdős, P.; Stone, A. H., On the structure of linear graphs, Bull. Amer. Math. Soc., 52, 1087-1091 (1946) · Zbl 0063.01277
[18] Erdős, P.; Volkmann, B., Additive Gruppen mit vorgegebener Hausdorffscher Dimension, J. Reine Angew. Math., 221, 203-208 (1966) · Zbl 0135.10202
[19] Falgas-Ravry, V.; Vaughan, E., Applications of the semi-definite method to the Turán density problem for 3-graphs, Combin. Probab. Comput., 22, 1, 21-54 (2013) · Zbl 1257.05077
[20] Frankl, P.; Peng, Y.; Rödl, V.; Talbot, J., A note on the jumping constant conjecture of Erdős, J. Combin. Theory Ser. B, 87, 2, 204-216 (2007) · Zbl 1110.05052
[21] Frankl, P.; Rödl, V., Hypergraphs do not jump, Combinatorica, 4, 2-3, 149-159 (1984) · Zbl 0663.05047
[22] Glebov, R.; Král’, D.; Volec, J., A problem of Erdős and Sós on 3-graphs, Israel J. Math. (2015), in press
[23] Gowers, W. T., Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math., 166, 3, 897-946 (2007) · Zbl 1159.05052
[24] Grzesik, A., On the maximum number of five-cycles in a triangle-free graph, J. Combin. Theory Ser. B, 102, 5, 1061-1066 (2012) · Zbl 1252.05093
[25] Gurvits, L., Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all, Electron. J. Combin., 15 (2008), 26 pp · Zbl 1182.15008
[26] Hajek, B., A conjectured generalized permanent inequality and a multiaccess problem, (Cover, T.; Gopinath, B., Open Problems in Communication and Computation (1987), Springer-Verlag: Springer-Verlag New York), 127-129
[27] Hatami, H.; Hladký, J.; Král’, D.; Norine, S.; Razborov, A., Non-three-colorable common graphs exist, Combin. Probab. Comput., 21, 5, 734-742 (2012) · Zbl 1248.05090
[28] Hatami, H.; Hladký, J.; Král’, D.; Norine, S.; Razborov, A., On the number of pentagons in triangle-free graphs, J. Combin. Theory Ser. A, 120, 3, 722-732 (2013) · Zbl 1259.05087
[29] Hwang, S. G., A note on a conjecture on permanents, Linear Algebra Appl., 76, 31-44 (1986) · Zbl 0589.15016
[30] Hwang, S. G., On a conjecture of E. Dittert, Linear Algebra Appl., 95, 161-169 (1987) · Zbl 0628.15018
[31] Katona, G. O.H.; Nemetz, T.; Simonovits, M., On a graph problem of Turán, Mat. Fiz. Lapok, 15, 228-238 (1964), (in Hungarian) · Zbl 0138.19402
[32] Keevash, P., Hypergraph Turán problems, (Chapman, R., Surveys in Combinatorics (2011), Cambridge Univ. Press), 83-140 · Zbl 1244.05159
[33] Keevash, P.; Sudakov, B., On a hypergraph Turán problem of Frankl, Combinatorica, 25, 6, 673-706 (2005) · Zbl 1089.05075
[34] Körner, J.; Marton, K., Random Access Communication and Graph Entropy, IEEE Trans. Inform. Theory, 34, 2, 312-314 (1988) · Zbl 0667.94001
[35] Král’, D.; Liu, C.-H.; Sereni, J.-S.; Whalen, P.; Yilma, Z., A new bound for the 2/3 conjecture, Combin. Probab. Comput., 22, 3, 384-393 (2013) · Zbl 1263.05052
[36] Minc, H., Theory of permanents 1978-1981, Linear Multilinear Algebra, 12, 227-263 (1983) · Zbl 0511.15002
[37] Nagle, B.; Rödl, V.; Schacht, M., The counting lemma for regular \(k\)-uniform hypergraphs, Random Structures Algorithms, 28, 2, 113-179 (2006) · Zbl 1093.05045
[38] Peng, Y., Non-jumping numbers for 4-uniform hypergraphs, Graphs Combin., 23, 1, 97-110 (2007) · Zbl 1115.05045
[39] Peng, Y., Using Lagrangians of hypergraphs to find non-jumping numbers II, Discrete Math., 307, 14, 1754-1766 (2007) · Zbl 1128.05029
[40] Peng, Y., Using Lagrangians of hypergraphs to find non-jumping numbers I, Ann. Comb., 12, 307-324 (2008) · Zbl 1201.05101
[41] Peng, Y., On jumping densities of hypergraphs, Graphs Combin., 25, 5, 759-766 (2009) · Zbl 1205.05164
[42] Peng, Y.; Zhao, C., Generating non-jumping numbers recursively, Discrete Appl. Math., 156, 10, 1856-1864 (2008) · Zbl 1185.05109
[43] Pikhurko, O., On possible Turán densities, Israel J. Math., 201, 415-454 (2014) · Zbl 1302.05097
[44] Pikhurko, O., The maximal length of a gap between \(r\)-graph Turán densities, Electron. J. Combin., 22, 4 (2015), 7 pp · Zbl 1323.05078
[45] Razborov, A., Flag Algebras, J. Symbolic Logic, 72, 4, 1239-1282 (2007) · Zbl 1146.03013
[46] Razborov, A., On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discrete Math., 24, 3, 946-963 (2010) · Zbl 1223.05204
[47] Rödl, V.; Schacht, M., Generalizations of the removal lemma, Combinatorica, 29, 4, 467-501 (2009) · Zbl 1212.05133
[48] Rödl, V.; Skokan, J., Regularity lemma for \(k\)-uniform hypergraphs, Random Structures Algorithms, 25, 1, 1-42 (2004) · Zbl 1046.05042
[49] Rödl, V.; Skokan, J., Applications of the regularity lemma for uniform hypergraphs, Random Structures Algorithms, 28, 2, 180-194 (2006) · Zbl 1087.05031
[50] Ruzsa, I.; Szemerédi, E., Triple systems with no six points carrying three triangles, (Combinatorics, vol. II. Combinatorics, vol. II, Keszthely, 1976. Combinatorics, vol. II. Combinatorics, vol. II, Keszthely, 1976, Colloq. Math. Soc. János Bolyai, vol. 18 (1978), North-Holland: North-Holland Amsterdam), 939-945
[51] Sidorenko, A., Extremal combinatorial problems in spaces with continuous measure, Issled. Oper. ASU, 34, 34-40 (1989), (in Russian) · Zbl 0925.90369
[52] Sidorenko, A., Asymptotic solution of the Turán problem for some hypergraphs, Graphs Combin., 8, 2, 199-201 (1992) · Zbl 0769.05071
[53] Simonovits, M., A method for solving extremal problems in graph theory, stability problems, (Theory of Graphs, Proc. Colloq.. Theory of Graphs, Proc. Colloq., Tihany, 1966. Theory of Graphs, Proc. Colloq.. Theory of Graphs, Proc. Colloq., Tihany, 1966, Bolyai Soc. Math. Stud. (1968), Academic Press), 279-319
[54] Sinkhorn, R., A problem related to the van der Waerden permanent theorem, Linear Multilinear Algebra, 16, 167-173 (1984) · Zbl 0568.15004
[55] Steinhaus, H., Sur le distances des points dans les ensembles de mesure positive, Fund. Math., 1, 1, 93-104 (1920) · JFM 47.0179.02
[56] Turán, P., Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, 48, 436-452 (1941) · JFM 67.0732.03
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.