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

Given fixed values for $d \leq k \leq v$. I would like to find a set $B$ of $d$-sets of $[v]$ with the following properties:

  1. Every $k$-set of $[v]$ contains at least one element of $B$

  2. Every element of $[v]$ is contained in at most $r$ elements of $B$.

I would like to keep $r$ as small as possible.

This is very similar to the conditions for a balanced incomplete block design, but I only need an upper bound in condition 2. Also, I do not care about the coverage of pairs of elements of $V$.

Does this type of construction have a name? Are there any bounds on $r$ known (constructive or non-constructive)?

share|improve this question
1  
Passing to complements and dropping the second condition you have covering designs: ccrwest.org/cover.html –  Thomas Kalinowski Nov 20 '12 at 13:34
add comment

1 Answer

Sounds like similar to a forbidden configuration problem in extremal set theory, hypergraph theory, and design theory. I don't know if exactly the same problem has been studied in one of those fields (or somewhere outside of mathematics as applications of this problem), but probably the following similar one has been a subject of serious reseach:

What's the maximum number of edges on a $d$-uniform (hyper)graph avoiding complete ($d$-uniform) sub-(hyper)graphs on $k$ vertices?

If $d=2$, it's just a graph avoiding $K_k$ with as many edges as possible.

You can put it in the language of sets or blocks by regarding edges as $d$-sets or blocks of size $d$. For instance, a $(v, b)$-configuration in combinatorial design theory is a set (or a list) of $b$ blocks whose union is of cardinality $v$. So, the above question is the same as asking the maximum number of blocks avoiding the $\left(k, {{k}\choose{d}}\right)$-configuration.

To relate this to your problem, consider the missing $d$-sets. Since you chose combinatorial design theory, in the remainder we go with the standard notation in the field.

Let $V$ be a finite set of cardinality $v$ and $\mathcal{B}$ a set of $d$-subsets of $V$. In other words, $V$ is the point set and $\mathcal{B}$ is the block set.

You want any $k$-subset of $V$ to contain at least one block $B \in \mathcal{B}$ as its subset(s). If $k=d$, the problem is trivial because you have to take all the ${{v}\choose{d}}={{v}\choose{k}}$ sets as blocks. The case when $d = 1$ is also trivial; you take distinct $v-k+1$ singletons for $\mathcal{B}$, and that's the optimal one. So we assume that $k > d \geq 2$.

Define $\bar{\mathcal{B}}$ as the ${{v}\choose{d}} - \vert \mathcal{B}\vert$ $d$-sets that are not in $\mathcal{B}$. Take distinct ${{k}\choose{d}}$ blocks $\bar{B}_i$ in $\bar{\mathcal{B}}$. If $\vert \bigcup \bar{B}_i \vert = k$, then all the $d$-subsets of the $k$-set $\bigcup \bar{B}_i$ are in $\bar{\mathcal{B}}$, which means that no block in $\mathcal{B}$ appears in $\bigcup \bar{B}_i$. Conversely, if there is a $k$-subset of $V$ no block of $\mathcal{B}$ appears in, then you end up with distinct ${{k}\choose{d}}$ blocks $\bar{B}_i$ in $\bar{\mathcal{B}}$ with $\vert \bigcup \bar{B}_i \vert = k$.

So, the first requirement in your problem is equivalent to avoiding the distinct ${{k}\choose{d}}$ blocks $\bar{B}_i$ in $\bar{\mathcal{B}}$ with $\vert \bigcup \bar{B}_i \vert = k$ (or equivalently avoiding complete $d$-uniform hypergraph on $k$ vertices in a $d$-uniform hypergraph).

