On small non-uniform hypergraphs without property B
DOI:
https://doi.org/10.55630/mem.2023.52.71-75Keywords:
non-uniform hypergraphs, hypergraph colouring, property BAbstract
For a given hypergraph H = (V, E) consider the sum q(H) of 2^{−|e|} over e ∈ E. Consider the class of hypergraphs whose smallest edge is of size n and for which every 2-colouring has a monochromatic edge. Let q(n) be the smallest value of q(H) in this class. We provide a survey of the known bounds on q(n) and make some minor refinements.
References
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.
