Малки неравномерни хиперграфи без свойство B
DOI :
https://doi.org/10.55630/mem.2023.52.71-75Ключови думи :
неравномерни хиперграфи, оцветяване на хиперграфи, свойство BАбстракт
За даден хиперграф H = (V, E) нека да разгледаме сумата q(H) на 2^{−|e|} върху e ∈ E. Разглеждаме класа хиперграфи, чието най-малко ребро е с тегло n и за които всяко 2-оцветяване има едноцветно ребро. Нека q(n) е най-малката стойност на q(H) в този клас. Представяме преглед на известните граници на q(n) и правим някои малки подобрения.
Литература (библиография)
S. Aglave, V. A. Amarnath, S. Shannigrahi, S. Singh. Improved bounds for uniform hypergraphs without property B. Australas. J Combin., 76, part 1 (2020), 73–86.
M. Akhmejanova. Biuniform hypergraph coloring. Trudy MFTI, 13, no. 3 (2021), 23–27.
J. Beck. A remark concerning arithmetic progressions. J. Combin. Theory Ser. A, 29, no. 3 (1980), 376–379.
D. D. Cherkashin, J. Kozik. A note on random greedy coloring of uniform hypergraphs. Random Structures Algorithms, 47, no. 3 (2015), 407–413.
L. Duraj, G. Gutowski, J. Kozik. A note on two-colorability of nonuniform hypergraphs. 45th International Colloquium on Automata, Languages, and Programming, Art. No. 46, 13 pp., LIPIcs. Leibniz Int. Proc. Inform., 107. Wadern, Schloss Dagstuhl. Leibniz-Zent. Inform., 2018.
P. Erdos. On a combinatorial problem. Nordisk Mat. Tidskr., 11 (1963), 5–10.
P. Erdos. On a combinatorial problem, II. Acta Math. Acad. Sci. Hungar., 15, no. 3–4 (1964), 445–447.
L. Lu. On a problem of Erd˝os and Lov´asz on coloring non-uniform hypergraphs. Preprint, 2008, www.math.sc.edu/~lu/papers/propertyB.pdf.
P. R. J. Ostergard. On the minimum size of 4-uniform hypergraphs without property B. Discrete Appl. Math., 163, part 2 (2014), 199–204.
J. Radhakrishnan, A. Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures Algorithms, 16, no. 1 (2000), 4–32.
J. Radhakrishnan, A. Srinivasan. Property B: Two-coloring non-uniform hypergraphs. In: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), 2021, 31:1–31:8, DOI 10.4230/LIPIcs.FSTTCS.2021.31.
Andrei Mikhailovich Raigorodskii and Danila Dmitrievich Cherkashin. Extremal problems in hypergraph colourings. Uspekhi Mat. Nauk 75, no. 1(451) (2020), 95–154 (in Russian); English translation in Russian Math. Surveys 75, no. 1 (2020), 89–146.
P. D. Seymour. A note on a combinatorial problem of Erd˝os and Hajnal. J. London Math. Soc. (2), 8 (1974) 681–682.
D. A. Shabanov. Coloring non-uniform hypergraphs without short cycles. Graphs Combin., 30, no. 5 (2014), 1249–1260.
Dmitry A. Shabanov. Around Erd˝os–Lov´asz problem on colorings of non-uniform hypergraphs. Discrete Mathem., 338, no. 11 (2015), 1976–1981.
B. Toft. On color critical hypergraphs. In: Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday), Vols. I, II, III, 1445–1457. Colloq. Math. Soc. Janos Bolyai, Vol. 10, Amsterdam, North-Holland, 1975.