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

9
votes
3answers
266 views

Question about members in sets

Let $A_1,A_2,...,A_n$ be sets with $k$ members in $A_i$ for every $1\le i\le n$. Suppose that the $A_i$ satisfy: 1) $|A_i\cap A_j| = 1$ for all $i\ne j$, 2) $A_1\cap A_2\cdots\cap A_n =\emptyset$. ...
7
votes
3answers
1k views

How do you create projective plane out of a finite field?

I have heard and read unclear mentions of links between projective planes and finite fields. Is it possible to construct a projective plane (or a Steiner system) starting out with a field? Could you, ...
7
votes
1answer
96 views

How many different ways can the signs be chosen so that $\pm 1\pm 2\pm 3 … \pm (n-1) \pm n = n+1$?

How many different ways can the signs be chosen so that $\pm 1\pm 2\pm 3 ... \pm (n-1) \pm n = n+1$? This is an extension of this question: For what $n$ can $\pm 1\pm 2\pm 3 ... \pm (n-1) \pm n = ...
6
votes
3answers
277 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 ...
5
votes
2answers
295 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 ...
5
votes
1answer
173 views

Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I ...
5
votes
1answer
327 views

A generalization of Kirkman's schoolgirl problem

A friend of mine asked me this question. "I have $3n$ elements, and I want to know which is the maximum number of triplets $(a,b,c)$ so that no two triplets have more than one element in common". The ...
4
votes
3answers
388 views

Orthogonal Latin Square 6*6

I need to make remarks about Tarry's Proof for the nonexistence of 6x6 Latin Squares as part of my final exam for a class I'm in. Problem is, I can't find it ANYWHERE on the internet. I can only find ...
4
votes
1answer
229 views

Finding a system of sets resembling the projective plane

For every natural number $r$ I wish to construct a family of sets $\mathcal{F}$ such that Every set in $\mathcal{F}$ has cardinality $r$ and is a subset of $\{1,2,\ldots,r^2-r+1\},$ For every ...
4
votes
2answers
442 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 ...
4
votes
1answer
176 views

the table at the end of Theoretical Computer Science Cheat Sheet

Theoretical Computer Science Cheat Sheet, created by Steve Seiden, is a hodgepodge of well-known mathematical theorems and notions. I can understand (or guess at least) many of them, but I'm not sure ...
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 ...
4
votes
1answer
84 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 ...
3
votes
1answer
196 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 ...
3
votes
2answers
159 views

Geometric solution to classic committee problem

Most people know the classic committe style problems. I read this solution to one of the basic version of the committe problem and was impressed, but not sure why it works. I was hoping someone ...
3
votes
2answers
124 views

combinatorics question from the real world

This is a real world scenario - please help. My brain hurts and I can't figure it out on my own. Suppose I host an event with the following constraints There will be exactly 5 lectures There will ...
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 ...
2
votes
1answer
77 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 ...
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 ...
2
votes
1answer
96 views

Pairwise balanced designs

Let $X$ be a finite set containing $v$ elements and $\lambda$ be a positive integer. Let $K$ be a set of positive integers. Further let there be a multiset $\mathcal{B}$ containing subsets of $X$ ...
2
votes
1answer
68 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 ...
2
votes
1answer
43 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
0answers
55 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 ...
2
votes
0answers
87 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 ...
2
votes
0answers
73 views

Configuration analogues of projective spaces?

In a configuration, each point is incident to the same number of lines and each line is incident to the same number of points. The Fano plane is a configuration, with 3 points on each line, and 3 ...
2
votes
0answers
42 views

Question related to designs where t= 2

1)Let D be a 2−(v,k,λ) design with b blocks and r blocks through every point. Let B be any block. How to show that the number of blocks that meet B is at least $k(r−1)^2/[(k−1)(λ−1)+(r−1)]$ 2) How to ...
1
vote
2answers
207 views

France Olympiad Team Selection Test 2005

In an international meeting of n ≥ 3 participants, 14 languages are spoken. We know that: - Any 3 participants speak a common language. - No language is spoken by more than half of the participants. ...
1
vote
1answer
53 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
2answers
57 views

Choosing sets of vectors on a complex sphere

Consider a complex $t$ dimensional unit sphere. Can we have $t$ sets of $2^t$ vectors $v_{ij}\in \Bbb C^t$ on the sphere where $i=1$ to $t$ and $j=1$ to $2^t$ on this with inner products satisfying ...
1
vote
1answer
321 views

perfect binary e-error correcting code

let C be a perfect binary e-error correcting code of length n. assume 0 is a symbol and that 0 vector is a codeword.show that P={1,2,...,n} together with supports of codewords of weight 2e+1form an ...
1
vote
1answer
40 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
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
548 views

What algorithm is a good to search a lotto design?

I'm interested what kind of algorithm would be suitable to find a lotto design? I saw that is has been proven that $L(39,7,4,7)=329$. This notation is explained in ...
1
vote
1answer
46 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
29 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?
1
vote
0answers
48 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 ...
1
vote
0answers
21 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 ...
1
vote
0answers
27 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 ...
1
vote
2answers
42 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 ...
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
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 ...
1
vote
1answer
42 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 ...
1
vote
0answers
52 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 ...
1
vote
1answer
28 views

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 = ...
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. ...
0
votes
1answer
172 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
1answer
23 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
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 ...
0
votes
1answer
58 views

combinatorial design problem

A combinatorial design has six varieties {1, 2, 3, 4, 5, 6}, and nine blocks of size 2. Every variety occurs in three blocks, and the design is simple. Prove that there are exactly two non-isomorphic ...