Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
power of graph; $k$-switch problem; ultrafilter; tight coloring; finite independence
power of graph; $k$-switch problem; ultrafilter; tight coloring; finite independence
Summary:
We investigate the infinite version of the $k$-switch problem of D. Greenwell and L. Lovász. A function $F\colon ^{\lambda}\kappa \to \kappa $ is a proper coloring if $F(x)\ne F(y)$ whenever $x$ and $y$ are totally different elements of $^{\lambda} \kappa $, i.e. $x(i)\ne y(i)$ for each $i\in \lambda$. We call $F$ (i) weakly uniform if and only if there are pairwise totally different $\{{r_{\alpha}:} \alpha<\kappa\}\subset ^{\lambda}\kappa$ with $F(r_{\alpha})=\alpha$; (ii) tight if no proper coloring $G\colon ^{\lambda}\kappa \to \kappa$ differs from $F$ at exactly one point. We prove that a proper coloring $F\colon ^{\lambda}\kappa\to \kappa$ is weakly uniform if and only if there is a ${\kappa}^{+}$-complete ultrafilter $\mathscr{U}$ on $\lambda$ and there is a permutation $\pi\in {\rm Sym}(\kappa)$ such that for each $x\in ^{\lambda}\kappa$, $$ F(x)=\pi(\alpha) \Leftrightarrow \{i\in \lambda\colon x(i)=\alpha\} \in \mathscr{U}. $$ We also show that there are tight proper colorings which cannot be obtained in this way.
References:
[1] Komjáth P., Totik V.: Ultrafilters. Amer. Math. Monthly 115 (2008), no. 1, 33–44. DOI 10.1080/00029890.2008.11920493
[2] Greenwell D., Lovász L.: Applications of product colouring. Acta Math. Acad. Sci. Hungar. 25 (1974), 335–340. DOI 10.1007/BF01886093
Search
Partner of
