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

10
votes
3answers
2k 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, ...
9
votes
3answers
267 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$. ...
8
votes
3answers
346 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 ...
7
votes
1answer
234 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. $(AAAA-...
7
votes
2answers
239 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 $\...
7
votes
1answer
116 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 = n+...
7
votes
0answers
128 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 ...
5
votes
2answers
910 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 ...
5
votes
3answers
547 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 ...
5
votes
2answers
429 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
211 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
370 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
1answer
248 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
526 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 N$)...
4
votes
1answer
264 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
83 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
100 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 ...
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 ...
3
votes
2answers
164 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 ...
3
votes
2answers
180 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
1answer
75 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 ...
3
votes
3answers
63 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
2answers
129 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
99 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 ...
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 M_n(1,-...
3
votes
1answer
57 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 ...
3
votes
1answer
41 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
2answers
44 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, ...
2
votes
1answer
71 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 ...
2
votes
1answer
163 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\}$ ...
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 ${10 ...
2
votes
1answer
109 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
34 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
1answer
106 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
2answers
68 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
0answers
64 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 ...
2
votes
1answer
92 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
92 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
97 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
87 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
49 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
243 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
2answers
92 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 ...
1
vote
2answers
212 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 ...
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 ...
1
vote
1answer
83 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
1answer
48 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 possible ...
1
vote
2answers
59 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
387 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
31 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). ...