6
$\begingroup$

I asked this question on Stackexchange, but I got no answer, so I ask it here.

Let us define a $2$-set as a set with exactly $2$ elements. For a natural number $n$, let $l(n)$ denote the least possible number of members of a union-closed family of sets generated by $n$ distinct $2$-sets. I'm interested in a useful formula or minoration for $l(n)$.

There are easy majorations, for example $l({r\choose 2}) \leq 2^{r} - 1 - r$ and (for $r \geq 1$) $l({r\choose 2}+1) \leq 2^{r} + 2^{r-1} - 1 - r$, and these upper bounds seem to be exact values for small values of $r$, but I would avoid the task of handling this question if there is literature about it. Do you know ? Thanks in advance.

Note : there is a similar question here : Kruskal-Katona type question for union-closed families of sets

but not identical.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

That problem was solved by Uwe Leck, Ian T. Roberts and Jamie Simpson in the paper "Minimizing the weight of the union-closure of families of two-sets.", Australasian Journal of Combinatorics 52 (2012): 67-73.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. My bet was : If $n={r\choose 2}+s$ with $s \leq r-1$ (which is posible in one and only one way), then $l(n) = 2^{r+1}-2^{r-s}-1-r$. Was I right ? (Sorry, stupid comment, since you gave a link.) $\endgroup$
    – Panurge
    May 6, 2016 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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