Re: injective monotone functions on k-sets

edfromo@xxxxxxxxx writes:

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?

Yes. In fact, by a theorem of de Bruijn, Tenbergen and Kruyswijk,
the subsets of S can be written as the disjoint union of symmetric chains,
where a symmetric chain consists of nested subsets
A_1 \subset A_2 \subset ... \subset A_m
with card(A_{j+1}) = card(A_j) + 1 and card(A_1) + card(A_m) = n.
See e.g. chapter 3 of I. Anderson, "Combinatorics of Finite Sets",
Oxford 1987, ISBN 0-19-853367-5 and 0-19-853379-9.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

.

Loading