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

## 1 Answer

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 at 18:26