Is it possible to choose $k$ fixed point free maps $f\_i$ from an arbitrarily large finite set $X$ to itself such that:


$$\max\_{A\subset X} \vert A \setminus \cup\_{i=1..k} f\_i(A)\vert = O(\vert X\vert^{1-\epsilon})$$


for some $\epsilon >0$?


I am mostly interested in the case $k=2$ or $3$.



Almost covering every set with few images
The maximum is attained at a set $A$ disjoint with al its images (just replace $A$ with $A\setminus\bigcup\_i f\_i(A)$). For choosing that, you need to find an independent set in a digraph which is a union of $k$ graphs of out-degrees $1$, i.e., in a digraph of out-degree $k$. 


Any such graph contains a vertex of total degree $\leq 2k$. Put thevertex into $A$ and remove it with all its neighbours from $G$; you again get a graph of largest out-degree $\leq k$, so repeating this procedure you get such independent set of cardinality $\geq\lceil|X|/(2k+1)\rceil$.


This is really the maximum you can get. Split $X$ into groups of $2k+1$ elements (and the remainder). The graph $K\_{2k+1}$ can be split into $k$ Hamiltonian cycles; orienting them, you get the required functions $f\_i$. The remainder can be dealt with similarly.


Thus, the maximum under consideration is $\geq\lceil|X|/(2k+1)\rceil$, and this is sharp.