If the size of $\bar{\mathcal{B}}$ is small, it's easy to avoid the forbidden configuration. The more blocks, the harder it becomes to not have one. Now you want to make any point in $V$ appear as few times as possible (or make $r$ as small as possible in your original phrasing). If a set of blocks avoiding the forbidden configuration has theoretically as many blocks as possible, the corresponding $\mathcal{B}$ (which you had in mind) has the smallest possible number of blocks. If every point appears as often in $\mathcal{B}$, this achieves the smallest $r$ possible. So, a lower bound on the maximum $\vert \bar{\mathcal{B}} \vert$ leads to a better-than-wild-guess kind of educated guesstimate on the best possible $r$ by assuming each point appears averagely in "optimal" $\mathcal{B}$ and dividing the number of blocks by an appropriate number. An upper bound on the maximum $\vert \bar{\mathcal{B}} \vert$ leads to a lower bound on the minimum size of $\mathcal{B}$ satisfying the first condition in your problem (and the lower bound on $r$ by assuming every point appears equally frequently in an optimal $\mathcal{B}$).

So, the problem of finding a bound on $r$ is now related to that of finding bounds on the maximum number of blocks avoiding complete (hyper)graphs.

If $d = 2$, it's a problem in graph theory. I don't know much about graph theory, but there must be nice results on this kind of forbidden subgraph, I think. So you should check the graph theory literature.

If $d \geq 3$, it's a problem in hypergraph theory (or design theory or extremal set theory). There has to be results on this somewhere, and I'm pretty sure some folks in hypergraph theory and extremal set theory can give you a very good answer. Anyway, as a design theorist, what I'd do first for the lower bound on $\vert \mathcal{B} \vert$ (while keeping in mind the requirement of each point appearing uniformly) is something like this:

Take uniformly at random $d$-subsets of $V$ with probability $p = c\cdot v^x$, where $c$ and $x$ are constants (of which nice exact values will be chosen later) and $\vert V \vert = v$.

The expected value of the number $f_k$ of forbidden configurations you get is upper bounded by ${{v}\choose{k}}\cdot p^{{k}\choose{d}}$. By Markov's Inequality, the probability that you wind up with twice as many as or more than the average is smaller than or equal to $\frac{1}{2}$. Hence, you have the probably $P(f_k \leq 2{{v}\choose{k}}\cdot p^{{k}\choose{d}}) \geq \frac{1}{2}$.

Let $t$ be the random variable counting the number of blocks and $E(t)$ its expected value. Then $E(t) = {{v}\choose{d}}p$. Because $t$ is a binomial random variable, by Chernoff's inequality, for sufficiently large $v$ we have

$P\left(t < \frac{E(t)}{2}\right) < e^{-\frac{E(t)}{8}} < \frac{1}{2}$ (if we choose $c$ and $x$ wisely). Hence, if $v$ is sufficiently large, with positive probability we end up with block set $\mathcal{B}$, where $\vert\mathcal{B}\vert > {{v}\choose{d}}p$ and there are at most $2{{v}\choose{k}}\cdot p^{{k}\choose{d}}$ forbidden configurations. Deleting one block from each forbidden configuration will give you the desired complete-graph-free block set. Hence, with positive probability you can have at least ${{v}\choose{d}}p - 2{{v}\choose{k}}\cdot p^{{k}\choose{d}}$ blocks while avoiding unwanted guys.

So, our task is now to choose $c$ and $x$ for $p=c\cdot v^x$ so that the above number is the largest. The best you can do is, I think, pick $x$ so that the two terms ${{v}\choose{d}}p$ and $2{{v}\choose{k}}\cdot p^{{k}\choose{d}}$ are of the same order, and then set $c$ so that the former becomes strictly larger; this way you get the best order in terms of $v$'s function. If it doesn't work (e.g., $c$ must be egregiously tiny to do this but the background of your problem doesn't want $v$ really large), you lower $x$ a tiny bit, and the number of blocks becomes big and positive for sufficiently (but not unrealistically) large $v$. Either way, since we picked blocks uniformly at randome, the resulting blocks are expected to have every point roughly evenly.

This is just an off-the-top-of-my-head approach, so there has to be a much better way to attack this. I didn't think about the upper bound at all, so the problem may have already be solved somewhere. I might have even botched mathematics in this post somewhere... But I hope at least this way of viewing your problem helps.

Edit: fixed typos and some inaccurate statements about bounds.

More edit: added a minor note that each point likely appears uniformly in the resulting set of blocks.

...and fixed grammar.

share|improve this answer
    
Isn't the $d=2$ case answered by Turan's theorem? –  Felix Goldberg Mar 7 at 10:08
add comment

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.