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

Izv. RAN. Ser. Mat.:

Personal entry:
Save password
Forgotten password?

Izv. RAN. Ser. Mat., 2007, Volume 71, Issue 6, Pages 183–222 (Mi izv612)  

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

Extremal problems for colourings of uniform hypergraphs

D. A. Shabanov

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: We study a classical problem (first posed by Erdős) in the extremal theory of hypergraphs. According to Erdős, a hypergraph possesses property $B$ if its set of vertices admits a 2-colouring such that no edge of the hypergraph is monochromatic. The problem is to find the minimum $m(n)$ of all $m$ such that there is an $n$-uniform (each edge contains exactly $n$ vertices) hypergraph with exactly $m$ edges that does not possess property $B$. We consider more general problems (including the case of polychromatic colourings) and introduce a number of parametric properties of hypergraphs. We obtain estimates for analogues of $m(n)$ for extremal problems on various classes of hypergraphs.


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

English version:
Izvestiya: Mathematics, 2007, 71:6, 1253–1290

Bibliographic databases:

UDC: 519.179.1
MSC: 05C15, 05C65, 05D05, 05C80
Received: 11.10.2005

Citation: D. A. Shabanov, “Extremal problems for colourings of uniform hypergraphs”, Izv. RAN. Ser. Mat., 71:6 (2007), 183–222; Izv. Math., 71:6 (2007), 1253–1290

Citation in format AMSBIB
\by D.~A.~Shabanov
\paper Extremal problems for colourings of uniform hypergraphs
\jour Izv. RAN. Ser. Mat.
\yr 2007
\vol 71
\issue 6
\pages 183--222
\jour Izv. Math.
\yr 2007
\vol 71
\issue 6
\pages 1253--1290

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. D. A. Shabanov, “Randomized algorithms for colourings of hypergraphs”, Sb. Math., 199:7 (2008), 1089–1110  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    2. Rozovskaya A.P., “On general two-colorings of uniform hypergraphs”, Dokl. Math., 80:3 (2009), 837–839  mathnet  crossref  mathscinet  zmath  isi  elib  elib  scopus
    3. A. P. Rozovskaya, M. V. Titova, D. A. Shabanov, “On balanced colorings of hypergraphs”, J. Math. Sci., 169:5 (2010), 654–670  mathnet  crossref  mathscinet  elib  elib
    4. D. A. Shabanov, “The existence of panchromatic colourings for uniform hypergraphs”, Sb. Math., 201:4 (2010), 607–630  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    5. Shabanov D.A., “On a generalization of Rubin's theorem”, J. Graph Theory, 67:3 (2011), 226–234  crossref  mathscinet  zmath  isi  elib  scopus
    6. A. P. Rozovskaya, D. A. Shabanov, “Improvement of the Lower Bound in the Kostochka Problem of Panchromatic Coloring of a Hypergraph”, Math. Notes, 89:6 (2011), 903–906  mathnet  crossref  crossref  mathscinet  isi
    7. A. P. Rozovskaya, “Combinatorial Extremum Problems for $2$-Colorings of Hypergraphs”, Math. Notes, 90:4 (2011), 571–583  mathnet  crossref  crossref  mathscinet  isi
    8. A. M. Raigorodskii, D. A. Shabanov, “The Erdős–Hajnal problem of hypergraph colouring, its generalizations, and related problems”, Russian Math. Surveys, 66:5 (2011), 933–1002  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    9. Cherkashin D.D., Kulikov A.B., “O dvukhtsvetnykh raskraskakh gipergrafov”, Doklady Akademii nauk, 436:3 (2011), 316–319  mathscinet  zmath  elib
    10. A. P. Rozovskaya, D. A. Shabanov, “Extremal problems for panchromatic colourings of uniform hypergraphs”, Discrete Math. Appl., 22:2 (2012), 185–206  mathnet  crossref  crossref  mathscinet  elib  elib
    11. S. M. Teplyakov, “Upper Bound in the Erdős–Hajnal Problem of Hypergraph Coloring”, Math. Notes, 93:1 (2013), 191–195  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  elib
    12. A. V. Lebedeva, “On algorithmic methods of analysis of two-colorings of hypergraphs”, J. Math. Sci., 213:2 (2016), 211–229  mathnet  crossref  mathscinet
    13. Yu. A. Demidovich, A. M. Raigorodskii, “2-Colorings of Uniform Hypergraphs”, Math. Notes, 100:4 (2016), 629–632  mathnet  crossref  crossref  mathscinet  isi  elib
  • Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Number of views:
    This page:778
    Full text:138
    First page:11

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