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
10 views

Combinatorial Designs - Pairwise Balanced Design

I've been asked to prove that a number of designs exist, but I'm having trouble conceptualizing how to actually go about starting these proofs. For starters, I've been asked to prove the existence ...
0
votes
0answers
16 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
13 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
0answers
23 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, ...
4
votes
1answer
46 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 ...
0
votes
0answers
26 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$, ...
0
votes
0answers
7 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$.
0
votes
2answers
22 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
69 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
7 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 ...
0
votes
0answers
13 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
40 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
42 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
141 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
30 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
17 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. ...
0
votes
0answers
22 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
22 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
0answers
10 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
34 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
42 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
76 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 ...
-1
votes
1answer
38 views

Small groups for church [closed]

I have a group of 20 families. Every quarter 5 families will meet together. The following three quarters ,famlies will be rotated so no families will be with the same families again. How do I set up ...
0
votes
0answers
30 views

Collection of subsets of $S$ where any $t$ have union equal to $S$ but any $t-1$ do not.

This recent question had me thinking about a generalization. Suppose we have a set of $n$ elements $S$. Suppose that we can assign the elements of $S$ to $b$ subsets $\{B_1,\ \cdots,\ B_b\}$ of $k$ ...
2
votes
1answer
58 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 ...
0
votes
1answer
50 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
2answers
181 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. ...
5
votes
3answers
219 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 ...
4
votes
1answer
99 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 ...
0
votes
1answer
41 views

Decomposing $K_v - K_u$ into Hamilton paths where $v = u^2 - u + 1$.

A decomposition of a graph $G$ into subgraphs $H$ is a collection of graphs all isomorphic to $H$ which are edge-disjoint in $G$ and together cover all the edges of $G$. Let $u \geq 1$ and $v = u^2 ...
1
vote
2answers
53 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 ...
5
votes
1answer
135 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 ...
7
votes
1answer
89 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 = ...
1
vote
1answer
410 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 ...
0
votes
1answer
638 views

fabric design using trigonometric functions

is there any trigonometric function or any others that involve trigonometric function, that draw cool fabric shapes or patterns? I have seen some pictures like but with trigonometric functions... ...
4
votes
3answers
553 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, ...
0
votes
1answer
45 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 ...
1
vote
1answer
25 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 = ...
2
votes
0answers
58 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 ...
4
votes
1answer
255 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 ...
3
votes
2answers
132 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
165 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 ...
2
votes
1answer
85 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$ ...
0
votes
1answer
79 views

Show that the complement of a difference set is a difference set

In combinatorics, a $(v,k,\lambda)$ difference set is a subset $D$ of cardinality $k$ of a group $G$ of order $v$ such that every nonidentity element of $G$ can be expressed as a product $d_1d_2^{-1}$ ...
1
vote
1answer
206 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 ...
4
votes
3answers
243 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 ...
-1
votes
1answer
90 views

Golf Round for a group of $12$

$12$ gentlemen wish to play $7$ rounds of golf. They want to split into $3$ groups of $4$ and play a different group each time with as much variety as possible without playing the same individuals ...
2
votes
0answers
38 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 ...
4
votes
1answer
209 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 ...
9
votes
3answers
262 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$. ...