Geodesic
Randomized algorithms for colourings of hypergraphs
Sbornik. Mathematics, Tome 199 (2008) no. 7, pp. 1089-1110 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{SM_2008_199_7_a7,
     author = {D. A. Shabanov},
     title = {Randomized algorithms for colourings of hypergraphs},
     journal = {Sbornik. Mathematics},
     pages = {1089--1110},
     year = {2008},
     volume = {199},
     number = {7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2008_199_7_a7/}
}
TY  - JOUR
AU  - D. A. Shabanov
TI  - Randomized algorithms for colourings of hypergraphs
JO  - Sbornik. Mathematics
PY  - 2008
SP  - 1089
EP  - 1110
VL  - 199
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/SM_2008_199_7_a7/
LA  - en
ID  - SM_2008_199_7_a7
ER  - 
%0 Journal Article
%A D. A. Shabanov
%T Randomized algorithms for colourings of hypergraphs
%J Sbornik. Mathematics
%D 2008
%P 1089-1110
%V 199
%N 7
%U http://geodesic.mathdoc.fr/item/SM_2008_199_7_a7/
%G en
%F SM_2008_199_7_a7
D. A. Shabanov. Randomized algorithms for colourings of hypergraphs. Sbornik. Mathematics, Tome 199 (2008) no. 7, pp. 1089-1110. http://geodesic.mathdoc.fr/item/SM_2008_199_7_a7/

[1] P. Erdős, “On a combinatorial problem”, Nordisk Mat. Tidskr., 11 (1963), 5–10 | MR | Zbl

[2] P. Erdős, “On a combinatorial problem. II”, Acta Math. Acad. Sci. Hungar, 15:3–4 (1964), 445–447 | DOI | MR | Zbl

[3] J. Beck, “On 3-chromatic hypergraphs”, Discrete Math., 24:2 (1978), 127–137 | DOI | MR | Zbl

[4] J. Radhakrishnan, A. Srinivasan, “Improved bounds and algorithms for hypergraph 2-coloring”, Random Structures Algorithms, 16:1 (2000), 4–32 | 3.0.CO;2-2 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[5] D. A. Shabanov, “On one combinatorial problem of Erdős”, Russian Acad. Sci. Dokl. Math., 69:3 (2004), 359–362 | MR | Zbl

[6] D. A. Shabanov, “On colorings of hypergraphs”, Russian Acad. Sci. Dokl. Math., 71:3 (2005), 438–442 | MR

[7] D. A. Shabanov, “On the vertex number of almost bipartite hypergraphs”, Russian Acad. Sci. Dokl. Math., 75:1 (2007), 25–27 | DOI

[8] D. A. Shabanov, “Extremal problems for colourings of uniform hypergraphs”, Izv. Math., 71:6 (2007), 1253–1290 | DOI | MR | Zbl

[9] W. Feller, An introduction to probability theory and its applications, vol. I, Wiley, New York–London–Sydney, 1968 | MR | MR | Zbl | Zbl