Geodesic
On algorithmic methods of analysis of two-colorings of hypergraphs
Fundamentalʹnaâ i prikladnaâ matematika, Tome 19 (2014) no. 2, pp. 125-149.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper deals with an extremal problem concerning hypergraph colorings. Let $k$ be an integer. The problem is to find the value $m_k(n)$ equal to the minimum number of edges in an $n$-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains at least $k$ vertices of each color. In this paper, we obtain upper bounds of $m_k(n)$ for small $k$ and $n$, the exact value of $m_4(8)$, and a lower bound for $m_3(7)$. 
@article{FPM_2014_19_2_a6,
     author = {A. V. Lebedeva},
     title = {On algorithmic methods of analysis of two-colorings of hypergraphs},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {125--149},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2014_19_2_a6/}
}
TY  - JOUR
AU  - A. V. Lebedeva
TI  - On algorithmic methods of analysis of two-colorings of hypergraphs
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2014
SP  - 125
EP  - 149
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2014_19_2_a6/
LA  - ru
ID  - FPM_2014_19_2_a6
ER  - 
%0 Journal Article
%A A. V. Lebedeva
%T On algorithmic methods of analysis of two-colorings of hypergraphs
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2014
%P 125-149
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2014_19_2_a6/
%G ru
%F FPM_2014_19_2_a6
A. V. Lebedeva. On algorithmic methods of analysis of two-colorings of hypergraphs. Fundamentalʹnaâ i prikladnaâ matematika, Tome 19 (2014) no. 2, pp. 125-149. http://geodesic.mathdoc.fr/item/FPM_2014_19_2_a6/

[1] Raigorodskii A. M., Shabanov D. A., “Zadacha Erdësha–Khainala o raskraskakh gipergrafov, eë obobscheniya i smezhnye problemy”, Uspekhi mat. nauk, 66:5(401) (2011), 109–182 | DOI | MR | Zbl

[2] Rozovskaya A. P., “O dvukhtsvetnykh raskraskakh obschego vida dlya ravnomernykh gipergrafov”, Dokl. RAN, 429:3 (2009), 309–311 | MR | Zbl

[3] Rozovskaya A. P., Titova M. V., Shabanov D. A., “O polovinnykh raskraskakh gipergrafov”, Fundament. i prikl. mat., 15:7 (2009), 141–163 | MR

[4] Teplyakov S. M., “Rekurrentnye verkhnie otsenki v zadache Erdësha–Khainala o raskraske gipergrafa i v eë obobscheniyakh”, Tr. MFTI, 4:1 (2012), 141–150

[5] Teplyakov S. M., “Verkhnyaya otsenka v zadache Erdësha–Khainala o raskraske gipergrafa”, Mat. zametki, 93:1 (2013), 148–151 | DOI | MR | Zbl

[6] Cherkashin D. D., Kulikov A. B., “O dvukhtsvetnykh raskraskakh gipergrafov”, Dokl. RAN, 463:3 (2011), 316–319 | MR

[7] Shabanov D. A., “Ob odnoi kombinatornoi zadache Erdësha”, Dokl. RAN, 396:2 (2004), 166–169 | MR | Zbl

[8] Shabanov D. A., “Ekstremalnye zadachi dlya raskrasok ravnomernykh gipergrafov”, Izv. RAN. Ser. mat., 71:6 (2007), 183–222 | DOI | MR | Zbl

[9] Shabanov D. A., “Randomizirovannye algoritmy raskrasok gipergrafov”, Mat. sb., 199:7 (2008), 139–160 | DOI | MR | Zbl

[10] Abbott H. L., Hanson D., “On a combinatorial problem of Erdős”, Can. Math. Bull., 12 (1969), 823–829 | DOI | MR | Zbl

[11] Abbott H. L., Hare D. R., “Families of 4-sets without property B”, Ars Combinatoria, 60 (2001), 239–245 | MR | Zbl

[12] Abbott H. L., Moser L., “On a combinatorial problem of Erdős and Hajnal”, Can. Math. Bull., 7 (1964), 177–181 | DOI | MR | Zbl

[13] Erdős P., Hajnal A., “On a property of families of sets”, Acta Math. Acad. Sci. Hungar., 12 (1961), 87–123 | MR | Zbl