<p>Let there be a large set $X$, and a bijective function $f$ which maps the integer range 1 to $|X| \choose 2$  onto the subsets of $X$ of size 2. Given integers $L$ and $k$, where $2 \leq L \leq |X|$ and $1 \leq k \leq {|X| \choose 2}$, what is the cardinality of the collection $P^L_k=\{Y : Y \subset X$ and $|Y|=L$ and $f(i) \not\subset Y \; \forall 1\leq i \leq k\}$.</p>

<p>Is there a more efficient way than generating all subsets of size $L$ and checking? Alternatively, do you see a good way to approximate the cardinality?</p>

CC BY-SA 3.0
2012-02-14T00:37:55.143Z
Is f given as part of input or some fixed function you forgot to specify in the question?  If f is given as part of input, then the problem is equivalent to counting the independent sets of certain size in a graph, and I am sure that it is #P-complete although I do not have a reference at hand.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-14T00:43:40.393Z
Yes the function f is given. How would you construct such a graph?
mitchus
CC BY-SA 3.0
2012-02-14T00:45:50.687Z
Rephrasing the current question in terms of counting independent sets of certain size in a graph is an easy exercise, so probably it is better if you can think it by yourself.  Please ask me (or someone else) if you cannot figure it out in a day or two.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-14T01:00:50.413Z
Ok I see what you mean. Hmm this is bad news, literature seems to say that it is very hard to even approximate unless the graph is very sparse.
mitchus
<co.combinatorics>
How many subsets of size L do not contain the first k arbitrary pairs?
mitchus
# How many subsets of size L do not contain the first k arbitrary pairs?

(Asked by: username_0 on 2012-02-14)

Let there be a large set $X$, and a bijective function $f$ which maps the integer range 1 to $|X| \choose 2$ onto the subsets of $X$ of size 2. Given integers $L$ and $k$, where $2 \leq L \leq |X|$ and $1 \leq k \leq {|X| \choose 2}$, what is the cardinality of the collection $P^L\_k=\{Y : Y \subset X$ and $|Y|=L$ and $f(i) \not\subset Y \; \forall 1\leq i \leq k\}$.

Is there a more efficient way than generating all subsets of size $L$ and checking? Alternatively, do you see a good way to approximate the cardinality?

**Tags:** co.combinatorics
> **Comments:**
> **username_1**: Is f given as part of input or some fixed function you forgot to specify in the question?  If f is given as part of input, then the problem is equivalent to counting the independent sets of certain size in a graph, and I am sure that it is #P-complete although I do not have a reference at hand.  
> **username_0**: Yes the function f is given. How would you construct such a graph?  
> **username_1**: Rephrasing the current question in terms of counting independent sets of certain size in a graph is an easy exercise, so probably it is better if you can think it by yourself.  Please ask me (or someone else) if you cannot figure it out in a day or two.  
> **username_0**: Ok I see what you mean. Hmm this is bad news, literature seems to say that it is very hard to even approximate unless the graph is very sparse.  

---

## 0 answers

