Transversal of $\mathbb{N}\times\mathbb{N}$

Question

Motivation. I am trying to make an interesting infinite version out of this fascinating problem from the Russian mathematical olympiad:

There are $c$ flavours of cookies, we are given $n$ cookies of each flavour. The $c\cdot n$ cookies are put into $c$ boxes, each box containing $n$ cookies. Prove that we can select one cookie from each box such that the selection contains a cookie from each flavour.

Let $f:(\newcommand{\N}{\mathbb{N}}\N\times\N)\to \N$ be a map with the following properties:

1. For all $n\neq n'\in \N$ we have $\{f(n,k):k\in \N\}\neq \{f(n',k):k\in\N\}$, and

2. For all $n\in\N$ the set $L_n := \big\{i\in\N: \big(\{i\} \times \N\big) \cap f^{-1}(\{n\}) \text{ is infinite}\big\}$ is infinite.

If $c:\N\to\N$ is a map, the transversal map of $c$ with respect to $f$ is defined by $t_{(f,c)}(n) = f\big(n, c(n)\big)$ for all $n\in \N$.

Question. If $f:\N\to\N$ has the property defined above, is there a map $c:\N\to\N$ such that $t_{(f,c)}$ is a bijection?

Answer 1

Counterexample. Let $\mathbb N=\{0,1,2,\dots\}$. Define $f(0,k)=0$, $f(1,k)=1$, and $f(n,k)=k\operatorname{mod}n$ for $n\ge2$. Your conditions are satisfied, and a transversal map $t=t_{(f,c)}$ can't be injective since $t(0)=0$, $t(1)=1$, and $t(2)\in\{0,1\}$.

The nicest generalization of that "Russian olympiad problem" that I know of is this classical theorem of D. Kőnig:

Theorem. If $n$ is a positive integer, then every $n$-regular bipartite multigraph (finite or infinite) has a perfect matching. (And so it has a $1$-factorization.)

In the olympiad problem, the vertices are "boxes" and "flavours", and each "cookie" is an edge joining a "box" to a "flavour". There may be multiple edges, as a box may contain several cookies of the same flavour. And of course in the olympiad problem the multigraph is assumed to be finite.

Let me sketch a proof of Kőnig's theorem. Call the partite sets $A$ and $B$. By Hall's "marriage theorem" we can find a matching that covers any given finite subset of $A$. Then we can use the compactness of the Tychonoff product space $\prod_{a\in A}N(a)$ to get a matching $M_1$ that covers $A$. Likewise there is a matching $M_2$ that covers $B$. To extract a perfect matching from $M_1$ and $M_2$ we use Banach's refinement of the Cantor–Bernstein theorem:

Theorem. Given any maps $f:A\to B$ and $g:B\to A$, we can find sets $A_1,A_2,B_1,B_2$ such that $A=A_1\cup A_2$, $B=B_1\cup B_2$, $A_1\cap A_2=B_1\cap B_2=\varnothing$, and $f[A_1]=B_1$ and $g[B_2]=A_2$.

P.S. For simple graphs, the condition "$n$ is a positive integer" in Kőnig's theorem can be weakened to "$n$ is a nonzero cardinal number, finite or infinite"; see the old question Perfect matchings in infinite regular bipartite graphs.