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$ Commented 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$ Commented 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$ Commented 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$ Commented Dec 27, 2012 at 17:22
  • $\begingroup$ Ah, I didn't F5 before posting the above comment. I'm sorry. $\endgroup$ Commented 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$ Commented 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$ Commented Dec 28, 2012 at 10:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .