Geodesic
Combinatorial Extremum Problems for $2$-Colorings of Hypergraphs
Matematičeskie zametki, Tome 90 (2011) no. 4, pp. 584-598.

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

We consider a generalization of the Erdős–Hajnal classical combinatorial problem. Let $k$ be a positive integer. It is required to find the value of $m_k(n)$ equal to the minimum number of edges of an $n$-uniform hypergraph that does not admit $2$-colorings of the set of its vertices such that each edge of the hypergraph contains exactly $k$ vertices of each color. In the present paper, we obtain a new asymptotic lower bound for $m_k(n)$, which improves the preceding results in a wide range of values of the parameter $k$. We also consider some other generalizations of this problem.
Keywords: $n$-uniform hypergraph, $2$-coloring, asymptotic lower bound. 
@article{MZM_2011_90_4_a7,
     author = {A. P. Rozovskaya},
     title = {Combinatorial {Extremum} {Problems} for $2${-Colorings} of {Hypergraphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {584--598},
     publisher = {mathdoc},
     volume = {90},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2011_90_4_a7/}
}
TY  - JOUR
AU  - A. P. Rozovskaya
TI  - Combinatorial Extremum Problems for $2$-Colorings of Hypergraphs
JO  - Matematičeskie zametki
PY  - 2011
SP  - 584
EP  - 598
VL  - 90
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2011_90_4_a7/
LA  - ru
ID  - MZM_2011_90_4_a7
ER  - 
%0 Journal Article
%A A. P. Rozovskaya
%T Combinatorial Extremum Problems for $2$-Colorings of Hypergraphs
%J Matematičeskie zametki
%D 2011
%P 584-598
%V 90
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2011_90_4_a7/
%G ru
%F MZM_2011_90_4_a7
A. P. Rozovskaya. Combinatorial Extremum Problems for $2$-Colorings of Hypergraphs. Matematičeskie zametki, Tome 90 (2011) no. 4, pp. 584-598. http://geodesic.mathdoc.fr/item/MZM_2011_90_4_a7/

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

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

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

[4] A. V. Kostochka, “Color-critical graphs and hypergraphs with few edges: a survey”, More Sets, Graphs and Numbers, Bolyai Soc. Math. Stud., 15, Springer-Verlag, Berlin, 2006, 175–197 | MR | Zbl

[5] 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

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

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

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

[9] A. Pluhár, “Greedy colorings for uniform hypergraphs”, Random Structures Algorithms, 35:2 (2009), 216–221 | DOI | MR | Zbl

[10] P. Erdős, L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and Finite Sets, v. II, Colloq. Math. Soc. Janos Bolyai, 10, North-Holland, Amsterdam, 1975, 609–627 | MR | Zbl

[11] Z. Szabó, “An application of Lovász Local Lemma – a new lower bound for the van der Waerden number”, Random Structures Algorithms, 1:3 (1990), 343–360 | MR | Zbl

[12] N. Alon, Dzh. Spenser, Veroyatnostnyi metod, Binom. Laboratoriya znanii, M., 2007 | MR | Zbl