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
vote
0answers
26 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
66 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
44 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
21 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 ...
6
votes
3answers
272 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
22 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
26 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
10 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
27 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
21 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 ...
1
vote
1answer
36 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
173 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
47 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
47 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
24 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
76 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" ...
0
votes
0answers
54 views

How to count minimum rows required for combination of pairs

In another thread, I asked a question whether 75 binary options can be tested just by using 4 rows when arranged using an orthogonal array (i.e. contain all pairwise combinations). 4 is the lower ...
1
vote
1answer
47 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 ...
1
vote
1answer
41 views

Intersection of blocks of the symmetric BIBD $PG(d,q)$

The definition of a Balance Incomplete block design $(v,k,\lambda)$-BIBD can be found here. It is a well known fact (also see the link above) that every two blocks of a symmetric $(v,k,\lambda)$-BIBD ...
0
votes
1answer
50 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| ...
5
votes
2answers
289 views

Applications of design theory

I have recently started reading up on design theory, with the ultimate purpose of doing some original research in that area. I understand the mathematics fairly well, but am not understanding the ...
0
votes
0answers
17 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
44 views

Nullifying columns of a matrix by nullifying rows

Let $A$ be a real rectangular matrix. Each column of $A$ is a nonzero vector. Now each row of $A$ is nullified with probability $p$, all independently of each other. What is the probability that ...
0
votes
0answers
34 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
20 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
39 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
1answer
24 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
31 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 ...
0
votes
1answer
28 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 ...
0
votes
1answer
47 views

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

Can someone give an example of Symmetric Balanced Incomplete Block design with (56,7,1). That is v=b=56,k=r=7, $\Lambda = 1$.
4
votes
1answer
73 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
vote
0answers
26 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
0answers
42 views

A question regarding a combinatorial design.

I've been given the following question, and it almost seems too simple, so I'm not really too sure whether I'm just trying to overthink things. Let $B_0$ be a block of a $(v,k,1)$-design $(X, ...
0
votes
0answers
41 views

A proof regarding a symmetric $(v, k, \lambda)$-design.

I've been asked to prove the following; Consider a symmetric $(v,k,\lambda)$-design where $2k < v$. Prove that $2\lambda < k$. Now, being a symmetric design, I know that $v = b$, $r = k$, ...
4
votes
1answer
83 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 ...
1
vote
2answers
39 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 ...
0
votes
0answers
16 views

Estimate time it takes the minimum mean cycle cancelling algorithm to converge

This particular algorithm solves the circulation problem, equivalent to the minimum-capacitated flow. My question rather than only from this particular algorithm, but for combinatorial solutions in ...
4
votes
2answers
438 views

Minimum number of X-subsets needed to cover all K-subsets

Assume I have a universe of N elements. The question is: How many sets of size $X$ are needed to assure that every set of K elements is a subset of (at least) one of these sets (where $K \ll X \lt ...
0
votes
0answers
17 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
54 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
1answer
49 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
169 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
41 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
22 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. ...
1
vote
1answer
48 views

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. ...
1
vote
0answers
32 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 ...
0
votes
1answer
39 views

formula from 2s complement to decimal please

Hi what is the formula for an $n$ bit twos complement to decimal.. for example from $ n$ bit unsigned to decimal the formula is.. $\sum_{i=0}^{n-1} a_i 2^i$ from signed magnitude to decimal is ...
1
vote
0answers
51 views

Upper bound for constant weight code L(n,d,w), with n=128, d=4

I would like to find an upper bound: L(n,d,w) <= f(n,d,w) for a constant weight code L(n,d,w), where w is the maximum weight, d is the Hamming distance between codes, and n is the code length. I ...
2
votes
0answers
84 views

Out of all combinations (n,k), largest set such that each combination overlaps with others by d or less.

This problem is relevant to determining the number of discriminable combinations of components in a sensory perception task. Suppose that there are N components to choose from, and we are only ...