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 ...

learn more… | top users | synonyms

-1
votes
0answers
44 views

combinatorial design

Prove that there is a (7, 7, 4, 4, 2)- design and that is is unique up to isomorphism. (v,b, r, k, lamda) v, number of treatments or primary factor levels. b, number of blocks K, number of treatments ...
1
vote
1answer
48 views

How to arrange tournament with 4 rounds for 100 players with each player playing game in group of 10?

I have tournament with 4 rounds and 100 players. Each round consists of 10 games (groups) with 10 players playing together a game (so every round is $10 \times 10$). Is it possible to schedule ...
3
votes
1answer
57 views

how to make a $3$-$(10,4,1)$ design using graphs

A $t$-$(v,k,\lambda)$ design is defined this way : We have a set with $v$ elements (called the points). We also have a collection of distinguished subsets each having $k$ elements, we call each of ...
2
votes
1answer
62 views

Special subspace in vector space over $\mathbb F_5$

Let $\mathbb F_5=\{0,1,2,3,4\}$ is finite field of size $5$. I am trying to find minimal $n$ so that vector space of dimension $n$ over $\mathbb F_5$ contains $2$ linearly independent vectors so that ...
1
vote
1answer
32 views

How can I create 14 unique team rosters from 24 students in groups of 2?

I have a class of 24 students, and they have 14 labs in which I have students partner up. I am trying to find a way to create a roster automatically such that none of my students has a repeat partner ...
3
votes
1answer
94 views

Finding symmetric commuting matrices $A,B,C,D \in M_n(1,-1)$ such that $ A^2+B^2+C^2+D^2=4nI_n $

I am trying to construct a Hadamard matrix of order 28 using Williamson's construction. But I am unable able to construct the necessary symmetric and commuting matrices. Definition: $H_n \in ...
0
votes
1answer
23 views

Existence of a (40,13,4)BIBD (Balanced Incomplete Block Design)

I have been asked to prove that there exists a (40,13,4)BIBD. I admittedly have no idea where to start with this. Checking some of the necessary conditions for BIBDs shows me that if such a BIBD ...
3
votes
3answers
46 views

Points necessary to intersect all lines in finite projective geometry

I'm reading about finite geometries, projective and affine. I wonder what the smallest set of points is, given a geometry $PG(d,q)$, that intersects all lines. (or hyperplanes.) For example in the ...
6
votes
1answer
202 views

What is the minimum number of guesses in order to guarantee to win the prize?

Your friend will pick a $4$-letter word and you will make guesses in order to find it. -A word can contain only the letters $A, B, C,\:\text {and} \:D$, and they can be used more than once. ...
7
votes
0answers
116 views

Minimal number of animals in a matching card game

I saw a card game designed for small children. Each card has a picture of 6 animals on it, and there are 31 cards. When any two cards are compared to each other, they share exactly one animal. The ...
0
votes
0answers
18 views

Hadamard matice decomposition to sparce matrices

$H_2=\begin{pmatrix} 1 & 1\\1 & -1 \end{pmatrix}$ and $H_{2n}=H_2\otimes H_n$. I am looking for decomposition of $H_n$ to sparce matrices and its proof. Is there any good source to suggest ? ...
0
votes
1answer
69 views

Visualising a 1-(50,15,15) design.

The problem I have is the visualisation of a 1-(50,15,15) design. That is a set of 50 points and 50 blocks (lines), so that each point is on 15 lines, and each line contains 15 points. My attempts ...
1
vote
1answer
47 views

A strange scheduling for $K_{24}$.

This question came from a question asked earlier today linked here The question implicitly asked how to make a schedule with his/her class of 24 students such that: 1) Everyday will consist of the ...
-5
votes
1answer
38 views

combinations of 5 groups question [duplicate]

I have $25$ people who will be split in to groups of $5$ people each day over $5$ days in $5$ different locations. Can I rotate them so they all meet each other only once and visit each location once ...
2
votes
1answer
73 views

How does the multiplicative group of a finite field, considered as a vector space, act on subspaces?

Given that a finite vector space $V = \operatorname{GF}(p)^n$ corresponds to the finite field $F = \operatorname{GF}(p^n)$, I'm wondering about how the multiplicative subgroup of $F$, $F^*$, acts on ...
2
votes
1answer
86 views

