Hajnal, A.; Juhász, I.; Soukup, L.; Szentmiklóssy, Z. Conflict free colorings of (strongly) almost disjoint set-systems. (English) Zbl 1274.03074 Acta Math. Hung. 131, No. 3, 230-274 (2011). Summary: \(f :\bigcup\mathcal A\to \rho\) is called a conflict-free coloring of the set-system \(\mathcal A\) (with \(\rho\) colors) if \[ \forall A\in \mathcal A\; \exists \zeta < \rho\;(| A \cap f^{-1}\{\zeta\}| = 1). \] The conflict-free chromatic number \(\chi_{\text{CF}} (\mathcal A)\) of \(\mathcal A\) is the smallest \(\rho\) for which \(\mathcal A\) admits a conflict-free coloring with \(\rho\) colors. \(\mathcal A\) is a \((\lambda,\kappa,\mu)\)-system if \(| \mathcal A| =\lambda \), \(| A| =\kappa\) for all \(A \in \mathcal A\), and \(\mathcal A\) is \(\mu\)-almost disjoint, i.e., \(| A\cap A'| < \mu\) for distinct \(A,A' \in\mathcal A\). Our aim here is to study \[ \chi_ {\text{CF}} (\lambda,\kappa,\mu)= \sup\{\chi_ {\text{CF}} (\mathcal A) : \mathcal A\;\text{is a}\;(\lambda,\kappa,\mu)\text{-system}\} \] for \(\lambda \geqq \kappa \geqq \mu\), actually restricting ourselves to \(\lambda \geqq \omega\) and \(\mu \leqq \omega\). For instance, we prove that \(\bullet\) for any limit cardinal \(\kappa\) (or \(\kappa =\omega )\) and integers \(n \geqq 0\), \(k > 0\), GCH implies \[ \chi_ {\text{CF}} (\kappa^{+n}, t, k + 1) =\begin{cases} \kappa^{+(n+1-i)} & \text{if}\;i\cdot k < t \leqq (i + 1) \cdot k,\;i = 1,\dots, n; \\ \kappa & \text{if}\;(n + 1)\cdot k < t; \end{cases} \] \(\bullet\) if \(\lambda \geqq \kappa \geqq \omega > d>1\), then \(\lambda < \kappa^{+\omega}\) implies \(\chi_ {\text{CF}} (\lambda,\kappa , d) < \omega\) and \(\lambda \geqq \gimel_ \omega (\kappa )\) implies \(\chi_ {\text{CF}} (\lambda,\kappa , d) = \omega\); \(\bullet\) GCH implies \(\chi_ {\text{CF}} (\lambda,\kappa ,\omega)\leqq \omega_ 2\) for \(\lambda \geqq \kappa \geqq\omega_ 2\) and \(V = L\) implies \(\chi_ {\text{CF}} (\lambda,\kappa ,\omega)\leqq \omega_ 1\) for \(\lambda \geqq \kappa \geqq \omega_ 1\); \(\bullet\) the existence of a supercompact cardinal implies the consistency of GCH plus \(\chi_{\text{CF}}(\aleph_{\omega +1}, \omega_ 1, \omega ) =\aleph_ {\omega +1}\) and \(\chi_ {\text{CF}} (\aleph_ {\omega +1}, \omega_ n, \omega ) = \omega_ 2\) for \(2\leqq n\leqq \omega\); \(\bullet\) CH implies \(\chi_ {\text{CF}}(\omega_ 1, \omega,\omega) = \chi_ {\text{CF}}(\omega_ 1, \omega_ 1, \omega ) = \omega_ 1\), while \(\mathrm{MA}_ {\omega_ 1}\) implies \(\chi_ {\text{CF}} (\omega_ 1, \omega , \omega ) = \chi_ {\text{CF}} (\omega_ 1, \omega_ 1, \omega ) = \omega \). Cited in 1 ReviewCited in 5 Documents MSC: 03E35 Consistency and independence results 03E05 Other combinatorial set theory Keywords:conflict-free coloring; almost disjoint sets; essentially disjoint sets PDFBibTeX XMLCite \textit{A. Hajnal} et al., Acta Math. Hung. 131, No. 3, 230--274 (2011; Zbl 1274.03074) Full Text: DOI arXiv References: [1] P. Cheilaris, Conflict-Free Coloring, PhD thesis, City University of New York (2008). · Zbl 1445.68357 [2] P. Erdos, F. Galvin and A. Hajnal, On set-systems having large chromatic number and not containing prescribed subsystems, in: Infinite and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erdos on his 60th birthday, Vol. I). Colloq. Math. Soc. János Bolyai, 10, North-Holland (Amsterdam, 1975), pp. 425–513. [3] P. Erdos and A. Hajnal, On a property of families of sets, Acta Math. Acad. Sci. Hung., 12 (1961), 87–124. · Zbl 0201.32801 [4] P. Erdos and A. Hajnal, On the chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hung., 17 (1966), 159–229. · Zbl 0151.33702 [5] P. Erdos, A. Hajnal and B. Rothchild, On chromatic numbers of graphs and set-systems, in: Proceedings of the 1971 Cambridge Summer School. Springer Lecture Notes in Math., 337 (1971), pp. 531–538. [6] G. Even, Z. Lotker, D. Ron and S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellural networks, SIAM J. Comput., 33 (2003), 94–136. · Zbl 1069.68120 [7] A. Hajnal, I. Juhász and S. Shelah, Splitting strongly almost disjoint families, Trans. Amer. Math. Soc., 295 (1986), 369–387. · Zbl 0619.03033 [8] A. Hajnal, I. Juhász and S. Shelah, Strongly almost disjoint families, revisited, Fund. Math., 163 (2000), 13–23. · Zbl 0946.03057 [9] P. Komjáth, Dense systems of almost-disjoint sets, in: Finite and Infinite Sets (Eger, 1981). Coll Math Soc. J. Bolyai, 10 (1984), pp. 527–536. [10] P. Komjáth, Families close to disjoint ones, Acta Math. Hungar., 43 (1984), 199–207. · Zbl 0541.03027 [11] K. Kunen, Set Theory, North-Holland (New York, 1980). [12] E. W. Miller, On a property of families of sets, Comptes Rendus Varsovie, 30 (1937), 31–38. · Zbl 0017.30003 [13] J. Pach and G. Tardos, Conflict-free colourings of graphs and hypergraphs, Combin. Probab. Comput., 18 (2009), 819–834. · Zbl 1197.05054 [14] S. Shelah, Diamonds, preprint of paper #922, arXiv:0711.3030 . [15] P. J. Szeptycki, Transversals for strongly almost disjoint families, Proc. Amer. Math. Soc., 135 (2007), 2273–2282. · Zbl 1118.03040 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.