Let \(R(n_1,\ldots,n_c;m)\) be the minimum number of nodes such that any coloring of its \(m\)-subset using \(c\) colors yields a subset of size \(n_i\) all of whose \(m\)-subsets are colored \(i\) for some color \(i\). If all parameters are finite, then so is \(R(n_1,\ldots,n_c;m)\).
===============================================
Proof:
If we have $$|V|=1+R\left(R\left(n_1-1,n_2,\ldots,n_c;m\right),\ldots,R\left(n_1,n_2,\ldots,n_c-1;m\right);m-1\right)$$ nodes, pick an arbitrary vertex \(v\in V\). By induction, for some color \(i\) we have \(S\subset V-v\) of size \(R(n_1,\ldots,n_{i-1},n_i-1,n_{i+1},\ldots,n_c;m-1)\) and all \(m\)-subsets of \(S\cup\{v\}\) containing \(v\) have color \(i\). By definition \(S\) either has a subset of size \(n_k\) with all \(m\)-subsets colored \(k\) for some color\(k\ne i\), or a subset of size \(n_i-1\) with all \(m\)-subsets colored \(i\), which together with \(v\) is what we want.
===============================================
Infinite version
Any $c$-coloring of $m$-subsets of $\mathbb{N}$ yields an infinite subset all of whose \(m\)-subsets have the same color.
Proof:
With similar spirit and by induction on \(m\), fix a \(x_1\in\mathbb{N}\). There is an infinite set \(V_1\subseteq\mathbb{N}-\{x_1\}\) all of whose \((m-1)\)-subsets have color \(c_{1}\), or equivalently, all \(m\)-subsets containing \(x_1\) in \(V_1\cup\{x_1\}\) have color \(c_{1}\). We proceed to \(V_1\) and repeat on an arbitrary $x_2\in V_1$ to get $c_2$ and $V_2\subseteq V_1-\{x_2\}$. Keep going indefinitely, we get infinite sequences \(x=(x_1,x_2,\dots)\) and \(c=(c_1,c_2,\dots)\). A color appears infinite times in \(c\), and its corresponding elements in \(x\) form the desired infinite subset of $\mathbb{N}$.
===============================================
Proof:
If we have $$|V|=1+R\left(R\left(n_1-1,n_2,\ldots,n_c;m\right),\ldots,R\left(n_1,n_2,\ldots,n_c-1;m\right);m-1\right)$$ nodes, pick an arbitrary vertex \(v\in V\). By induction, for some color \(i\) we have \(S\subset V-v\) of size \(R(n_1,\ldots,n_{i-1},n_i-1,n_{i+1},\ldots,n_c;m-1)\) and all \(m\)-subsets of \(S\cup\{v\}\) containing \(v\) have color \(i\). By definition \(S\) either has a subset of size \(n_k\) with all \(m\)-subsets colored \(k\) for some color\(k\ne i\), or a subset of size \(n_i-1\) with all \(m\)-subsets colored \(i\), which together with \(v\) is what we want.
===============================================
Infinite version
Any $c$-coloring of $m$-subsets of $\mathbb{N}$ yields an infinite subset all of whose \(m\)-subsets have the same color.
Proof:
With similar spirit and by induction on \(m\), fix a \(x_1\in\mathbb{N}\). There is an infinite set \(V_1\subseteq\mathbb{N}-\{x_1\}\) all of whose \((m-1)\)-subsets have color \(c_{1}\), or equivalently, all \(m\)-subsets containing \(x_1\) in \(V_1\cup\{x_1\}\) have color \(c_{1}\). We proceed to \(V_1\) and repeat on an arbitrary $x_2\in V_1$ to get $c_2$ and $V_2\subseteq V_1-\{x_2\}$. Keep going indefinitely, we get infinite sequences \(x=(x_1,x_2,\dots)\) and \(c=(c_1,c_2,\dots)\). A color appears infinite times in \(c\), and its corresponding elements in \(x\) form the desired infinite subset of $\mathbb{N}$.
No comments:
Post a Comment