5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ $\lbrace (1,2,5),(2,3),(3,4,5),(1,4)\rbrace$ $\endgroup$
    – Gjergji Zaimi
    Commented Feb 9, 2012 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
    Commented Feb 9, 2012 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
    Commented Feb 9, 2012 at 21:44
  • 1
    $\begingroup$ Better and better ... thanks, Andreas. It seems like a silly question that I started with now. $\endgroup$
    – Johnny
    Commented Feb 9, 2012 at 21:48

1 Answer 1

Reset to default
7
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\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
    Commented Feb 9, 2012 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
    Commented Feb 10, 2012 at 7:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .