Conflict free colorings of (strongly) almost disjoint set-systems |
| |
Authors: | András Hajnal István Juhász Lajos Soukup Zoltán Szentmiklóssy |
| |
Institution: | 1.Alfréd Rényi Institute of Mathematics,Budapest,Hungary;2.E?tv?s Loránd University,Budapest,Hungary |
| |
Abstract: | \(f\: \cup {\mathcal {A}}\to {\rho}\) is called a conflict free coloring of the set-system\({\mathcal {A}}\)(withρcolors) if $\forall A\in {\mathcal {A}}\ \exists\, {\zeta}<{\rho} (|A\cap f^{-1}\{{\zeta}\}|=1).$ The conflict free chromatic number\(\operatorname {\chi _{\rm CF}}\, ({\mathcal {A}})\) of \({\mathcal {A}}\) is the smallest ρ for which \({\mathcal {A}}\) admits a conflict free coloring with ρ colors. \({\mathcal {A}}\) is a ( λ, κ, μ)-system if \(|{\mathcal {A}}| = \lambda\), | A|= κ for all \(A \in {\mathcal {A}}\), and \({\mathcal {A}}\) is μ-almost disjoint, i.e. | A∩ A′|< μ for distinct \(A, A'\in {\mathcal {A}}\). Our aim here is to study $\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,\mu) = \sup \{\operatorname {\chi _{\rm CF}}\, ({\mathcal {A}})\: {\mathcal {A}}\mbox{ is a } (\lambda,\kappa,\mu)\mbox{-system}\}$ for λ≧ κ≧ μ, actually restricting ourselves to λ≧ ω and μ≦ ω. For instance, we prove that? for any limit cardinal κ (or κ= ω) and integers n≧0, k>0, GCH implies $\operatorname {\chi _{\rm CF}}\, (\kappa^{+n},t,k+1) =\begin{cases}\kappa^{+(n+1-i)}&; \text{if \ } i\cdot k < t \le (i+1)\cdot k,\ i =1,\dots,n;\\2pt]\kappa&; \text{if \ } (n+1)\cdot k < t;\end{cases}$ ? if λ≧κ≧ω>d>1, then λ<κ +ω implies \(\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,d) <\omega\) and λ≧? ω (κ) implies \(\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,d) = \omega\);? GCH implies \(\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,\omega) \le \omega_{2}\) for λ≧κ≧ω 2 and V=L implies \(\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,\omega) \le \omega_{1}\) for λ≧κ≧ω 1;? the existence of a supercompact cardinal implies the consistency of GCH plus \(\operatorname {\chi _{\rm CF}}\,(\aleph_{\omega+1},\omega_{1},\omega)= \aleph_{\omega+1}\) and \(\operatorname {\chi _{\rm CF}}\, (\aleph_{\omega+1},\omega_{n},\omega) = \omega_{2}\) for 2≦n≦ω;? CH implies \(\operatorname {\chi _{\rm CF}}\, (\omega_{1},\omega,\omega) = \operatorname {\chi _{\rm CF}}\, (\omega_{1},\omega_{1},\omega) = \omega_{1}\), while \(MA_{\omega_{1}}\) implies \(\operatorname {\chi _{\rm CF}}\, (\omega_{1},\omega,\omega) = \operatorname {\chi _{\rm CF}}\, (\omega_{1},\omega_{1},\omega) = \omega\). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|