Geodesic
New lower bound for the minimal number of edges of simple uniform hypergraph without the property $B_k$
Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 10-37.

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

A hypergraph $H=(V,E)$ has the property $B_k$ if there exists an assignment of two colors to $V$ such that each edge contains at least $k$ vertices of each color. A hypergraph is called simple if every two edges of it have at most one common vertex. We obtain a new lower bound for the minimal number of edges of $n$-uniform simple hypergraph without the property $B_k$.
Keywords: simple hypergraphs, colorings of hypergraphs, property $B$. 
@article{DM_2020_32_4_a1,
     author = {Yu. A. Demidovich},
     title = {New lower bound for the minimal number of edges of simple uniform hypergraph without the property $B_k$},
     journal = {Diskretnaya Matematika},
     pages = {10--37},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_4_a1/}
}
TY  - JOUR
AU  - Yu. A. Demidovich
TI  - New lower bound for the minimal number of edges of simple uniform hypergraph without the property $B_k$
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 10
EP  - 37
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_4_a1/
LA  - ru
ID  - DM_2020_32_4_a1
ER  - 
%0 Journal Article
%A Yu. A. Demidovich
%T New lower bound for the minimal number of edges of simple uniform hypergraph without the property $B_k$
%J Diskretnaya Matematika
%D 2020
%P 10-37
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2020_32_4_a1/
%G ru
%F DM_2020_32_4_a1
Yu. A. Demidovich. New lower bound for the minimal number of edges of simple uniform hypergraph without the property $B_k$. Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 10-37. http://geodesic.mathdoc.fr/item/DM_2020_32_4_a1/

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

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

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

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

[5] Raigorodskii A. M., Shabanov D. A., “The Erd{ő}s-Hajnal problem of hypergraph colouring, its generalizations, and related problems”, Russian Math. Surveys, 66:5 (2011), 933–1002 | DOI | MR | Zbl

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

[7] Cherkashin D., Kozik J., “A note on random greedy coloring of uniform hypergraphs”, Random Struct. Algor., 47:3 (2015), 407–413 | DOI | MR | Zbl

[8] Shabanov D. A., “On one combinatorial problem of Erd{ő}s”, Doklady Mathematics, 69:3 (2004), 359–362 | MR | Zbl

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

[10] Teplyakov S. M., “Verkhnyaya otsenka v zadache Erdesha–Khainala o raskraske gipergrafa”, Matem. zametki, 93:1 (2013), 148–151 | MR | Zbl

[11] Shabanov D. A., “Randomized algorithms for colourings of hypergraphs”, Sb. Math., 199:7 (2008), 1089–1110 | DOI | MR | Zbl

[12] Rozovskaya A. P., “Combinatorial extremum problems for 2-colorings of hypergraphs”, Math. Notes, 90:4 (2011), 571–583 | DOI | MR | Zbl

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

[14] Demidovich Yu.A., “Nekotorye obobscheniya zadachi o svoistve $B$ $n$-odnorodnogo gipergrafa”, Fundam. i prikl. matem., 23:1 (2020), 95–122 | MR

[15] Erd{ő}s P., Lovász L., “Problems and results on 3-chromatic hypergraphs and some related questions”, Colloq. Math. Soc. Janos. Bolyai, 10 (1973), 609–627 | MR

[16] Kupavskii A., Shabanov D., “Colourings of uniform hypergraphs with large girth and applications”, Comb., Probab. and Comput., 27:2 (2018), 245–273 | DOI | MR | Zbl

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

[18] Kostochka A. V., Kumbhat M., “Coloring uniform hypergraphs with few edges”, Random Struct. Algor., 35:3 (2009), 348–368 | DOI | MR | Zbl

[19] Kozik J., Shabanov D., “Improved algorithms for colorings of simple hypergraphs and applications”, J. Comb. Theory, Ser. B, 116 (2016), 312–332 | DOI | MR | Zbl

[20] Kostochka A.V., R{ő}dl V., “Constructions of sparse uniform hypergraphs with high chromatic number”, Random Struct. Algor., 36:1 (2010), 46–56 | DOI | MR | Zbl

[21] Demidovich Yu. A., Raigorodskii A. M., “2-Colorings of uniform hypergraphs”, Math. Notes, 100:4 (2016), 629–632 | DOI | MR | Zbl

[22] Demidovich Yu. A., “2-Colorings of hypergraphs with large girth”, Math. Notes, 108:2 (2020), 188–200 | DOI | MR | Zbl

[23] Semenov A., Shabanov D., “On the weak chromatic number of random hypergraph”, Discr. Appl. Math., 276 (2020), 134–154 | DOI | MR | Zbl

[24] Akhmejanova M., Shabanov D., “Coloring hypergraphs with bounded cardinalities of edge intersections”, Discrete Mathematics, 343:4 (2020), 1–11 | DOI | MR

[25] Semenov A. S., “Two-colorings of a random hypergraph”, Theory Probab. Appl., 64:1 (2019), 59–77 | DOI | MR | Zbl

[26] Cherkashin D., Petrov F., “On small $n$-uniform hypergraphs with positive discrepancy”, J. Comb. Theory, Ser. B, 139 (2019), 353–359 | DOI | MR | Zbl

[27] Ayre P., Coja-Oghlan A., Greenhill C., “Hypergraph coloring up to condensation”, Random Struct. Algor., 54:4 (2019), 615–652 | DOI | MR | Zbl

[28] Duraj L., Gutowski G., Kozik J., “A note on two-colorability of nonuniform hypergraphs”, 45th Int. Colloq. Automata, Languages, and Programm. (ICALP 2018), Leibniz Int. Proc. in Informatics, 107, Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2018, 46:1–46:13 http://drops.dagstuhl.de/opus/volltexte/2018/9050 | MR

[29] Dyer M., Frieze A., Greenhill C., “On the chromatic number of a random hypergraph”, J. Comb. Theory, Ser. B, 113 (2015), 68–122 | DOI | MR | Zbl

[30] Balogh J., Cherkashin D., Kiselev S., “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, Europ. J. Combin., 79 (2019), 228–236 | DOI | MR | Zbl

[31] Raigorodskii A. M., Cherkashin D. D., “Extremal problems in hypergraph colourings”, Russian Math. Surveys, 75:1 (2020), 89–146 | DOI | MR | Zbl