4
$\begingroup$

A quick look at Ed Spence's page reveals two such examples: (7,3,3) and (16,6,3).

If there is a known classification and/or name by which such designs go, I'd love to know about them too.

EDIT: I am specifically interested in designs where at least one pair of blocks has a nonempty intersection, with multiple blocks allowed. A slightly off-the-beaten-path kind of object, perhaps.

EDIT2: Oops, I actually meant empty intersection. (Nevertheless, the case $B=V$ is too trivial for my purposes.) I am afraid that this creates a problem with Yuichiro Fujiwara's beautiful construction. Really sorry about the mistake, I've only noticed it now.

$\endgroup$
8
  • 1
    $\begingroup$ If we restrict the question just to symmetric designs (so that $v=b$) then there are examples $(7,4,2), (25,9,3), (61,16,4),(121,25,5)$ described in the CRC Handbook of Combinatorial Designs [link text][1] (The list does not go far enough to examine $\lambda=6$.) If one removes a block from such a design one obtains a residual design in which $r$ is still equal to $\lambda^2.$ So there are certainly a number of examples. It would be interesting to know if there are any infinite families. [1]: emba.uvm.edu/~jdinitz/hcd.html $\endgroup$ Dec 27, 2012 at 14:12
  • $\begingroup$ @Ken W. Smith: I am actually interested in designs where at least one pair of blocks has a nonempty intersection, so this rules out symmetric designs, but the residual idea is interesting. So thanks a million! $\endgroup$ Dec 27, 2012 at 14:35
  • $\begingroup$ @Felix: thanks! -- your more general question is probably VERY open! btw, even if a symmetric design does not exist (such as $(211,36,6)$), there is still a possibility that a design exists with the residual parameters. $\endgroup$ Dec 27, 2012 at 14:46
  • $\begingroup$ Didn't you forget some other restrictions on the kind of (block) design you want? If you're really ok with a $2$-design of any kind as long as $r = \lambda^2$, then infinitely many of them sure exist. For example, for any finite point set $V$, you take $B = V$ as its only block. Obviously $\lambda = 1$ because every pair of elements of $V$ appears exactly once in a block of the block set (which is a singleton consisting of a block of size $\vert V \vert$). You have $r = 1$ as well because every point appears exactly once for obvious reasons. $\endgroup$ Dec 27, 2012 at 17:22
  • $\begingroup$ Ah, I didn't F5 before posting the above comment. I'm sorry. $\endgroup$ Dec 27, 2012 at 17:35

2 Answers 2

6
$\begingroup$

So I read your edit, and here's the answer: Yes. Infinitely many of them exist.

Anyway, if you only need a $2$-design with $r = \lambda^2$ which has at least one pair of blocks intersecting each other, then you can simply copy a Steiner $2$-design. Take an $S(2,k,v)$ (i.e., a Steiner $2$-design of order $v$ and block size $k$, which exist for infinitely many pairs of $v$ and $k$). Then its repetition number $r$ is exactly $r = \frac{v-1}{k-1}$. Since it's a Steiner $2$-design, its index $\lambda$ is one. If you make a copy of this design $r = \frac{v-1}{k-1}$ times, then what you get is a $2$-design of order $v$, block size $k$, index $\frac{v-1}{k-1}$, and repetition number $(\frac{v-1}{k-1})^2$.

To make the above trivial method even more trivial, here's an example: Take the Fano plane. It's the unique $S(2,3,7)$. Copy this guy $3$ times. Then you get the $2$-$(7,3,3)$ design you mentioned in your question. Why we copied $3$ times is because it's $\frac{v-1}{k-1}=\frac{6}{2}=3$. So, for example, because an $S(2,3,v)$ exists for all $v \equiv 1, 3 \pmod{6}$, you can have infinitely many examples of what you want by pasting the same $S(2,3,v)$ $\frac{v-1}{2}$ times.

Edit: I don't know if this makes a difference, but if you don't want repeated blocks, there are still infinitely many examples. A $2$-design is simple if it has no repeated blocks (i.e., all blocks are distinct). Two $2$-designs $D_0$ and $D_1$ on the same point set are disjoint if they have no common block.

Now, if you have $\frac{v-1}{k-1}$ mutually disjoint $S(2,k,v)$s, taking the union of their block sets will give you a simple $2$-design of the same order and the same block size which satisfies $r = \lambda^2$. Since you didn't specify the block size, you can use, for example, the large set of Steiner triple systems of order $v$, which is a set of $v-2$ mutually disjoint $S(2,3,v)$s. (A large set is a set of disjoint designs of block size $k$ in which the union of block sets is the set of all $k$-subset of the point set. For the case of Steiner triple systems, you have $v-2$ mutually disjoint $S(2,3,v)$s.) A large set of $S(2,3,v)s$ exist for all possible $v \not= 7$. Since $\frac{v-1}{2} < v-2$ for all $v > 3$, you can surely have $\frac{v-1}{2}$ mutually disjoint $S(2,3,v)$s. Hence, infinitely many no-repeated-block versions also exist.

Edit2: The $2$-designs constructed here have a pair of parallel blocks unless you pick too small $v$. For example, the $S(2,3,7)$ is the only nontrivial guy that doesn't have parallel blocks. So larger v always works for your problem with the added condition if $k$ is $3$. I'm on my iPhone, so allow me to omit the details; it's almost trivial if you think about if you can construct a Steiner $2$-design without parallel blocks.

Edit3: Now I'm back on my mac. Here's why every $S(2,k,v)$ for large enough $v$ has a pair of blocks that don't intersect each other:

Let $(V, \mathcal{B})$ be an $S(2,k,v)$ in which no pair of blocks are parallel. Take a block $B = \lbrace x, y , z\rbrace \in \mathcal{B}$. Because every block must intersect $B$, the degree of $x$ (i.e., the number of blocks that contain $x$) is $\frac{\vert \mathcal{B}\vert-1}{k} +1 = \frac{v(v-1)-k(k-1)}{k^2(k-1)}+1$. However, because we have $r = \frac{v-1}{k-1}$, we must have $\frac{v-1}{k-1} = \frac{v(v-1)-k(k-1)}{k^2(k-1)}+1$. Because the left-hand side is $O(v)$ while the right-hand side is $O(v^2)$, this can hold only when $v$ is small enough compared to $k$. (You can actually solve it to express $v$ by $k$ and check when this condition can be met if you want.) So, for fixed $k$, if you take a large $S(2,k,v)$, it must have a parallel block. Thus, by taking $\frac{v-1}{k-1}$ copies or pasting $\frac{v-1}{k-1}$ mutually disjoint ones, you get the desired $2$-design as long as $v$ is large enough.

$\endgroup$
1
  • $\begingroup$ It turns out there is an even simpler way to show that $S(2,k,v)$ has no parallel blocks for $v \geq 8$: a $(v,k,1)$-design with $b>v$ must be quasi-symmetric with $x=0,y=1$. And for $S(2,k,v)$ we have $b>v$ iff $v \geq 8$. QED. Thanks again, Yuichiro, for the nice solution! $\endgroup$ Jan 28, 2013 at 20:33
1
$\begingroup$

I will go ahead and put this as an (attempt at an) answer. Looking at the Bruck-Ryser-Chowla theorem for symmetric designs, it appears that as long as $\lambda$ is not congruent to 2 modulo 4 then the BRC is satisfied. Therefore there are an infinite number of parameters for putative symmetric designs with $r=k=\lambda^2$. Since no family of this type appears in the chapter on symmetric designs in the CRC Handbook of Combinatorial Designs then I suppose that in general it is an open question as to whether symmetric designs with these parameters exist. (They certainly exist for $\lambda = 2, 3, 4, 5$ but are ruled out by the BRC for $\lambda = 6.$)

If a symmetric design with $r=\lambda^2$ exists then its residual design also has this property.

The problem of general $(v,b,r,k,\lambda)$ designs is much broader and I don't have an answer to the more general original question. (I assume that in the definition of ``combinatorial design" we do not allow repeated blocks.)

$\endgroup$
1
  • $\begingroup$ I accepted the other answer, as it gives a direct answer to the infinite existence problem, but this one is also very good and useful. Wish I could accept both. $\endgroup$ Dec 28, 2012 at 10:54

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.