unbalancing lights

I'm reading the following notes on unbalancing lights, http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf. The question i have is regarding the first page. Where it says Consider a square $n ...
1
vote
1answer
59 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
1
vote
0answers
49 views

Rotation of 15 people at five tables

I have five tables of four people each. At each table is a table leader who remains stationery. How do I rotate the 15 participants so that they get to meet new people each time they rotate?
0
votes
1answer
33 views

Integrality conditions and proof by double counting.

Theorem $\mathbf{3.4.}$ In a block design of type $2-(v,k,\lambda)$ every element lies in precisely $r$ blocks, where $$r(k-1)=\lambda(v-1)\textit{ and }bk=vr\;.$$ The letter $r$ stands for ...
0
votes
1answer
31 views

Constructing $\lambda$-difference sets. Please help.

Given a set say $A=${$0,1,4,16,r$} which is a subset of $\mathbb{Z}_{21}$. How do I find r, such that $A$ is a $\lambda$-difference set for some $\lambda$? Is there some methodical way to solve ...
0
votes
0answers
23 views

Isomorphic Designs

In lectures we were told: "If two designs are isomorphic, then they have the same parameters. However, the converse does not hold" Could someone provide an example were two designs have the same ...
0
votes
1answer
34 views

Question about symmetric block design and Hadamard matrix

I stock in middle of proving that if $A$ is matrix of symmetric block design and $B = 2A - J$ that $J$ is ones matrix then B is a Hadamard matrix if and only if $v = 4(k-\lambda)$. I need to prove ...
0
votes
1answer
25 views

Prove PB(8, {4,3}, 1) does not exist.

I was reading Wallis, Intro to Combinatorial Design. This is 2.1.3. I couldn't understand the way of counting. Hint says, let $f_4, f_3$ be the block counts of sizes 4,3 respectively, then, $6f_4 ...
2
votes
1answer
108 views

Determining the size of an automorphism group for a given design

I'm trying to wrap my head around the idea of automorphisms, and I'm having a lot of issues. One of the questions I've been given as an exercise is thus; Let $\mathbb{V} = \{1, 2, 3, 4, 5, 6\}$ ...
3
votes
1answer
673 views

Is there a memorable solution to Kirkman's School Girl Problem?

Given a solution to Kirkman's School Girl Problem, it is of course easy enough to check that it actually is a solution. But how could you reconstruct it if you lost it? Is there a method or algorithm ...
1
vote
1answer
73 views

Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version

I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help: We would like a general way of creating 'fair' cookie-baking ...
1
vote
0answers
65 views

Existence of Designs

I am familiar with Keevash's proof that provided divisibility conditions hold, $t-(n,k,\lambda)$ designs exist for all but finitely many $t,n,k,\lambda$. My question is, given some $n,t,k$ does ...
3
votes
1answer
33 views

Trying to find a combinatorial design which describes my problem

A group of 8 golfers would like to play in teams, split into two teams of 4, with a different arrangement of teams on each of 5 consecutive days; they would like each pair of players to be on the same ...
0
votes
2answers
95 views

Orthogonal arrays - relation to software testing, is that sample true?

When doing ortohognal arrays testing, the process is like this: Consider a function with 3 variables,each with 3 options. 3 pairs, each with 3*3 values = 27 parametric pairs. Each "function call" ...
1
vote
1answer
56 views

pairwise balanced design has block size related to the number of elements.

A pairwise balanced design is a set of elements $X$ and set of blocks $A$ such that each pair of elements of $X$ occurs in exactly $\lambda$ blocks. I am trying to solve the following problem: Given ...
0
votes
1answer
61 views

Proving Steiner triple system

Let $S$ be a set of size $v$ and let $T$ be a set of $3$-element subsets of $S$. Furthermore, suppose that (a) each pair of distinct elements of $S$ belongs to at least one triple in $T$, (b) $|T| ...
0
votes
0answers
20 views

Construction of a (3v-2,3,1)-BIBD

I want to construct a $(3v - 2,3,1)$-BIBD from a $(v,3,1)$-BIBD and a quasigroup of order $v-1$. Attempt: For new BIBD, firstly, I need $3v-2$ points. Let $A$ be a block in $(3v - 2,3,1)$-BIBD and ...
0
votes
0answers
38 views

