0
$\begingroup$

Is it possible to show that every 1-design $D$ with $\lambda=4,k=4$ on $v$ points (for $v$ that is a multiple of $3$) contain some 1-design $Q$ with $\lambda=1,k=3$ on $v$ points such that every block of $Q$ is some block of $D$ that one of its elements is removed?

$\endgroup$
6
  • 1
    $\begingroup$ What do you mean by a $1$-design? Normally block designs parameters are given as $(v,k,\lambda)$ or $t-(v,k,\lambda)$ where $t \ge 2$. Are you really looking at $t=1$, regular hypergraphs? $\endgroup$ Dec 14, 2013 at 23:12
  • $\begingroup$ Douglas Zare, yes. I am looking at $t=1$. $\endgroup$
    – j.s.
    Dec 15, 2013 at 15:20
  • $\begingroup$ I don't quite follow what you mean by "such that every block of $Q$ is some block of $D$ that one of its elements is removed." Can you rephrase it or explain exactly what you mean by an example? Did you mean $Q$ is a triple system instead of block size $4$? Or is it of order $v-1$ rather than $v$? $\endgroup$ Dec 15, 2013 at 17:02
  • $\begingroup$ If you are looking at $t=1, \lambda=1$ then you just have a partition. A necessary condition to have a disjoint collection of sets of size $3$ covering everything is that the number of points is divisible of $3$. However, you can have a regular hypergraph of degree $4$ so the number of points is not divisible by $3$. For example, $4$ copies of a $4$ element set, or less trivially the complements of lines in the Fano plane which has $7$ vertices. $\endgroup$ Dec 15, 2013 at 23:22
  • $\begingroup$ Yuichiro Fujiwara; I correct my question. $k$ for $Q$ is $4$. $\endgroup$
    – j.s.
    Dec 17, 2013 at 10:54

1 Answer 1

3
$\begingroup$

As I understand it, your question has the answer no.

Since you ask for $1-$designs, $\lambda$ is essentially how many times one of the $v$-many points appear in a block, which has size $k=4$ in the design $D$. Start with a design $D'$ on $16$ points. I arrange them in a square and choose for blocks the rows, columns, and both (extended) diagonals, giving $16$ blocks and $\lambda=4$. Now multiply this design by 3 to get $D$ on $v=48$ points with the desired parameters. Any partition into sets of size $3$ has to have one or more sets "cross" different copies of $D'$. One can modify this to get larger "clumps", but if your $D$ falls into two or more pieces on $v'$ and $v''$ points where one of them is not a multiple of $3$, then you cannot refine that design into a partition of $3-$sets as you desire.

I have not verified it, but I suspect that this can be modified to a "connected" example where one still fails to refine such a design into a partition into $3-$sets.

Gerhard "I Think That Covers It" Paseman, 2013.12.17

$\endgroup$
3
  • $\begingroup$ Gerhard, thanks. In fact, I assume D is a connected. Can you give a counterexample in this case? $\endgroup$
    – j.s.
    Dec 18, 2013 at 9:45
  • $\begingroup$ No, I don't have one. However, I would start with the following "gadget" in trying to build one. Arrange n>4 elements in a ring, and cover adjacent elements with 4-sets. Remove one of the 4-sets and call this a ring. (Later you will add elements and blocks to cover the 4 "exposed" elements with lambda = 3.) Refining this by a three-set partition limits the possibilities of which of the exposed elements are uncovered, and $n$ gives you some control. Try putting some of these rings and a few blocks together. Gerhard "Does That Cover It Now?" Paseman, 2013.12.18 $\endgroup$ Dec 18, 2013 at 18:33
  • $\begingroup$ For example, if n is 2 mod 3, then only two "adjacent exposed" elements of a ring must remain uncovered by a 3-refinement restricted to 3-sets inside that ring. Now arrange some "transverse" blocks that mess with this adjacent property. Gerhard "You Can Finish It Up" Paseman, 2013.12.18 $\endgroup$ Dec 18, 2013 at 18:40

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.