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


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.

  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jul 19 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.