Is there a formula to rotate users through 2 positions without repeating weeks, repeating positions, or being paired with the same user?

I need to rotate through users to do 2 jobs without doing the same job for consecutive times, without doing the same job twice in a row, and without being paired with the same person twice. Is there ...
1
vote
0answers
25 views

Combinatorial designs give triangulations of complete graphs

I recently attended a talk on combinatorial design theory. The speaker mentioned briefly that the Fano plane, and other designs give rise to triangulations of complete graphs (the Fano plane gives a ...
2
votes
1answer
46 views

Choosing a committee from two people who are not sitting beside each other.

Assume that $10$ people are sitting around a table. Determine the number of ways to choose a committee, where the committee is made up of two people who are NOT sitting next to each other. Take ...
0
votes
2answers
35 views

Number of blocks in this design $(V,\mathcal{B})$ $|V|=16$ and $\mathcal{B}$ has size $4$

Let $(V,\mathcal{B})$ be a design in which $|V|=16$, each block in $\mathcal{B}$ has size $4$, and each pair of points occurs in precisely one block. How many blocks are in this design? Try 1: ...
0
votes
1answer
22 views

Matrix array built from range?

I have the problem on a past exam: Let the array $L$ be defined by: $0\leq i, j \leq n-1$ $$L=[l_{i,j}] \text{where } l_{i.j} \equiv i+j \pmod n$$ Let $n=4$ and write down the array ...
0
votes
1answer
58 views

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 ...
1
vote
0answers
30 views

A question involving Partial Steiner Triple Systems

I've been given the following question, which I think I've completed, but I just wanted to check whether what I've said is valid. Suppose that a PSTS(23) with a $K_5$ leave is constructed using ...
0
votes
1answer
35 views

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 ...
4
votes
1answer
80 views

Steiner Triple Systems block clique

Given a Steiner Triple System (STS) of order $v$, one can build its graph in the following way: each vertex is a block, and two verticies are adjacent if their blocks have nonempty intersection. Thr ...
-1
votes
1answer
81 views

Symmetric Balanced Incomplete Block Design Example with (56,7,1) [closed]

Can someone give an example of Symmetric Balanced Incomplete Block design with (57,7,1). That is v=b=57,k=r=7, $\lambda = 1$.
2
votes
2answers
57 views

Terminology - variant of a hypergraph

In a hypergraph, we have vertices $V$ and hyperedges $H$, where each hyperedge is a subset of $V$. Suppose that we would like the hyperedges to be (ordered) tuples, rather than subsets. Does this ...
4
votes
1answer
93 views

Diner Combinations, Each Pair Sits Together Exactly Once

There are $N^2$ guests at a party. How can we seat these guests at $N$ tables, in a number of rounds, so that each guest sits with every other guest exactly once? I've come up with an algorithm that ...
0
votes
0answers
21 views

network design: why can't an almost satisfied proper function violated by all given sets?

I'm reading a book about (survivable) network design and i have a problem understanding a lemma. Given an undirected graph G and $V(G)$ its nodes and $E(G)$ its edges. The book defines a proper ...
2
votes
0answers
71 views

$24$ people in groups of $3$ where everyone meets exactly once at the end of some number of rounds

I was presented with this problem at work. Say you have $24$ people and $8$ tables in a room. You want to set people at these tables in groups of three such that during each new round (where people ...
0
votes
2answers
61 views

What is the minimum number of sign patterns in $\frac n2$ of columns (or rows) of Hadamard matrices?

Given a Hadamard matrix of size $n$, I want to know what is the minimum number of unique sign patterns in any $\frac n2$ columns (or rows). I count a sign pattern and its negation to be the same. My ...
0
votes
1answer
194 views

Prove that $\lambda(v-1) = r(k-1)$

This is to do with balanced incomplete block design. Some homework exercise wants me to prove the relation $$\lambda(v-1) = r(k-1)$$ $v$ is the number of elements in your ground set. $r$ is the ...
0
votes
0answers
48 views

Counting the 1s in each row of the incidence matrix of a 2-design

Consider the $2 - (4t-1, 2t, t)$ design where $t$ is an odd number and $A$ is the incidence matrix. I suspect that the number of elements with value $1$ in each row of $A$ is equal to $2t$ but I can't ...
1
vote
0answers
26 views

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. ...