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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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,...
user avatar
  • 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 ...
user avatar
  • 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 &...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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]\; ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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? ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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&...
user avatar
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}$ ...
user avatar
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: $...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
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$. ...
user avatar
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 ...
user avatar
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$ ...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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,...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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}}\...
user avatar
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$ ...
user avatar

1
2 3 4 5
7