Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, and which satisfies the following properties:

  1. $\forall A\in \mathcal{F},\ f(A)\in A$,
  2. If $|A_1\cap A_2|=n-1$ then $f(A_1)\not=f(A_2)$.

My question is:

When does this kind of functions exist?

A simple result is that if $n=N-2$ then this kind of functions exist iff $N$ is odd, since we can reduce this question to idempotent symmetric latin square designing problem.

Proof: We change the function to its complement functions, i.e. $f'(\bar{A})=f(A)$. Note that $\bar{A}$ have only two elements, so $f'$ can be regarded as a function $\Omega\times \Omega\rightarrow \Omega$ such that $f'(a,b)\not=a\not=b$ and $f'(a,b)\not=f'(a,c)$ and $f'(a,b)=f'(b,a)$, which is exactly some kind of idempotent symmetric latin square.

We can also show that $n$ should not less then $N/2-1$.

Proof: Suppose not, choosing an arbitrary subset $A'\in \Omega$ and $|A'|=n-2$, since $n<N/2-1$ we can find different $a,b\not\in A'$ and denote $A_1=A'\cup\{a\},\ A_2=A'\cup \{b\}$. For $i=1,2$, we have $N-n+1$ ways to extend $A_i$ to a subset with cardinal $n$ by adding a new element. We claim that there must be an element $e\not\in A_1\cup A_2$, such that $f(A_1\cup\{e\})=f(A_2\cup \{e\})=e$ and which contradict to property 2. But this is easily follows by $2(n+1)<N\Leftrightarrow n<N/2-1$.

So, does anyone know whether this problem can be reduced to any well studied problems?

Actually, I conjecture that this kind of functions do not exist when $n<N-2$, but I don't know how to prove it.

  • $\begingroup$ If the first condition is replaced by $f(A) \in L_A$, where $L_A$ is some adversarially chosen set of size $|A|$, then you are asking whether the Johnson graph $J_{N,n}$ has list chromatic number at most $n$. $\endgroup$ – Ben Barber Jul 24 '15 at 15:50
  • $\begingroup$ I suppose propertise is sort of like expertise. I like it! Perhaps the "propertise" of an object is not just a miscellaneous list of properties, but the gestalt of all relevant properties taken together. $\endgroup$ – Gerald Edgar Jul 24 '15 at 15:55

Let $p$ be smallest prime divisor of $n$. I claim that $N<n+p$ though I have no idea about how adequate this estimate is. Consider any subset $C\subset \Omega$ of size $|C|=n+1$. Note that all $n$-element subsets of $C$ have different values of $f$, hence all $n+1$ values are taken each exactly once. Assume that $N\geq n+p$ and choose $U\subset \Omega$, $|U|=n+p$. Consider all $\binom{n+p}{n+1}$ subsets $C\subset U$, $|C|=n+1$, for each of them consider all its subsets $A\subset C$, $|A|=n$. Each element of $C$ equals $f(A)$ for unique $A\subset C$. Sum up by all $C$. Each $A$ is counted $p$ times, while each $a\in U$ appears as $f(A)$ for $\binom{n+p-1}{n}$ subsets, as it lies in $\binom{n+p-1}{n}$ sets $C$. But $\binom{n+p-1}{n}$ is not divisible by $p$, a contradiction.

| cite | improve this answer | |
  • $\begingroup$ Nice arguments! $\endgroup$ – Paul Sep 23 '15 at 5:45

You do not want $f$ to be injective; so a condition weaker than that for system of distinct representatives should do. If $|\mathcal{F}|=n$ definitely this is true.

| cite | improve this answer | |
  • $\begingroup$ thank you, of course $f$ is not injective since $\mathcal{F}$ is much larger than $\Omega$. Indeed, the restriction of $f$ on the family generated by $A_1\cup A_2$ is a distinct representation, but I can't see how this can be used to solve this problem. $\endgroup$ – Paul Mar 26 '15 at 13:36

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.