Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection

A. V. Bobu   ; A. E. Kupriyanov   ; A. M. Raigorodskii

Sbornik. Mathematics, Tome 207 (2016) no. 5, pp. 652-677

Résumé

The object of this research is the quantity $m(n,k,t)$ defined as the maximum number of edges in a $k$-uniform hypergraph possessing the property that no two edges intersect in $t$ vertices. The case when $k\sim k'n$ and $t \sim t'n$ as $n \to \infty$, and $k' \in (0,1)$, $t' \in (0,k')$ are fixed constants is considered in full detail. In the case when $2t < k$ the asymptotic accuracy of the Frankl-Wilson upper estimate is established; in the case when $2t \geqslant k$ new lower estimates for the quantity $m(n,k,t)$ are proposed. These new estimates are employed to derive upper estimates for the quantity $A(n,2\delta,\omega)$, which is widely used in coding theory and is defined as the maximum number of bit strings of length $n$ and weight $\omega$ having Hamming distance at least $2\delta$ from one another. Bibliography: 38 titles.

Détail

Keywords: hypergraphs with one forbidden intersection of edges, Frankl-Wilson Theorem, constant-weight error-correcting codes, Nelson-Hadwiger problem.

Bibliographie

[1] F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes, Parts I, II, North-Holland Math. Library, 16, North-Holland, Amsterdam–New York–Oxford, 1977, xv+ix+762 pp. | MR | MR | Zbl | Zbl

[2] L. Bassalygo, G. Cohen, G. Zémor, “Codes with forbidden distances”, Discrete Math., 213:1-3 (2000), 3–11 | DOI | MR | Zbl

[3] V. G. Boltyanski, H. Martini, P. S. Soltan, Excursions into combinatorial geometry, Universitext, Springer-Verlag, Berlin, 1997, xiv+418 pp. | MR | Zbl

[4] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem”, Surveys in contemporary mathematics, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2008, 202–247 | MR | Zbl

[5] A. M. Raigorodskii, “Around Borsuk's hypothesis”, J. Math. Sci. (N. Y.), 154:4 (2008), 604–623 | DOI | MR | Zbl

[6] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete geometry and algebraic combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109 | DOI | MR | Zbl

[7] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty essays on geometric graph theory, Springer-Verlag, New York, 2013, 429–460 | DOI | MR | Zbl

[8] A. M. Raigorodskii, “Borsuk's problem and the chromatic numbers of some metric spaces”, Russian Math. Surveys, 56:1 (2001), 103–139 | DOI | DOI | MR | Zbl

[9] A. M. Raigorodskii, “On the chromatic numbers of spheres in Euclidean spaces”, Dokl. Math., 81:3 (2010), 379–382 | DOI | MR | Zbl

[10] A. M. Raigorodskii, “On the chromatic numbers of spheres in $ {\mathbb R}^n $”, Combinatorica, 32:1 (2012), 111–123 | DOI | MR | Zbl

[11] P. K. Agarwal, J. Pach, Combinatorial geometry, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 1995, xiv+354 pp. | MR | Zbl

[12] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his mathematics (Budapest, 1999), v. II, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

[13] A. Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators, Springer-Verlag, New York, 2009, xxx+607 pp. | DOI | MR | Zbl

[14] V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Dolciani Math. Exp., 11, Math. Assoc. America, Washington, DC, 1991, xvi+333 pp. | MR | Zbl

[15] P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR | Zbl

[16] A. V. Bobu, O. A. Kostina, A. E. Kupriyanov, “Independence numbers and chromatic numbers of some distance graphs”, Problems Inform. Transmission, 51:2 (2015), 165–176 | DOI | Zbl

[17] E. I. Ponomarenko, A. M. Raigorodskii, “An improvement of the Frankl–Wilson theorem on the number of edges in a hypergraph with forbidden intersections of edges”, Dokl. Math., 89:1 (2014), 59–60 | DOI | DOI | MR | Zbl

[18] E. I. Ponomarenko, A. M. Raigorodskii, “New estimates in the problem of the number of edges in a hypergraph with forbidden intersections”, Problems Inform. Transmission, 49:4 (2013), 384–390 | DOI | MR | Zbl

[19] R. Ahlswede, L. H. Khachatrian, “The complete nontrivial-intersection theorem for systems of finite sets”, J. Combin. Theory Ser. A, 76:1 (1996), 121–138 | DOI | MR | Zbl

[20] R. Ahlswede, L. H. Khachatrian, “The complete intersection theorem for systems of finite sets”, European J. Combin., 18:2 (1997), 125–136 | DOI | MR | Zbl

[21] R. Ahlswede, V. Blinovsky, Lectures on advances in combinatorics, Universitext, Springer-Verlag, Berlin, 2008, xiv+314 pp. | DOI | MR | Zbl

[22] R. R. Varshamov, “Otsenka chisla signalov v kodakh s korrektsiei oshibok”, Dokl. AN SSSR, 117:5 (1957), 739–741 | Zbl

[23] E. N. Gilbert, “A comparison of signalling alphabets”, Bell Syst. Tech. J., 31:3 (1952), 504–522 | DOI

[24] V. I. Levenshtein, “Upper-bound estimates for fixed-weight codes”, Problems Inform. Transmission, 7:4 (1971), 281–287 | Zbl

[25] V. A. Zinov'ev, T. Ericson, “On concatenated constant-weight codes beyond the Varshamov–Gilbert bound”, Problems Inform. Transmission, 23:1 (1987), 110–111 | MR | Zbl

[26] V. Rödl, “On a packing and covering problem”, European J. Combin., 6:1 (1985), 69–78 | DOI | MR | Zbl

[27] R. W. Hamming, “Error detecting and error correcting codes”, Bell System Tech. J., 29:2 (1950), 147–160 | DOI | MR

[28] R. J. McEliece, E. R. Rodemich, H. Rumsey, Jr., L. R. Welch, “New upper bounds on the rate of a code via the Delsarte–MacWilliams inequalities”, IEEE Trans. Information Theory, 23:2 (1977), 157–166 | DOI | MR | Zbl

[29] L. A. Bassalygo, “New upper bounds for error correcting codes”, Problems Inform. Transmission, 1:4 (1965), 32–35 | MR | Zbl

[30] H. Hadwiger, “Ein Überdeckungssatz für den Euklidischen Raum”, Portugaliae Math., 4 (1944), 140–144 | MR | Zbl

[31] A. M. Raigorodskii, “On the chromatic number of a space”, Russian Math. Surveys, 55:2 (2000), 351–352 | DOI | DOI | MR | Zbl

[32] D. G. Larman, C. A. Rogers, “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24 | DOI | MR | Zbl

[33] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey theory, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., Wiley, New York, 1990, xii+196 pp. | MR | Zbl

[34] A. M. Raigorodskii, “The Borsuk problem for $(0,1)$-polyhedra and cross polytopes”, Dokl. Math., 61 (2), 256–259 | MR | Zbl

[35] A. M. Raigorodskii, “Borsuk's problem for $(0,1)$-polytopes and cross-polytopes”, Dokl. Math., 65:3 (2002), 413–416 | MR | Zbl

[36] A. M. Raigorodskii, “The Borsuk problem for integral polytopes”, Sb. Math., 193:10 (2002), 1535–1556 | DOI | DOI | MR | Zbl

[37] A. M. Raigorodskii, “The problem of Borsuk, Hadwiger, and Grünbaum for some classes of polytopes and graphs”, Dokl. Math., 67:1 (2003), 85–89 | MR | Zbl

[38] A. M. Raigorodskii, “The problems of Borsuk and Grünbaum on lattice polytopes”, Izv. Math., 69:3 (2005), 513–537 | DOI | DOI | MR | Zbl