Re: injective monotone functions on k-sets

edfromo@xxxxxxxxx in litteris <ft2uu6$k7h$1@xxxxxxxxxxxxxxxx> scripsit:
Let S be a set of size n, and let S^k and S^{k+1} denote the set of
subsets of S of size k and k+1 respectively. Given k, is it true that
for sufficiently large n, there is an injective function
f : S^k -> S^{k+1}
such that A \subset f(A) for all A in S^k?

Clearly this requires n \geq 2k+1 by cardinality considerations. Is
this condition sufficient?

This is done with the marriage lemma. Viz.: if R \subset X \times Y
is a binary relation between finite sets X and Y, such that for every
subset E of X the cardinality of the projection in Y of R \cap (E
\times Y) (i.e., the image of E in Y) is at least equal to the
cardinality of E, then there exists an injetion of X in Y whose graph
is included in R).

With the notation above, let X be S^k and Y be S^{k+1}, and let R be
the relation "A \subset B" (for A in X and B in Y). The marriage
lemma shows that to obtain an f such as you ask, it is sufficient
that, for any set E of m subsets of S of size k, the set E' obtained
by adding one element in every possible way to every element of E is
of cardinality at least m. But the relation R restricted to E \times
E' matches each element of E with exactly n-k elements of E' and each
element of E' with at most k+1 elements of E; so as long as n-k >=
k+1, i.e. n >= 2k+1, we have indeed card(E') >= card(E) (by double
counting).

Cheers,

--
David A. Madore
(david.madore@xxxxxx,
http://www.madore.org/~david/ )


.

Loading