Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
$\lbrace (1,2,5),(2,3),(3,4,5),(1,4)\rbrace$ –  Gjergji Zaimi Feb 9 '12 at 21:39
    
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? –  Johnny Feb 9 '12 at 21:44
3  
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$. –  Andreas Blass Feb 9 '12 at 21:44
1  
Better and better ... thanks, Andreas. It seems like a silly question that I started with now. –  Johnny Feb 9 '12 at 21:48

1 Answer 1

up vote 6 down vote accepted

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?

share|improve this answer
    
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. –  Johnny Feb 9 '12 at 22:00
1  
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)$. –  domotorp Feb 10 '12 at 7:17

Your Answer

 
discard

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.