Skip to main content
added 42 characters in body
Source Link
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

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. TheAn 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}$).

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

...and fixed grammar.

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 $r$ by assuming each point appears averagely in "optimal" $\mathcal{B}$ and dividing the number of blocks by an appropriate number. The 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}$).

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

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}$).

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

...and fixed grammar.

added 308 characters in body; added 2 characters in body; added 1 characters in body
Source Link
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

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:

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.

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.

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$ is something like this:

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$.

Edit: fixed typos and some inaccurate statements about bounds.

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:

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.

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.

added 107 characters in body; added 8 characters in body
Source Link
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

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 $r$ by assuming each point appears averagely in "optimal" $\mathcal{B}$ and dividing the number of blocks by an appropriate number. The upper bound on the maximum $\vert \bar{\mathcal{B}} \vert$ leads to an uppera 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}$).

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 guesshope at least this way of viewing your problem helps.

Edit: fixed typos and some inaccurate statementstatements about bounds on $r$.

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 $r$ by assuming each point appears averagely in "optimal" $\mathcal{B}$ and dividing the number of blocks by an appropriate number. The upper bound on the maximum $\vert \bar{\mathcal{B}} \vert$ leads to an upper bound on the minimum size of $\mathcal{B}$ satisfying the first condition in your problem.

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 guess at least this way of viewing your problem helps.

Edit: fixed inaccurate statement about bounds on $r$.

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 $r$ by assuming each point appears averagely in "optimal" $\mathcal{B}$ and dividing the number of blocks by an appropriate number. The 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}$).

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.

added 264 characters in body
Source Link
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43
Loading
added 138 characters in body; added 17 characters in body
Source Link
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43
Loading
Source Link
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43
Loading