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?
$\begingroup$
$\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$– Douglas ZareDec 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$– Yuichiro FujiwaraDec 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$– Douglas ZareDec 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
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
3
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
answered Dec 17, 2013 at 20:05
-
$\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