Conflict free colorings of (strongly) almost disjoint set-systems

Abstract

A set-system $X$ is a $(\lambda ,\kappa ,\mu )$-system iff $|X|=\lambda$, $|x|=\kappa$ for each $x\in X$, and $X$ is $\mu$-almost disjoint. We write $[\lambda ,\kappa ,\mu ]->\rho$ iff every $(\lambda ,\kappa ,\mu )$-system has a "conflict free coloring with $\rho$ colors", i.e. there is a coloring of the elements of $\cup X$ with$\rho$ colors such that for each element $x$ of $X$ there is a color $\xi <\rho$ such that exactly one element of $x$ has color $\xi$. Our main object of study is the relation $[\lambda ,\kappa ,\mu ]->\rho$. We give full description of this relation when $\kappa$ is finite. We also show that if $d$ is a natural number then $[\lambda ,\kappa ,d]->\omega$ always holds. Under GCH we prove that $[\lambda ,\kappa ,\omega ]->{\omega }_2$ holds for $\kappa >{\omega }_1$, but the relation $[\lambda ,\kappa ,\omega ]->{\omega }_1$ is independent (modulo some large cardinals).

45 pages

Cited by in corpus (1)

• Elementary submodels in infinite combinatorics