Let $2 \leq k \leq n$ be integers, let $[n] := \{1,2,\ldots,n\}$, and for a subset $A \subseteq [n]$ let $A^2 := A \times A$ be the Cartesian product of $A$ with itself and let $|A|$ denote the cardinality of $A$.
Question: Let $f(k,n)$ denote the smallest integer $r$ for which there exist subsets $A_1,A_2,\ldots,A_r \subseteq [n]$ with the properties that $|A_j| \leq k$ for all $j$ and $\bigcup_{j=1}^r A_j^2 = [n]^2$. What is $f(k,n)$ (e.g., is there an explicit or explicit-ish formula)?
Examples and notes:
If $k \geq n$ then we have $f(k,n) = 1$ trivially, since we can pick $A_1 = [n]$.
If $k = 2$ then we have $f(2,n) = n(n-1)/2$, since the only way to have $\bigcup_{j=1}^r A_j^2 = [n]^2$ is if $\{A_1,A_2,\ldots,A_r\}$ contains all $n(n-1)/2$ of the $2$-element subsets of $[n]$.
A counting argument shows that $f(k,n) \geq \frac{n(n-1)}{k(k-1)}$.
The lower bound from the previous bullet point is not always attained. For example, if $n = 4$ and $k = 3$ then that bound says that $f(3,4) \geq 2$. However, it is not difficult to show that $f(3,4) = 3$ (attained, for example, by the $3$ subsets $\{1,2,3\}$, $\{1,2,4\}$, $\{2,3,4\}$).
Similar to the previous bullet, $f(n-1,n) = 3$ for all $n \geq 3$.
I have searched the OEIS, but have not found anything that I am convinced is this sequence/triangle. Additional numerical results might help in this regard.
