# 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$$.

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.

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.

• For this approach, it seems a worst case scenario is when every map decomposes into disjoint 3-cycles. Even then you can add extra elements to A so that A intersect with its images is small, and A is larger than X/(3^k). Gerhard "Is Also Only Asserting This" Paseman, 2019.07.19. – Gerhard Paseman Jul 19 '19 at 18:26