Skip to main content
added 225 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases} $$ The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.

Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases} $$

Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases} $$ The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.

added 225 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases} $$

Let $U = [m]$, and let $h$ be the identity function.

Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases} $$

Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Let $U = [m]$, and let $h$ be the identity function.