Малки неравномерни хиперграфи без свойство B

Автори

  • Данила Черкашин Институт по математика и информатика към Българска академия на науките https://orcid.org/0000-0002-8716-9794

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) и правим някои малки подобрения.

Авторска биография

Автор: Данила Черкашин, Институт по математика и информатика към Българска академия на науките

Данила Черкашин
Институт по математика и информатика
Българска академия на науките
ул. "Акад. Г. Бончев", блок 8
1113 София, България
e-mail: jiocb@math.bas.bg

Литература (библиография)

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.

Файлове за сваляне

Публикуван

01.04.2023

Как да цитирате

[1]
Черкашин, Д. 2023. Малки неравномерни хиперграфи без свойство B. Математика и математическо образование. 52, (Апр 2023), 71–75. DOI:https://doi.org/10.55630/mem.2023.52.71-75.

Брой

Раздел (Секция)

Доклади по покана

Най-четените статии от същия автор(и)