×

Improvements of the Frankl-Rödl theorem on the number of edges of a hypergraph with forbidden intersections, and their consequences in the problem of finding the chromatic number of a space with forbidden equilateral triangle. (English. Russian original) Zbl 1319.05095

Proc. Steklov Inst. Math. 288, 94-104 (2015); translation from Tr. Mat. Inst. Steklova 288, 109-119 (2015).
Summary: We survey the results (both old and new) related to the classical Frankl-Rödl theorem on the upper bound for the product of cardinalities of edge sets of two hypergraphs satisfying the condition that the intersection of any two edges of different hypergraphs cannot consist of a prescribed number of vertices. We also present corollaries to these results in the problem of finding the chromatic number of a space with a forbidden equilateral triangle with monochromatic vertices.

MSC:

05C65 Hypergraphs
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Frankl and V. Rödl, “Forbidden intersections,” Trans. Am. Math. Soc. 300 (1), 259-286 (1987). · Zbl 0611.05002 · doi:10.1090/S0002-9947-1987-0871675-6
[2] A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, and A. A. Kharlamova, “Improvement of the Frankl-Rödl theorem on the number of edges in hypergraphs with forbidden cardinalities of edge intersections,” Dokl. Akad. Nauk 457 (2), 144-146 (2014) [Dokl. Math. 90 (1), 432-434 (2014)]. · Zbl 1306.05174
[3] A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, and A. A. Kharlamova, “On the chromatic number of a space with forbidden equilateral triangle,” Mat. Sb. 205 (9), 97-120 (2014) [Sb. Math. 205, 1310-1333 (2014)]. · Zbl 1307.05169 · doi:10.4213/sm8312
[4] R. Ahlswede and L. H. Khachatrian, “The complete nontrivial-intersection theorem for systems of finite sets,” J. Comb. Theory A 76, 121-138 (1996). · Zbl 0861.05058 · doi:10.1006/jcta.1996.0092
[5] R. Ahlswede and L. H. Khachatrian, “The complete intersection theorem for systems of finite sets,” Eur. J. Comb. 18, 125-136 (1997). · Zbl 0869.05066 · doi:10.1006/eujc.1995.0092
[6] R. Ahlswede and V. Blinovsky, Lectures on Advances in Combinatorics (Springer, Berlin, 2008). · Zbl 1182.05002 · doi:10.1007/978-3-540-78602-3
[7] A. M. Raigorodskii, Probability and Algebra in Combinatorics, 2nd ed. (MTsNMO, Moscow, 2010) [in Russian].
[8] A. M. Raigorodskii, A Linear-Algebraic Method in Combinatorics (MTsNMO, Moscow, 2007) [in Russian]. · Zbl 1227.05003
[9] Borg, P.; Baswell, A. R. (ed.), Intersecting families of sets and permutations: A survey, 287-302 (2012), New York
[10] P. Borg, “The maximum sum and the maximum product of sizes of cross-intersecting families,” Eur. J. Comb. 35, 117-130 (2014). · Zbl 1296.05191 · doi:10.1016/j.ejc.2013.06.029
[11] P. Frankl, S. J. Lee, M. Siggers, and N. Tokushige, “An Erdšs-Ko-Rado theorem for cross <Emphasis Type=”Italic“>t-intersecting families,” J. Comb. Theory A 128, 207-249 (2014); arXiv: 1303.0657 [math.CO]. · Zbl 1301.05316 · doi:10.1016/j.jcta.2014.08.006
[12] P. Frankl and R. M. Wilson, “Intersection theorems with geometric consequences,” Combinatorica 1, 357-368 (1981). · Zbl 0498.05048 · doi:10.1007/BF02579457
[13] E. I. Ponomarenko and A. M. Raigorodskii, “An improvement of the Frankl-Wilson theorem on the number of edges in a hypergraph with forbidden intersections of edges,” Dokl. Akad. Nauk 454 (3), 268-269 (2014) [Dokl. Math. 89 (1), 59-60 (2014)]. · Zbl 1306.05108
[14] E. I. Ponomarenko and A. M. Raigorodskii, “New estimates in the problem of the number of edges in a hypergraph with forbidden intersections,” Probl. Peredachi Inf. 49 (4), 98-104 (2013) [Probl. Inf. Transm. 49, 384-390 (2013)]. · Zbl 1308.05083
[15] E. I. Ponomarenko and A. M. Raigorodskii, “New upper bounds for the independence numbers of graphs with vertices in {−1, 0, 1}n and their applications to problems of the chromatic numbers of distance graphs,” Mat. Zametki 96 (1), 138-147 (2014) [Math. Notes 96, 140-148 (2014)]. · Zbl 1312.05110 · doi:10.4213/mzm10352
[16] R. C. Baker, G. Harman, and J. Pintz, “The difference between consecutive primes. II,” Proc. London Math. Soc., Ser. 3, 83, 532-562 (2001). · Zbl 1016.11037 · doi:10.1112/plms/83.3.532
[17] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam, 1977). · Zbl 0369.94008
[18] V. A. Zinov’ev and T. Ericson, “On concatenated constant-weight codes beyond the Varshamov-Gilbert bound,” Probl. Peredachi Inf. 23 (1), 110-111 (1987). · Zbl 0635.94019
[19] H. Hadwiger, “Ein Überdeckungssatz für den Euklidischen Raum,” Port. Math. 4, 140-144 (1944). · Zbl 0060.40610
[20] A. M. Raigorodskii, Chromatic Numbers (MTsNMO, Moscow, 2003) [in Russian]. · Zbl 1125.05041
[21] J. Pach and P. K. Agarwal, Combinatorial Geometry (J. Wiley & Sons, New York, 1995). · Zbl 0881.52001 · doi:10.1002/9781118033203
[22] V. Klee and S. Wagon, Old and New Unsolved Problems in Plane Geometry and Number Theory (Math. Assoc. Am., Washington, DC, 1991). · Zbl 0784.51002
[23] A. Soifer, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators (Springer, New York, 2009). · Zbl 1221.05001
[24] P. Brass, W. Moser, and J. Pach, Research Problems in Discrete Geometry (Springer, New York, 2005). · Zbl 1086.52001
[25] A. M. Raigorodskii, “Borsuk’s problem and the chromatic numbers of some metric spaces,” Usp. Mat. Nauk 56 (1), 107-146 (2001) [Russ. Math. Surv. 56, 103-139 (2001)]. · Zbl 1008.54018 · doi:10.4213/rm358
[26] Raigorodskii, A. M., Cliques and cycles in distance graphs and graphs of diameters, 93-109 (2014), Providence, RI · Zbl 1338.52019 · doi:10.1090/conm/625/12493
[27] Raigorodskii, A. M.; Pach, J. (ed.), Coloring distance graphs and graphs of diameters, 429-460 (2013), Berlin · Zbl 1272.05058 · doi:10.1007/978-1-4614-0110-0_23
[28] Székely, L. A., Erdős on unit distances and the Szemerédi-Trotter theorems, 649-666 (2002), Berlin · Zbl 1035.05037
[29] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory, 2nd ed. (J. Wiley & Sons, New York, 1990). · Zbl 0705.05061
[30] A. M. Raigorodskii, “On the chromatic number of a space,” Usp. Mat. Nauk 55 (2), 147-148 (2000) [Russ. Math. Surv. 55, 351-352 (2000)]. · Zbl 0966.05029 · doi:10.4213/rm281
[31] P. Frankl and V. Rödl, “All triangles are Ramsey,” Trans. Am. Math. Soc. 297 (2), 777-779 (1986). · Zbl 0598.05003 · doi:10.1090/S0002-9947-1986-0854099-6
[32] P. Frankl and V. Rödl, “A partition property of simplices in Euclidean space,” J. Am. Math. Soc. 3 (1), 1-7 (1990). · Zbl 0696.05014 · doi:10.1090/S0894-0347-1990-1020148-2
[33] A. M. Raigorodskii and D. V. Samirov, “Chromatic numbers of spaces with forbidden monochromatic triangles,” Mat. Zametki 93 (1), 117-126 (2013) [Math. Notes 93, 163-171 (2013)]. · Zbl 1330.05076 · doi:10.4213/mzm9055
[34] Samirov, D. V.; Raigorodskii, A. M., New lower bounds for the chromatic number of a space with forbidden isosceles triangles (2013), Moscow · Zbl 1338.05093
[35] D. V. Samirov and A. M. Raigorodskii, “New bounds for the chromatic number of a space with forbidden isosceles triangles,” Dokl. Akad. Nauk 456 (3), 280-283 (2014) [Dokl. Math. 89 (3), 313-316 (2014)]. · Zbl 1303.05068
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.