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

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

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

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 Erdős) in the extremal theory of hypergraphs. According to Erdő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.

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

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

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
\Bibitem{Sha07} \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 \mathnet{http://mi.mathnet.ru/izv612} \crossref{https://doi.org/10.4213/im612} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2378699} \zmath{https://zbmath.org/?q=an:05250403} \elib{http://elibrary.ru/item.asp?id=9602121} \transl \jour Izv. Math. \yr 2007 \vol 71 \issue 6 \pages 1253--1290 \crossref{https://doi.org/10.1070/IM2007v071n06ABEH002388} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000252675200007} \elib{http://elibrary.ru/item.asp?id=13538965} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-38849187142} 

• http://mi.mathnet.ru/eng/izv612
• https://doi.org/10.4213/im612
• http://mi.mathnet.ru/eng/izv/v71/i6/p183

 SHARE:

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
2. Rozovskaya A.P., “On general two-colorings of uniform hypergraphs”, Dokl. Math., 80:3 (2009), 837–839
3. A. P. Rozovskaya, M. V. Titova, D. A. Shabanov, “On balanced colorings of hypergraphs”, J. Math. Sci., 169:5 (2010), 654–670
4. D. A. Shabanov, “The existence of panchromatic colourings for uniform hypergraphs”, Sb. Math., 201:4 (2010), 607–630
5. Shabanov D.A., “On a generalization of Rubin's theorem”, J. Graph Theory, 67:3 (2011), 226–234
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
7. A. P. Rozovskaya, “Combinatorial Extremum Problems for $2$-Colorings of Hypergraphs”, Math. Notes, 90:4 (2011), 571–583
8. A. M. Raigorodskii, D. A. Shabanov, “The Erdős–Hajnal problem of hypergraph colouring, its generalizations, and related problems”, Russian Math. Surveys, 66:5 (2011), 933–1002