Inverting sets and the packing problem

Details Inverting sets and the packing problem Inverting sets and the packing problem

1994-09-16

arxiv.org/abs/math/9409213v1

Mathematics

Combinatorics

16 pages

Scientific paper

Given a set $V$, a subset $S$, and a permutation $\pi$ of $V$, we say that $\pi$ permutes $S$ if $\pi (S) \cap S = \emptyset$. Given a collection $\cS = \{V; S_1,\ldots , S_m\}$, where $S_i \subseteq V ~~(i=1,\ldots ,m)$, we say that $\cS$ is invertible if there is a permutation $\pi$ of $V$ such that $\pi (S_i) \subseteq V-S_i$. In this paper, we present necessary and sufficient conditions for the invertibility of a collection and construct a polynomial algorithm which determines whether a given collection is invertible. For an arbitrary collection, we give a lower bound for the maximum number of sets that can be inverted. Finally, we consider the problem of constructing a collection of sets such that no sub-collection of size three is invertible. Our constructions of such collections come from solutions to the packing problem with unbounded block sizes. We prove several new lower and upper bounds for the packing problem and present a new explicit construction of packing.

Affiliated with

Also associated with

No associations

Rating

Inverting sets and the packing problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inverting sets and the packing problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inverting sets and the packing problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-566369