RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

This article is cited in 18 scientific papers (total in 18 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
НШ-2964.2014.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

DOI: https://doi.org/10.4213/sm8473

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
\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 Mat. Sb.
\yr 2016
\vol 207
\issue 5
\pages 17--42
\mathnet{http://mi.mathnet.ru/msb8473}
\crossref{https://doi.org/10.4213/sm8473}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3507497}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2016SbMat.207..652B}
\elib{https://elibrary.ru/item.asp?id=26414394}
\transl
\jour Sb. Math.
\yr 2016
\vol 207
\issue 5
\pages 652--677
\crossref{https://doi.org/10.1070/SM8473}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000380765400002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84979675840}


Linking options:
  • http://mi.mathnet.ru/eng/msb8473
  • https://doi.org/10.4213/sm8473
  • http://mi.mathnet.ru/eng/msb/v207/i5/p17

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathscinet  zmath  isi
    14. A. A. Sagdeev, “On a Frankl–Wilson Theorem”, Problems Inform. Transmission, 55:4 (2019), 376–395  mathnet  crossref  crossref  isi  elib
    15. Sagdeev A.A., Raigorodskii A.M., “On a Frankl-Wilson Theorem and Its Geometric Corollaries”, Acta Math. Univ. Comen., 88:3 (2019), 1029–1033  mathscinet  isi
    16. D. A. Zakharov, “Chromatic Numbers of Some Distance Graphs”, Math. Notes, 107:2 (2020), 238–246  mathnet  crossref  crossref  isi  elib
    17. 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  mathnet  crossref  crossref  isi  elib
    18. A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “A Generalization of Kneser Graphs”, Math. Notes, 107:3 (2020), 392–403  mathnet  crossref  crossref  isi
  • Математический сборник Sbornik: Mathematics (from 1967)
    Number of views:
    This page:390
    Full text:59
    References:49
    First page:51

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