×

Conflict free colorings of (strongly) almost disjoint set-systems. (English) Zbl 1274.03074

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 \).

MSC:

03E35 Consistency and independence results
03E05 Other combinatorial set theory
PDFBibTeX XMLCite
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.