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

0
votes
0answers
8 views

An extemal combinatorial design question. “Weak” steiner stystems.

A Steiner system $S(t,k,\nu)$ is a collection $X$ of $\nu$ points and a collection of subsets of $X$ of size $k$ (frequently called blocks) such that each $t$ element subset of $X$ occurs in exactly ...
7
votes
2answers
231 views

Who conjectured that there are only finitely many biplanes, and why?

This question on MathOverflow motivates me to ask what the reasoning is behind the conjecture that there are only finitely many biplanes. More generally, it has been conjectured that for fixed ...
1
vote
1answer
25 views

Minimum length $m$ of $n$ string with pairwise Hamming distance $m/2$

I want to construct $n$ binary strings, each of the same length $m$ (to be determined), such that each pair of string has Hamming distance exactly $m/2$ (i.e. the strings disagree on $m/2$ positions). ...
3
votes
2answers
139 views

How large can a set of pairwise disjoint 2-(7,3,1) designs (Fano planes) be?

As wikipedia defines well, the Fano plane is a small symmetric block design, specifically a 2-(7,3,1)-design. The points of the design are the points of the plane, and the blocks of the design are the ...
5
votes
2answers
862 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
2answers
82 views

Scheduling gym class

My cousin came to me with this problem yesterday: She has 8 students in her gym class. In tomorrows class she has planned 4 different activities to rotate them through, each of which requires ...
0
votes
1answer
26 views

Is there an estimate for how much k-element subsets are needed to have any t-element subset in at least one of them?

Let's call $S(t, k, n)$ a minimal number of $k$-element subsets (blocks) of an $n$-element set $S$ with the property that each $t$-element subset of $S$ is contained in at least one block. Are there ...
3
votes
1answer
54 views

Forming clubs with an odd number of members, with each pair of clubs having an even number of members in common

Suppose we have a town with $n$ residents who love forming groups. To limit the number of groups, the town head decided: 1) Every club must have an odd number of members, and 2) Any two clubs must ...
2
votes
2answers
42 views

Known classes of Hadamard matrices

In the book Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices by Wallis et al., Appendix A of the chapter on Hadamard matrices gives a list of known classes of Hadamard matrices. However, ...
1
vote
0answers
44 views

Permutation of people and teams

Suppose 20 people attend an event where there is 4 different activities to do. Suppose we want to split the group in subgroups, each subgroup attending one session of an activity, then moving on the ...
0
votes
0answers
18 views

Constructing partial Steiner triple systems

Is there a general way to construct a partial Steiner triple system? There are algorithms to construct complete Steiner triple systems for $n \equiv 1, 3 \bmod 6$. From complete Steiner triple ...
4
votes
1answer
54 views

Steiner triple system with $\lambda \le 1$

What's the maximum number of 3-sized subsets of $[n]$ that can exist such that no two subsets contain more than one common element? When $n \equiv 1,3 \mod 6$ then this is equivalent to a Steiner ...
1
vote
1answer
46 views

Show that it is possible to guarantee a win by buying $14$ tickets.

You enter a lottery by picking a subset of three numbers from $\{1,2,3,4 \dots 14\}$ . You win a prize if you match at least two of the numbers on the winning ticket. Show that it is ...
2
votes
1answer
33 views

Balanced incomplete Block design for testing an experiment

I am reading something balanced incomplete block design from a book. I don't understand why is it easy to see that in this design Each vehicle is evaluated 8 times, each test driver evaluates 4 ...
2
votes
0answers
61 views

Is Einstein's riddle an example of a combinatorial design?

I have just learned a bit about combinatorial designs (BIBDs, constructing a ($b,v,r,k, \lambda$)-design, necessary conditions for a design, cyclic designs) and it reminded me a lot of Einstein's ...
1
vote
2answers
205 views

Grouping Problem

Suppose there are 9 strangers. We will assign them into 3 groups and each group has exactly 3 people. For each grouping, the strangers who were assigned into the same group will get to know each other ...
0
votes
2answers
120 views

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 ...
1
vote
1answer
29 views

a problem with tasters-combinatorial design theory

I have a collection of flavors being sampled in batches of $3$. I know that each pair of flavors occur together in exactly one batch. Also each flavor appears in the same number of batches. How can ...
0
votes
2answers
67 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
35 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 ...
0
votes
2answers
38 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: ...
1
vote
1answer
55 views

Symmetric 2-Designs

We just proved that for any symmetric 2-design (or Symmetric BIBDs as most literature puts it) with parameters $(v,k,\lambda)$, any two blocks intersects at exactly $\lambda$ points. Our lecturer ...
1
vote
1answer
58 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
74 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 ...
0
votes
1answer
70 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 ...
2
votes
1answer
69 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 ...
3
votes
3answers
57 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 ...
3
votes
1answer
102 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 ...
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 ...
7
votes
1answer
232 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
124 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
20 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 ? ...
1
vote
1answer
49 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 ...
2
votes
2answers
64 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 ...
2
votes
1answer
94 views

Hypergraph terminology

Suppose I have a hypergraph with vertices V and hyperedges H, where each hyperedge is a subset of V. I want to form a normal graph with vertex set V, where two vertices are adjacent if they lie in ...
-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
88 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
102 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
68 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 ...
0
votes
1answer
37 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 ...
8
votes
3answers
337 views

Symmetries of combinatorial structures.

Studying the automorphism groups of graphs/finite geometries/designs has been quite useful and important for both group theory and combinatorics. I know of the following books which cover the ideas ...
1
vote
0answers
54 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
34 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
1answer
37 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
26 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
150 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\}$ ...
1
vote
1answer
75 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
66 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
38 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
105 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" ...