Questions tagged [combinatorial-designs]
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 of experiments.
315
questions
0
votes
0
answers
17
views
For a Steiner system, how many blocks intersect exactly one position of a specific block?
Consider Steiner system $S(2,k,v)$ with $2 = t < k < v$, a family of $k$-subsets of finite set $S$ with $|S|=v$ such that each $t$-subset of $S$ is contained in exactly one block.
A paper I'm ...
- 31
4
votes
3
answers
70
views
maximal number of independent subsets (bitstrings with uniform distribution)?
Let $B=\{0,1\}^n$ be the set of length $n$ bit-strings with the uniform distribution, and let $\mathcal{F}=\{f:B\to \{0,1\}\}$ be the set of all binary functions on $B$.
What is the maximal size of an ...
- 8,325
0
votes
0
answers
11
views
Help understanding linear contrasts in randomized block design?
I have been given the following question:
"An experiment is conducted to compare the yield from one field, where samples from
the field are placed in plant pots with different levels of nitrogen ...
- 197
4
votes
0
answers
34
views
Organizing Meetups Where People Meet Exactly Once [duplicate]
Okay, I've seen this question asked multiple ways, but I cannot get my head wrapped around it! With 9 people, I can have a schedule where each person participates in 4 meetings of 3 people per meeting,...
- 141
0
votes
1
answer
38
views
How to sort into X bins Y times with minimum overlap?
Let's say I'm hosting a series of dinner parties for a total of $N$ guests. Each night, there are $X$ tables, and we are meeting for a total of $Y$ nights.
I want to preassign the guests to tables ...
- 3,898
-1
votes
0
answers
13
views
Incident Matrix and Concurrance Matrix
How would I find the incident and concurrance matrix for the below?
\left(\begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 2 & 2 \\
1 &...
- 29
0
votes
0
answers
24
views
Latin square analogy - finding a balanced arrangement of elements
I've come across a practical problem in discrete mathematics, and I suspect that some clever mind knows a better solution than brute force.
Imagine that we are hosting a competition in which each of ...
- 101
-1
votes
1
answer
74
views
Showing that whether a construction is the maximum /minimum or not
16 friends decided to form clubs. Each club will have 4 members, and any two clubs may have at most two member in common. What is the greatest/least possible number of clubs they can form.
Got 7 ...
- 697
9
votes
1
answer
315
views
Coloring a Generalized Latin Square
Suppose we have an $n \times n$ array, and there is a decomposition $\mathcal{A}$ of its coordinates $a_{i,j}$ into sets $A_m$ as follows:
If $a_{i,j} \in A_m$, then $a_{j,i} \in A_m$. So they're ...
- 601
0
votes
1
answer
49
views
Real World Problem - Groups Visiting Various Stations
Context: This is a real world problem that I am trying to solve that I would appreciate some help with - I'm sure there's a Mathematical concept that will help me, but I'm struggling to remember back ...
- 4,955
5
votes
1
answer
63
views
Minimum swaps necessary for every person to meet every other person at every location
The setting:
There are 9 people.
There are 3 locations.
At any time, there are 3 people at each location.
People can only swap locations at the same time.
The goal:
Every person visits each ...
- 153
1
vote
0
answers
22
views
Construction of STS with maximal complete arc
By definition, a Steiner Triple System (STS) is a $t-(v,k,\lambda)$ design with blocks of size 3 ($k=3$) such that each pair of points meets in exactly 1 block ($t=2$ and $\lambda=1$). Let us denote ...
- 1,311
3
votes
0
answers
115
views
How many collections of four points, no three of which are collinear, are there in a finite affine plane?
Suppose the order of the finite affine plane is $n\geq 2$ (that is, each line has exactly $n$ points). I claim there are
$$\binom{n^{2}}{4} - (n^{2}+n)\left[\binom{n}{4}+\binom{n}{3}(n^{2}-n)\right]\; ...
- 2,908
0
votes
1
answer
52
views
Optimal Card Game Schedule
I have the responsibility of creating a schedule for a card game league. While creating the schedule, the following problem has arisen...
Let $n,g,s \in \mathbb{N+}$ where $s \leq n$.
Let $P = \{1, 2, ...
- 213
0
votes
1
answer
49
views
How to implement a sampling criterion to obtain maximally distinct bit patterns from all possible bit sequences?
I need to choose $n$ samples of $x$-bit sequences. What is the criterion which will maximize the "information content" or ensure that the $n$ chosen bit sequences have maximal separation ...
2
votes
1
answer
54
views
Number of 3-element subsets with only 1 common element
In a party, there are $n$ guests attending where $3$ guests can seat around a table. What is the maximum number of ways in which they can be seated so that no $2$ guests sit together more than once?
...
- 1,242
1
vote
2
answers
69
views
Number of triangles in $K_n$ that don't share any edges
Consider $K_n$ the complete graph with n vertices, $n\ge3$.
Prove that there is a set $S$, of triangles from $K_n$ such that there are not $2$ triangles from $S$ that share an edge and $|S|\ge\frac{(n-...
- 758
3
votes
1
answer
79
views
In search of the most symmetric Steiner quadruple systems
Hanani's original 1960 proof of the existence of Steiner quadruple systems $SQS(n)$ for all $n\equiv2,4\bmod6$ involves explicitly constructing an $SQS(14)$ and an $SQS(38)$ in what is otherwise a ...
- 89.6k
2
votes
0
answers
41
views
Latin squares with one cycle type?
Now cross-posted to MO because of no answers here.
The following Latin square
$$\begin{bmatrix}
1&2&3&4&5&6&7&8\\
2&1&4&5&6&7&8&3\\
3&4&...
- 61
0
votes
0
answers
50
views
Minimum size set to guarantee m-matches on lottery
Consider a lottery where you pick a set $S_{pick}$ of $k$ numbers from a total of $N$ numbers. Then a set $S_{draw}$ of $n$ numbers ($n<=k<N$) is draw and if all the numbers from the $S_{draw}$ ...
- 1
0
votes
0
answers
21
views
traffic assignment
Here are $m$ cities $C_1,\cdots,C_m$. The road connecting $V_i$ and $V_j$ is denoted as $E(i,j)$. Now there are $n$ trains $T_1,\cdots,T_n$. For each train $T_i$, it corresponds to two parameters: $...
- 9
0
votes
0
answers
34
views
Could someone tell me how such a secret sharing scheme could work?
Taking into account a post here which is the following, I want to make some questions.
A secret sharing scheme is a method of distributing finite pieces of information (called shares $\alpha_i$) among ...
- 377
0
votes
2
answers
127
views
how to construct a binary matrix with given row and column distribution
I need to construct an $m \times n$ binary matrix $B$ from a given row and columns distribution.
What algorithms can be used for this? As a concrete example : $B$ a $12 \times 63$ matrix with row ...
- 790
4
votes
3
answers
234
views
Maximally unique beach volleyball games
There are 24 players, 12 men and 12 women. A team is a set of 1 man and 1 woman. A (beach volleyball mixed) game is a set of 2 different teams, i.e. players are unique in those teams.
Let's denote men ...
2
votes
2
answers
116
views
To find the minimum number of $3$-toppings pizza so that it meets the demand of my friend!
In a pizza shop they are offering $3$-toppings pizza with $10$ choices of toppings. A friend has decided that two of the three toppings on the pizza must be what they want but I don't know which two ...
- 157
5
votes
0
answers
164
views
Combinatorial design to compress a Boolean lattice without confusing small sets
Is there a kind of combinatorial design that controls the sizes of small unions of the blocks?
I'm looking for a set $B$ of $|B|=b$ blocks, where $b\sim100$, which are subsets of a set $X$ of $|X|=v$ ...
- 26.9k
0
votes
0
answers
24
views
The goal is to obtain the minimum number of subsets of size s from a set of items of size a, so that pair of items should appear in exactly n subsets
I am not a mathematician, I hope the question is sufficiently clear and has a solution.
The use case is the design of an online experiment.
Parameter a is ...
- 145
0
votes
0
answers
20
views
How to find the maximum number of edges that exactly contain x vertices in a k-uniform hypergraph？
Help me please. I really need some articles about this problem. Or are there any other extremal k-uniform hypergraph about this problem?
0
votes
0
answers
24
views
How can I show that $(v, k, \lambda)$-design exists if and only if $(v, v-k, b + \lambda - 2r)$-design exists?
I am still stuck on the proof, so here is my progress:
$(\leftarrow)$ : Suppose $(v,v-k,b+\lambda-2r)$-design exists.
Then $k = v-k$ and $\lambda = \lambda + b - 2r$.
This makes $v = 2k$ and $b = 2r$.
...
- 121
0
votes
0
answers
28
views
How can canasta teams can be set up for $6$ rounds so that the same players are on the same team as few times as possible?
Playing canasta we have 6 different players making 2 teams of 3 players. We play 6 rounds, switching players each time. How can we set that up so that the same players are on the same team as few ...
- 1
1
vote
1
answer
46
views
Edge cover in a regular uniform hypergraph
Let $H = (V,E)$ be a $15$-uniform hypergraph. That is, every edge contains exactly $15$ vertices. Suppose $|V| = 63$ and $|E| = 21$. Moreover, assume that every vertex is contained in exactly $5$ ...
- 1,137
2
votes
1
answer
63
views
How to find a set of combinations of 5 that cover all the combinations of 3 once?
I have a set of n numbers (e.g. 1 to n). For the sake of clarity, in the remaining I will use n = 10.
From these 10 numbers there is $\binom{10}{3} = 120$ combinations of 3, for instance (1, 3, 5), (3,...
- 23
1
vote
1
answer
34
views
How many different $2n$-block $A_i$ can we construct such that $|A_i\cap A_j|=n$?
I hope I can explain my problem properly. sorry if it is ambiguous or is not well defined.
Suppose $A_0=\mathsf{aa\dots a bb\dots b}$ which each $\mathsf{a}$ and $\mathsf{b}$ repeated $n$-times. By ...
- 7,809
1
vote
1
answer
45
views
Finding a bound for the number of cards in a deck
A deck of cards is such that each card has $n$ images drawn inside it and such that each pair of cards has exactly one image in common, but no image is present on all the cards. The question is to ...
- 107
2
votes
0
answers
47
views
Why does any non-trivial permutation of ${\rm Aut}(S(5,6,12))$ at least alter $8$ symbols?
In my study on Mathieu Groups I came across the following article.
R.G. Stanton states on the second page:
... thus $M_{12}$ is $5$-fold transitive and so has order $m_{12} = 12\cdot 11\cdot 10\cdot ...
- 175
1
vote
0
answers
16
views
"Orthogonal" Steiner Systems
Let $1\leq t\leq k\leq v$ be integers.
A Steiner system $S:=S(t,k,v)$ is a collection of subsets $K$ of size $k$ of a set $V$ of size $v$ such that for every subset $T\subseteq V$ of size $t$, there ...
- 3,403
1
vote
1
answer
62
views
Number of combinations to introduce people within certain groups
I am trying to calculate a combination of unique people inside of the different groups. Nonetheless, I have not observed any formula to achieve my intention. There are 4 different groups and each ...
- 11
0
votes
3
answers
142
views
10 events, 10 teams
I need help scheduling an event where there are 10 activities and 10 teams. Each team plays against another team for each activity. Each team must play each activity. Ideally, they would not play ...
- 27
1
vote
0
answers
109
views
What is the relationship between covering designs (La Jolla Covering Repository) and linear block codes?
In many papers I have been reading, bioengineers are utilizing covering sets from Dan Gordon's La Jolla Covering Repository to design custom Modified Hamming Codes (MHD).
These MHDs have custom ...
- 203
4
votes
0
answers
67
views
Combinatorial design related to scheduling group activities (everyone tries every activity, no pair is together twice)
Trying to solve this problem led me to consider the following generalization.
Let $g$ and $p$ be positive integers. Imagine that you own $g$ distinct board games, where each game requires exactly $p$ ...
- 56.8k
3
votes
0
answers
45
views
"Unbalanced" combinatorial designs
A combinatorial design on a set $X$ (which I'll call players) of size $n$ is a collection of subsets of $X$ (which I'll call games) such that:
Each player is in exactly $r$ games.
Each game contains ...
- 26.3k
0
votes
1
answer
109
views
How can I arrange a group of people at tables and switch them around so that no two ever meet twice? [closed]
Say I have 5 tables of 4 people (i.e. 20 people in total) and a different game at every table. We play one round of games (so each table plays one unique game) and then switch tables. Is it possible ...
- 35
0
votes
2
answers
97
views
Properties of submodular functions
I was working on submodular set functions, and I came across a property on Wikipedia, that I was not able to prove/find any reference for. On the Wikipedia article on submodular set functions, Under ...
1
vote
2
answers
133
views
Split $\{1,...,3n\}$ into triples with $x+y=5z$ - no solutions?
Following on from Split $\{1,2,...,3n\}$ into triples with $x+y=4z$ and For which $n\in\Bbb N$ can we divide $\{1,2,3,...,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,...
- 47.6k
4
votes
0
answers
390
views
Split $\{1,2,...,3n\}$ into triples with $x+y=4z$
A similar question appeared last week.
For which $n\in\Bbb N$ can we divide $\{1,2,3,...,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?
In this ...
- 47.6k
7
votes
0
answers
75
views
What is the "fairly easy" proof that the automorphism group of a Steiner system $S(t,k,n)$ is highly transitive?
I was reading this writeup on the Mathieu groups, and got stuck on a statement in page 2:
The Mathieu groups $M_{11}, M_{12}, M_{22}, M_{23},$ and $M_{24}$ are defined as follows:
$M_{11}=\{\sigma\...
- 11.6k
46
votes
2
answers
1k
views
For which $n\in\Bbb N$ can we divide $\{1,2,3,...,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?
For which $n\in \mathbb{N}$ can we divide the set $\{1,2,3,\ldots,3n\}$ into $n$ subsets each with $3$ elements such that in each subset $\{x,y,z\}$ we have $x+y=3z$?
Since $x_i+y_i=3z_i$ for each ...
- 86.2k
0
votes
1
answer
57
views
Minimum for combinatorial sortingproblem
I'm stuck with a combinatorial problem, maybe one of you can help me out, thanks in advance. So heres the problem:
Consider tuples $(i,j)\in \{1,...,N_1\}\times\{1,....,N_2\}=A$. Let $S_1,...,S_x$ be ...
- 300
1
vote
0
answers
24
views
Identify my $\{-1,1\}$-matrix
Let $n$ be a positive integer. Let $\mathbb{F}$ be a field not of characteristic $2$.
Let $\mathbf{M} \in \mathbb{F}^{2^{n-1} \times n}$ be a matrix with entries from $\{-1_{\mathbb{F}},1_{\mathbb{F}}\...
0
votes
1
answer
73
views
Construct a projective plane of order 7 [closed]
I am meant to construct a projective plane of order 7. Where the points are the one-dimensional subspaces of $\mathbb{Z_7^3}$. And the lines the two-dimensional subspaces. Incidence is given by $\in$ ...
- 353