Abstract:
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∼k′n and t∼t′n as n→∞, and k′∈(0,1), t′∈(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⩾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δ,ω), which is widely used in coding theory and is defined as the maximum number of bit strings of length n and weight ω having Hamming distance at least 2δ from one another.
Bibliography: 38 titles.
Keywords:
hypergraphs with one forbidden intersection of edges, Frankl-Wilson Theorem, constant-weight error-correcting codes, Nelson-Hadwiger problem.
This work was supported by the Russian Foundation for Basic Research (grant no. 15-01-03530) and by the Ministry of Education and Science of the Russian Federation (grant nos. МД-6008.2015.1 and НШ-2964.2014.1).
Citation:
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection”, Sb. Math., 207:5 (2016), 652–677
\Bibitem{BobKupRai16}
\by A.~V.~Bobu, A.~E.~Kupriyanov, A.~M.~Raigorodskii
\paper Asymptotic study of the maximum number of edges in a~uniform hypergraph with one forbidden intersection
\jour Sb. Math.
\yr 2016
\vol 207
\issue 5
\pages 652--677
\mathnet{http://mi.mathnet.ru/eng/sm8473}
\crossref{https://doi.org/10.1070/SM8473}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3507497}
\zmath{https://zbmath.org/?q=an:1345.05024}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2016SbMat.207..652B}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000380765400002}
\elib{https://elibrary.ru/item.asp?id=26414394}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84979675840}
Linking options:
https://www.mathnet.ru/eng/sm8473
https://doi.org/10.1070/SM8473
https://www.mathnet.ru/eng/sm/v207/i5/p17
This publication is cited in the following 19 articles:
D. A. Zakharov, “Chromatic Numbers of Some Distance Graphs”, Math. Notes, 107:2 (2020), 238–246
Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “A Generalization of Kneser Graphs”, Math. Notes, 107:3 (2020), 392–403
A. A. Sagdeev, “On the Chromatic Numbers Corresponding to Exponentially Ramsey Sets”, J Math Sci, 247:3 (2020), 488
D. A. Zakharov, A. M. Raigorodskii, “Clique Chromatic Numbers of Intersection Graphs”, Math. Notes, 105:1 (2019), 137–139
Ph. A. Pushnyakov, “The Number of Edges in Induced Subgraphs of Some Distance Graphs”, Math. Notes, 105:4 (2019), 582–591
A. M. Raigorodskii, E. D. Shishunov, “On the independence numbers of some distance graphs with vertices in (-1,0,1)(N)”, Dokl. Math., 99:2 (2019), 165–166
A. A. Sagdeev, “On a Frankl–Wilson Theorem”, Problems Inform. Transmission, 55:4 (2019), 376–395
A. A. Sagdeev, A. M. Raigorodskii, “On a Frankl-Wilson theorem and its geometric corollaries”, Acta Math. Univ. Comen., 88:3 (2019), 1029–1033
A. M. Raigorodskii, A. A. Sagdeev, “On a bound in extremal combinatorics”, Dokl. Math., 97:1 (2018), 47–48
A. A. Sagdeev, “Improved Frankl–Rödl theorem and some of its geometric consequences”, Problems Inform. Transmission, 54:2 (2018), 139–164
A. Sagdeev, “On the Frankl–Rödl theorem”, Izv. Math., 82:6 (2018), 1196–1224
A. A. Sagdeev, “Exponentially Ramsey sets”, Problems Inform. Transmission, 54:4 (2018), 372–396
A. A. Sagdeev, “O khromaticheskikh chislakh, sootvetstvuyuschikh eksponentsialno ramseevskim mnozhestvam”, Kombinatorika i teoriya grafov. X, Zap. nauchn. sem. POMI, 475, POMI, SPb., 2018, 174–189
A. M. Raigorodskii, T. V. Trukhan, “On the chromatic numbers of some distance graphs”, Dokl. Math., 98:2 (2018), 515–517
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “On the number of edges of a uniform hypergraph with a range of allowed intersections”, Problems Inform. Transmission, 53:4 (2017), 319–342
A. V. Bobu, A. E. Kupriyanov, “On chromatic numbers of close-to-Kneser distance graphs”, Problems Inform. Transmission, 52:4 (2016), 373–390
A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fundam. Inform., 145:3 (2016), 359–369
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “On the number of edges in a uniform hypergraph with a range of permitted intersections”, Dokl. Math., 96:1 (2017), 354–357
Citation in format AMSBIB
Contact us: