Article
| Title: | On proper colorings of functions (English) |
| Author: | Csernák, Tamás |
| Language: | English |
| Journal: | Commentationes Mathematicae Universitatis Carolinae |
| ISSN: | 0010-2628 (print) |
| ISSN: | 1213-7243 (online) |
| Volume: | 65 |
| Issue: | 2 |
| Year: | 2024 |
| Pages: | 215-238 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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. (English) |
| Keyword: | power of graph |
| Keyword: | $k$-switch problem |
| Keyword: | ultrafilter |
| Keyword: | tight coloring |
| Keyword: | finite independence |
| MSC: | 05C15 |
| MSC: | 05C63 |
| MSC: | 05C76 |
| DOI: | 10.14712/1213-7243.2025.012 |
| . | |
| Date available: | 2025-11-12T14:48:05Z |
| Last updated: | 2025-11-14 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/153170 |
| . | |
| Reference: | [1] Komjáth P., Totik V.: Ultrafilters.Amer. Math. Monthly 115 (2008), no. 1, 33–44. 10.1080/00029890.2008.11920493 |
| Reference: | [2] Greenwell D., Lovász L.: Applications of product colouring.Acta Math. Acad. Sci. Hungar. 25 (1974), 335–340. 10.1007/BF01886093 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
