General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Mat. Sb.:

Personal entry:
Save password
Forgotten password?

Mat. Sb., 2016, Volume 207, Number 5, Pages 17–42 (Mi msb8473)  

This article is cited in 16 scientific papers (total in 16 papers)

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

A. V. Bobua, A. E. Kupriyanova, A. M. Raigorodskiiabc

a Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Buryat State University, Institute for Mathematics and Informatics, Ulan-Ude
c Department of Innovations and High Technology, Moscow Institute of Physics and Technology

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\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 \ge 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.

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

Funding Agency Grant Number
Russian Foundation for Basic Research 15-01-03530
Ministry of Education and Science of the Russian Federation МД-6008.2015.1
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).

Author to whom correspondence should be addressed


Full text: PDF file (956 kB)
References: PDF file   HTML file

English version:
Sbornik: Mathematics, 2016, 207:5, 652–677

Bibliographic databases:

UDC: 519.112.74+519.176
MSC: Primary 05C15, 05C35; Secondary 63R10, 90C27
Received: 12.01.2015 and 18.01.2016

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”, Mat. Sb., 207:5 (2016), 17–42; Sb. Math., 207:5 (2016), 652–677

Citation in format AMSBIB
\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 Mat. Sb.
\yr 2016
\vol 207
\issue 5
\pages 17--42
\jour Sb. Math.
\yr 2016
\vol 207
\issue 5
\pages 652--677

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Bobu, A. E. Kupriyanov, “On chromatic numbers of close-to-Kneser distance graphs”, Problems Inform. Transmission, 52:4 (2016), 373–390  mathnet  crossref  isi  elib
    2. A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fundam. Inform., 145:3 (2016), 359–369  crossref  mathscinet  zmath  isi  scopus
    3. 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  crossref  crossref  zmath  isi  elib  scopus
    4. 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  mathnet  crossref  isi  elib
    5. A. M. Raigorodskii, A. A. Sagdeev, “On a bound in extremal combinatorics”, Dokl. Math., 97:1 (2018), 47–48  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    6. A. A. Sagdeev, “Improved Frankl–Rödl theorem and some of its geometric consequences”, Problems Inform. Transmission, 54:2 (2018), 139–164  mathnet  crossref  isi  elib
    7. A. Sagdeev, “On the Frankl–Rödl theorem”, Izv. Math., 82:6 (2018), 1196–1224  mathnet  crossref  crossref  adsnasa  isi  elib
    8. A. A. Sagdeev, “Exponentially Ramsey sets”, Problems Inform. Transmission, 54:4 (2018), 372–396  mathnet  crossref  isi  elib
    9. 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  mathnet
    10. A. M. Raigorodskii, T. V. Trukhan, “On the chromatic numbers of some distance graphs”, Dokl. Math., 98:2 (2018), 515–517  mathnet  crossref  crossref  zmath  isi  elib  scopus
    11. D. A. Zakharov, A. M. Raigorodskii, “Clique Chromatic Numbers of Intersection Graphs”, Math. Notes, 105:1 (2019), 137–139  mathnet  crossref  crossref  isi  elib
    12. Ph. A. Pushnyakov, “The Number of Edges in Induced Subgraphs of Some Distance Graphs”, Math. Notes, 105:4 (2019), 582–591  mathnet  crossref  crossref  isi  elib
    13. Raigorodskii A.M., Shishunov E.D., “On the Independence Numbers of Some Distance Graphs With Vertices in (-1,0,1)(N)”, Dokl. Math., 99:2 (2019), 165–166  crossref  isi
    14. D. A. Zakharov, “O khromaticheskikh chislakh nekotorykh distantsionnykh grafov”, Matem. zametki, 107:2 (2020), 210–220  mathnet  crossref
    15. F. A. Pushnyakov, A. M. Raigorodskii, “Otsenka chisla reber v osobykh podgrafakh nekotorogo distantsionnogo grafa”, Matem. zametki, 107:2 (2020), 286–298  mathnet  crossref
    16. A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “Ob odnom obobschenii knezerovskikh grafov”, Matem. zametki, 107:3 (2020), 351–365  mathnet
  • Математический сборник Sbornik: Mathematics (from 1967)
    Number of views:
    This page:368
    Full text:42
    First page:51

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020