On Proper Colorings of Functions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909556384202752 |
|---|---|
| author | Csernák, Tamás |
| author_facet | Csernák, Tamás |
| contents | We investigate the infinite version of the $k$-switch problem of Greenwell and Lovász.
Given infinite cardinals $κ$ and $λ$, for functions $x,y\in {}^λκ$ we say that they are totally different if $x(i)\ne y(i)$ for each $i\in λ$. A function $F:{}^λκ\longrightarrow κ $ is a proper coloring if $F(x)\ne F(y)$ whenever $x$ and $y$ are totally different elements of ${}^λκ $.
We say that $F$ is weakly uniform iff there are pairwise totally different functions $\{r_α:α<κ\}\subset {}^λκ$ such that $F(r_α)=α$;
$F$ is tight if there is no proper coloring $G:{}^λκ\longrightarrow κ$ such that there is exactly one $x\in {}^λκ$ with $G(x)\ne F(x)$.
We show that given a proper coloring $F:{}^λκ\to κ$, the following statements are equivalent $F$ is weakly uniform, there is a $κ ^{+}$-complete ultrafilter $\mathscr{U}$ on $λ$ and there is a permutation $π\in Symm(κ)$ such that for each $x\in {}^λκ$ we have
$$F(x)=π(α)\ \Longleftrightarrow \ \{i\in λ: x(i)=α\} \in \mathscr{U}.$$
We also show that there are tight proper colorings which cannot be obtained such a way. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_10654 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On Proper Colorings of Functions Csernák, Tamás Combinatorics 05C76, 05C63, 05C15 We investigate the infinite version of the $k$-switch problem of Greenwell and Lovász. Given infinite cardinals $κ$ and $λ$, for functions $x,y\in {}^λκ$ we say that they are totally different if $x(i)\ne y(i)$ for each $i\in λ$. A function $F:{}^λκ\longrightarrow κ $ is a proper coloring if $F(x)\ne F(y)$ whenever $x$ and $y$ are totally different elements of ${}^λκ $. We say that $F$ is weakly uniform iff there are pairwise totally different functions $\{r_α:α<κ\}\subset {}^λκ$ such that $F(r_α)=α$; $F$ is tight if there is no proper coloring $G:{}^λκ\longrightarrow κ$ such that there is exactly one $x\in {}^λκ$ with $G(x)\ne F(x)$. We show that given a proper coloring $F:{}^λκ\to κ$, the following statements are equivalent $F$ is weakly uniform, there is a $κ ^{+}$-complete ultrafilter $\mathscr{U}$ on $λ$ and there is a permutation $π\in Symm(κ)$ such that for each $x\in {}^λκ$ we have $$F(x)=π(α)\ \Longleftrightarrow \ \{i\in λ: x(i)=α\} \in \mathscr{U}.$$ We also show that there are tight proper colorings which cannot be obtained such a way. |
| title | On Proper Colorings of Functions |
| topic | Combinatorics 05C76, 05C63, 05C15 |
| url | https://arxiv.org/abs/2211.10654 |