Almost covering every set with few images 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$.
 A: I deleted a comment which was based on my misreading the problem. Let me give a heuristic which suggests the answer is no for large enough epsilon.
For any fixed point free map f on a set large enough, one can get a set A about half the size of X whose image is disjoint from A. Start by choosing pairs (a, f(a)) where f(a) has many pre images and a does not. If nothing else, gather all the points with no pre images to start with to build A. If this doesn't get you a large enough set of elements a, then look at the cycle structure induced on elements by f. If you have a cycle of elements, choose every other element of the cycle. If a single element fans out into a large tree of iterated preimages, choose alternating members from each branch. There is a way to do this so that you get at least a third and close to a half of all members of X into a set A.
So I assert (but do not prove here) that for any such fixed point free map f, there is a subset A of X which is completely moved by f and A is about half the size of X.  Now you should be able to iterate this argument to get a subset C of A which is at least (1/3)^k size of X which is completely moved by all k fixed point free maps f_i. 
Finding a largest sized set C given k maps is a combinatorial optimization problem that likely is hard and in the literature. I don't have a search term for you presently.
Gerhard "Searching Up Search Problems: NP-Hard?" Paseman, 2019.07.19.
A: 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.
