For $X=\lbrace 0,\ldots,n-1\rbrace$, let $F\subseteq 2^X$ be a family of subsets of $X$ such that, for every $x\in X$, the singleton $\lbrace x\rbrace$ is the intersection of some elements of $F$. I am interested in the minimal families that have this property, in particular whether it is possible to have $|F|< n$. Can anyone (a) give an example where $|F|< n$, (b) provide an argument for why $|F|\ge n$, or (c) point me in the direction of some existing results.

Bonus question: For any $k< n$, the family $F= \lbrace \lbrace x,x+1,\ldots,x+k-1 \rbrace:x\in X \rbrace$, where addition is carried out modulo $n$, satisfies the stated condition (minimally) and contains exactly $n$ elements, so $|F|= n$ is always achievable. How does the structure of a general minimal family relate to these highly regular families? Is a minimal family always a disjoint union of some regular families?

  • 3
    $\begingroup$ $\lbrace (1,2,5),(2,3),(3,4,5),(1,4)\rbrace$ $\endgroup$ – Gjergji Zaimi Feb 9 '12 at 21:39
  • $\begingroup$ Thanks Gjergji - this can easily be generalized for $n=2m+1$ to give a family of size $m+2$. So new question: can anyone find a better construction than this? $\endgroup$ – Johnny Feb 9 '12 at 21:44
  • 3
    $\begingroup$ Let $X$ be the set of vertices of a $d$-dimensional cube. Let $F$ be the set of faces of the cube (each face being considered as just the set of its vertices). Then $|X|=2^d$ while $|F|$ is only $2d$. $\endgroup$ – Andreas Blass Feb 9 '12 at 21:44
  • 1
    $\begingroup$ Better and better ... thanks, Andreas. It seems like a silly question that I started with now. $\endgroup$ – Johnny Feb 9 '12 at 21:48

You can achieve $\lvert F\rvert = 2\lceil\log_2 n\rceil$ by using all subsets of the form $\{x\in X \vert i^{\text{th}}\text{ bit of }x\text{ is }j\}$ for $i \in \{0,1,\ldots,\lceil\log_2 n\rceil-1\}$ and $j\in\{0,1\}$.

This rate is within a factor of two of best possible because there are at most $2^{\lvert F\rvert}$ different intersections you can form from $\lvert F\rvert$ sets. You require that all $n$ singletons be among this list of intersections, so $\lvert F\rvert \geq \log_2 n$.

Are you interested in the actual minimal value of $\lvert F\rvert$, or just asymptotics?

  • $\begingroup$ Thanks Noah. Originally I wanted the exact minimum for $|F|$, but it seems from the responses here that the answer may not be very clean. The problem came up while investigating the reconstruction of certain graphs from partial information and determining how sparse this information can be - I need to see how these constructions fit in with the larger problem now. $\endgroup$ – Johnny Feb 9 '12 at 22:00
  • 2
    $\begingroup$ Moreover, using Sperner's theorem only ${F \choose F/2}$ intersections can give singletons, so |F| is at least $\log n + \Omega(\log\log n)$. $\endgroup$ – domotorp Feb 10 '12 at 7:17

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.