Abstract:
Generalizations of the classical problem of Erdős on property B of hypergraphs are studied. According to the definition of Erdős, a hypergraph has property B if there exists a 2-colouring of its vertex set in which none of the edges of the hypergraph is monochromatic. It is required to find the quantity m(n) that is equal to the minimal possible number of edges in an n-uniform (each edge contains exactly n
vertices) hypergraph that does not have property B. More general settings of the problem are considered, several parametric properties of hypergraphs are introduced, and the corresponding extremal quantities are studied. The main results improve the lower estimates of these extremal quantities that were known
earlier.
Bibliography: 9 titles.
\Bibitem{Sha08}
\by D.~A.~Shabanov
\paper Randomized algorithms for colourings of hypergraphs
\jour Sb. Math.
\yr 2008
\vol 199
\issue 7
\pages 1089--1110
\mathnet{http://mi.mathnet.ru/eng/sm3931}
\crossref{https://doi.org/10.1070/SM2008v199n07ABEH003955}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2488227}
\zmath{https://zbmath.org/?q=an:1257.05046}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000260697900008}
\elib{https://elibrary.ru/item.asp?id=20425546}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-57049129429}
Linking options:
https://www.mathnet.ru/eng/sm3931
https://doi.org/10.1070/SM2008v199n07ABEH003955
https://www.mathnet.ru/eng/sm/v199/i7/p139
This publication is cited in the following 11 articles:
A. M. Raigorodskii, D. D. Cherkashin, “Extremal problems in hypergraph colourings”, Russian Math. Surveys, 75:1 (2020), 89–146
Yu. A. Demidovich, “2-Colorings of Hypergraphs with Large Girth”, Math. Notes, 108:2 (2020), 188–200
Yu. A. Demidovich, “New lower bound for the minimal number of edges of simple uniform hypergraph without the property BkBk”, Discrete Math. Appl., 32:3 (2022), 155–176
Yu. A. Demidovich, “On some generalizations of the property B problem of an nn-uniform hypergraph”, J. Math. Sci., 262:4 (2022), 457–475
Yu. A. Demidovich, A. M. Raigorodskii, “2-Colorings of Uniform Hypergraphs”, Math. Notes, 100:4 (2016), 629–632
A. V. Lebedeva, “On algorithmic methods of analysis of two-colorings of hypergraphs”, J. Math. Sci., 213:2 (2016), 211–229
S. M. Teplyakov, “Upper Bound in the Erdős–Hajnal Problem of Hypergraph Coloring”, Math. Notes, 93:1 (2013), 191–195
Citation in format AMSBIB
Contact us: