Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [combinatorial-designs]

For questions about Combinatorial design theory, a part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. The theory has applications in the area of the design of experiments.

Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. The theory has applications in the area of the design of experiments.

A combinatorial $t$-$(v,k,\lambda)$ design $D$ is a set of $k$-element subsets of $\{1,\ldots,v\}$ such that each $t$-element subset of $\{1,\ldots,v\}$ is contained in exactly $\lambda$ elements of $D$. Of particular interest are Steiner systems, which are designs with $\lambda = 1$.

This tag should not only be used for narrow sense combinatorial designs, but also for related combinatorial questions like packing designs, covering designs, the spatial arrangement of entries in an array as in Sudoku grids etc.

363 questions
2
votes
1 answer

On non-isomorphic and isomorphic Steiner Triple System!

in this wikipedia page, it says the following Up to isomorphism, the STS(7) and STS(9) are unique, there are two STS(13)s, 80 STS(15)s, and 11,084,874,829 STS(19)s Now, in wolframe page it says the following The numbers of nonisomorphic Steiner…
YOUSEFY
  • 639
  • 9
  • 21
1
vote
0 answers

finding confounded effects

In a (3$^3$,3$^2$) design, how to find the effects confounded given the key block (0,0,0),(0,1,2) and (1,0,1)? I have completed the key block. (0,0,0),(0,1,2),(1,0,1),(1,1,0),(2,1,1),(0,2,1),(2,0,2)(2,2,0),(1,2,2) i.e.,…
kris91
  • 401
1
vote
2 answers

Find a (16,6,1) Balanced incomplete block design (BIBD)

I'm trying to find a balanced incomplete block design with the 16 items and $\lambda= 1$. I've calculated (using these defenitions) that a BIBD with 8 blocks and 6 items per block should be possible. However, when trying to contruct this with r, it…
user3136936
  • 117
1
vote
2 answers

How one can combine two covering designs?

There is a discussion on a science forum that how can one find small covering designs for lotto system. Namely, in that lotto we take seven numbers from the set $\{1,\ldots,39\}$ and we win if we have at least four correct number. I found by Art of…
noncontinuity
  • 21
1
vote
1 answer

balanced incomplete designs

My textbook said a balanced design with covalency 0 is a complete design. I don't understand this, because $$\begin{gather} \text{set of varieties}=\{v_1,v_2,v_3\}\\ B_1 = \{v_1\},\\ B_2 = \{v_2\},\\ B_3 = \{v_3\}\end{gather}$$ is a design that is…
user81055
  • 599
1
vote
0 answers

"Orthogonal" Steiner Systems

Let $1\leq t\leq k\leq v$ be integers. A Steiner system $S:=S(t,k,v)$ is a collection of subsets $K$ of size $k$ of a set $V$ of size $v$ such that for every subset $T\subseteq V$ of size $t$, there exists a unique $K\in S$ with $T\subseteq K$. For…
jpvee
  • 3,563
1
vote
0 answers

$2$-$(v, \{3,4\},1)$-Designs

Let $t$, $\lambda$, $v$ be positive integers and let $K$ be a set of positive integers. A $t$-$(v,K,\lambda)$-design is a pair $(X,\scr{B})$ such that $X$ is a set (of so-called vertices) of cardinality $v$, $\scr{B}$ is a set of subsets of $X$…
jpvee
  • 3,563
1
vote
1 answer

How to construct a self orthogonal Latin square of order 5

I have been unable to find an elegant method of constructing self orthogonal Latin squares. However, I came across this question: construct a self orthogonal Latin square of order 5 using the fact that the set of elements on the main diagonal of a…
user486957
1
vote
0 answers

Pairing Combinations of an 8-player/team round-robin

I potentially want to write code for a 8-player/team round-robin tool that allows you to use any combination of schedule (e.g. select from various drop downs). The problem is I don't understand one complicated part. I'll use an example to explain…
Jack Ralls
  • 11
1
vote
1 answer

Show that $t-(v,k,\lambda)$ design with $v\leq k+t$ is trivial

Let $D=(V,B)$ be a $t-(v,k,\lambda)$ design where $V$ is a finite set and $B$ is a collection of subsets of $V$. A trivial $t$-design is defined as a design with one block that contains all the points or a design that has all the $k$-subsets of the…
kswim
  • 433
0
votes
1 answer

Prove Fisher's Inequality for a non-trivial 2 - (v, 4, λ) design

Fisher's Inequality states that if $v\ge k$, then $b\ge v$. In this case $k=4$. I am still pretty new to designs, and so don't understand things fully yet. There is a formula for $b$ as follows: $$b = \frac{\lambda v(v-1)}{k(k-1)}$$ Using this, I…
KierenC
  • 25
0
votes
1 answer

Proof relating to 2-designs. Show $\lambda \le \dbinom{v-2}{k-2}$.

I am required to show the following for any $2 - (v, k, \lambda)$ design: $$\lambda \le \dbinom{v-2}{k-2}$$ and that if equal, then the design is trivial. It's the proof I am struggling with, the second part I found trivial.
KierenC
  • 25
0
votes
0 answers

6 people playing 8 ball

We figured out how to play 15 games with 5 players but not six yet. 3 teams of 2, changing players each game. One team sits out each game. We need the team sequenced so it works out that everyone is teamed at least once with each of the other 5…
Alan
  • 1
  • 1
0
votes
1 answer

Why can't these $STS(9)$'s have 8 blocks in common?

Take the following pair of balanced partial triple systems $(R,P_1)$, $(R,P_2)$. Where $R=\{1,2,3,4,5,6\}$ and: $P_1=\{\{1,3,5\},\{1,4,6\},\{2,4,5\},\{2,3,6\}\}$ $P_2=\{\{1,4,5\},\{1,3,6\},\{2,4,6\},\{2,3,5\}\}$ Suppose we have a steiner triple…
Ook
  • 211
0
votes
1 answer

Question dealing with partitions of a set with N elements into classes with 2 elements

I stumbled upon a maths problem wich I need To solve for a current paper I am writing. Have you seen this before? Is it solved and more concretely is there an efficient algorithm for this problem? If there is any paper you can direct me to I`d be…
Constantin Economides
  • 1
1
2