Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Definition 1 ($MIF(k)$): A maximal intersecting family of k-sets [in short $MIF(k)$] is uniform intersecting family of k-sets such that if a k-set is not a member of family then there is at least a member in the family which has no common member with that k-set.

Definition 2 ($ISP(k)$): An intersecting family of k-sets say $(P, \mathbb B, \in)$ such that for each $B \in \mathbb B$ there exists a (k-1)-set $A^{'}$ such that $B$ and $A^{'}$ has no common element and $A^{'}$ intersects all the blocks except $B$.

Is it true that any $MIF(k)$ contains an $ISP(k)$ with the same point set $P$?

share|cite|improve this question
What's a $k$-set? Why does $P$ not occur in the explanation of $(P,\mathbb B,\in)$? How can an ISP and an MIF have the same points set $P$ if no point set is mentioned in the definition of an MIF? – joriki May 16 '12 at 12:11
@ to joriki: k-set is a set consisting of k elements. There is no need to express point set of any $MIF(k)$ it is intrinsic just union of the members of the family. – users31526 May 16 '12 at 12:38

This isn't true, simply because sometimes $P$ admits no $ISP(k)$ set! Namely, take $|P| < 2k-1$.

Even more explictly, take $|P| = k$, i.e. your $MIF(k)$ is just a single set $\{1, \ldots, k\}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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