# Questions tagged [combinatorial-designs]

Design theory is the subfield of combinatorics concerning the existence and construction of highly symmetric arrangements. Finite projective planes, latin squares, and Steiner triple systems are examples of designs.

95
questions

**2**

votes

**0**answers

45 views

### Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...

**1**

vote

**0**answers

36 views

### Optimal choice of points to maximize majorities in a $t-(v,k,\lambda)$ design

Let us consider a design $\mathcal{D} = (V,\mathcal{B})$ with points in $V$ and blocks in $\mathcal{B}$. I am interested in the special case of a $t-(v,k,\lambda)$ design for $k=3$, i.e., all blocks ...

**12**

votes

**1**answer

171 views

### Ternary sequences satisfying $ x_i + y_i = 1 $ for some $ i $

Consider a set of strings $ {\mathcal S} \subset \{0, 1, 2\}^n $ satisfying the following two conditions: 1.) every string in $ {\mathcal S} $ has exactly $ k $ symbols from $ \{0, 1\} $ (i.e., $ \...

**11**

votes

**5**answers

441 views

### What are efficient pooling designs for RT-PCR tests?

I realize this is long, but hopefully I think it may be worth the reading for people interested in combinatorics and it might prove important to Covid-19 testing. Slightly reduced in edit.
The ...

**3**

votes

**0**answers

73 views

### Mutually orthogonal Latin hypercubes

A $d$-dimensional Latin hypercube with side length $n$ is a $d$-dimensional array with $n$ symbols such that along any line parallel to an axis, each symbol appears exactly once. Let us call a $(n,d)$ ...

**3**

votes

**1**answer

57 views

### For which sets of $(n, m, k)$ does there exist an edge-labelling (using $k$ labels) on $K_n$, such that every single-labelled subgraph is $K_m$?

Or, equivalently - for what sets of $(n, m, k)$ is it possible, for a group* of $n$ people, to arrange $k$ days of "meetings", such that every day the group is split into subgroups of $m$ people, and ...

**1**

vote

**1**answer

54 views

### Does there exist a non-degenerate symmetric combinatorial 3-design?

Is there a non-degenerate 3-design where the number of blocks equals the number of points?
Non-degenerate in this context means that a point is incident with at least 2 and at most #blocks-2 blocks.

**2**

votes

**0**answers

76 views

### Packings with block size equal to $6$?

In design theory the following is the defintion of a packing :
Definition : A $(v,k)$-packing is a pair $(V, \mathcal{B})$ of a finite set $V$ of cardinality $\vert V \vert = v$ and a finite set $\...

**4**

votes

**3**answers

212 views

### Best strategy for a combinatorial game

Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball.
Now suppose we are given 5 chances to pick 20 out of ...

**5**

votes

**2**answers

140 views

### Coloring in Combinatorial Design Generalizing Latin Square

I have a question about a combinatorial design very similar to a Latin Square, which is arising out of an open problem in graph theory. The design is an $n \times n$ matrix whose entries we want to ...

**3**

votes

**0**answers

115 views

### Graeco-Latin squares and outer-automorphisms

It is well known that $n=6$ is the only number greater than two in which there is no Graeco-Latin square of order $n$. It is also well known that $n=6$ is the only number greater than two in which ...

**10**

votes

**2**answers

327 views

### Lower bound for a combinatorial problem ($N$ students taking $n$ exams)

We have $N$ students and $n$ exams. We need to select $n$ out of the students using the grade of those exams. The procedure is as follows:
1- We set some ordering on the exams.
2- Going through this ...

**2**

votes

**1**answer

51 views

### Constructing Group Divisible Designs - Algorithms?

I am starting my research on group divisible designs this year and I wonder if there are any algorithms/software that help with constructions.
Thank you

**4**

votes

**1**answer

66 views

### Bounding the number of orthogonal Latin squares from above

As is usual, let $N(n)$ denote the maximum size of a set of mutually orthogonal Latin squares of order $n$. I am wondering what results hold that bound $N(n)$ from above; the only ones I can think of ...

**3**

votes

**1**answer

109 views

### On the existence of a certain graph/hypergraph pair

Let $V$ be a finite set, $G$ a simple graph with vertex set $V$, and $H$ a hypergraph (i.e., set of subsets) with vertex set $V$ satisfying the following three conditions:
each pair of elements of $V$...

**2**

votes

**1**answer

119 views

### Distinguishing points by sets of given size

The problem is:
Given a finite set $X$ with size $x$ and let $B$ denote a family of $k$-element subsets of $X$, called blocks. What is the smallest possible number $n$ of blocks such that every ...

**8**

votes

**2**answers

476 views

### Pfaffian representation of the Fermat quintic

It is known (see for instance Beauville - Determinantal hypersurfaces) that a generic homogeneous polynomial in $5$ variables of degree $5$ with complex coefficients can be written as the Pfaffian of ...

**3**

votes

**2**answers

145 views

### Known result about existence of $n$-vertex $k$-uniform $r$-hypergraphs?

Are there known results about $n,k,r$ such that $n$-vertex $k$-uniform $r$-regular hypergraphs exist? If this is too large a class of hypergraphs, what if $k=\tilde{\theta}(\sqrt{n})$? What if an ...

**7**

votes

**2**answers

240 views

### Minimum covers of complete graphs by $4$-cycles

I am interested in coverings of the (edge set of the) complete graph $K_n$ by cycles of length $4$. It is clear that such coverings exist for each $n \ge 4$. I need to find the minimum number of $4$-...

**2**

votes

**1**answer

81 views

### Relative difference sets?

Do you know how to find order of known groups with RDS or without? Or Known groups which have RDS or not? If there is a references to survey all researches?

**2**

votes

**1**answer

193 views

### Has this kind of design been studied before?

Consider a design $(X,\mathcal{B})$, satisfying:
Each block in $\mathcal{B}$ has the same size
The intersection of every two blocks has the same size
Of course, it is easy to find many examples of ...

**2**

votes

**0**answers

71 views

### A generalization of PBIBDs

A PBIBD is an incidence structure together with an underlying symmetric association scheme. One can relax the symmetry requirement, and ask for incidence structures with an underlying (not necessarily ...

**0**

votes

**0**answers

88 views

### Steiner-like systems with large edges and many intersections

Let $l\geq 3$ be an integer. Is there $n\in\mathbb{N}$ and a hypergraph $H=(\{1,\ldots,n\},E)$ with the following properties?
for all $e\in E$ we have $|e| \geq l$
$e_1\neq e_2 \in E \implies |e_1 \...

**4**

votes

**3**answers

449 views

### Does there exist a finite hyperbolic geometry in which every line contains at least 3 points, but not every line contains the same number of points?

It seems to me that the answer should be yes, but my naive attempts to come up with an example have failed.
Just to clarify, by finite hyperbolic geometry I mean a finite set of points and lines such ...

**2**

votes

**0**answers

180 views

### Non-uniform Ray-Chaudhuri-Wilson (generalized Fisher's inequality)

A $t$-design on $v$ points with block size and index $\lambda$ is a collection $\mathcal{B}$ of subsets of a set $V$ with $v$ elements satisfying the following properties:
(a) every $B\in\mathcal{B}$ ...

**3**

votes

**0**answers

88 views

### what is the largest real orthogonal design in $n$ variables?

A real orthogonal design in $n$ variables is an $m \times n$ matrix with
entries from the set $\pm x_1,\pm x_2,\cdots,\pm x_n$ that satisfies :
$$ A A^T = (x_1^2 + x_2^2 + \cdots x_n^2) I_m $$
...

**0**

votes

**0**answers

65 views

### Non-continuous behaviour when designing a repeated experiment

Assume one can perform measurements of an unknown quantity $\theta$ as
$$y = \theta + \epsilon(t),$$
where $\epsilon(t) \sim \mathcal{N}(0,1/t)$ is the measurement error when a time $t$ was spent to ...

**1**

vote

**2**answers

139 views

### Reference Request: “Resolutions” of $K_n$ for $n$ odd

A resolution (in the combinatorial design sense) of $K_{n}$ is a collection of sets of edges of $K_{n}$ so that within each set of edges, each vertex appears once, and over the entire collection, each ...

**10**

votes

**2**answers

583 views

### Seeking very regular $\mathbb Q$-acyclic complexes

This question was raised from a project with Nati Linial and Yuval Peled
We are seeking a $3$-dimensional simplicial complex $K$ on $12$ vertices with the following properties
a) $K$ has a complete $...

**7**

votes

**0**answers

182 views

### More about self-complementary block designs

For what odd integers $n \geq 3$ does there exist a self-complementary $(2n,8n−4,4n−2,n,2n−2)$ balanced incomplete block design?
By "self-complementary" I mean that the complement of each block is a ...

**2**

votes

**2**answers

180 views

### Minimal number of blocks in a $(n,n/2,\lambda)$ block design

A $(n,n/2,\lambda)$ block-design is a family $A_1,...,A_K$ of subsets of $[n]$ such that $|A_i|=n/2$ and for every $1 \leq i < j \leq n$ it holds that
$\#\{1 \leq k \leq K : i,j \in A_k \} = \...

**7**

votes

**2**answers

250 views

### Self-complementary block designs

For what $n$ does there exist a self-complementary
$(2n,4n-2,2n-1,n,n-1)$ balanced incomplete block design?
(All I know is that a self-complementary design with these parameters does exist for all $...

**1**

vote

**1**answer

251 views

### Covering designs where $v$ is linear in $k$

A $(v,k,t)$ covering design is a collection of $k$-subsets of $V=\{1,\ldots,v\}$ chosen so that any $t$-subset of $V$ is contained in (or "covered by") at least one $k$-set in the collection. ...

**3**

votes

**2**answers

297 views

### When do such regular set systems exist?

Let '$n$-set' mean 'a set with $n$ elements'.
May we choose $77=\frac16\binom{11}5$ 5-subsets of 11-set $M$ such that any 6-subset $A\subset M$ contains unique chosen subset? Positive answer to ...

**5**

votes

**1**answer

376 views

### reverse definition for magic square

Recently, I saw a question in see here which is so interesting for me. This question is as follows:
Is it possible to fill the $121$ entries in an $11×11$ square with the values $0,+1,−1$, so that ...

**6**

votes

**1**answer

302 views

### Are there infinite constructions for partial circulant hadamard matrices?

I believe that the circulant Hadamard conjecture (that there are no circulant Hadamard matrices of size greater than $4\times4$) is still open.
I also know that examples of $(n/2) \times n$ matrices ...

**0**

votes

**1**answer

41 views

### Vector version of balanced incomplete block designs

I am interested in finding out what is known about the following generalization of balanced incomplete block designs (BIBDs):
"What is the maximum size of a collection $B$ of $v$-dimensional unit ...

**4**

votes

**0**answers

330 views

### Existence of a block design

Let $\ell$ be an integer parameter. I want to ask the existence of the following design: There is a universal constant $\beta < 1$ such that for all sufficiently large $\ell$, the following holds:
...

**3**

votes

**0**answers

117 views

### A question on the behavior of intersections of certain block design

Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that:
$\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$.
$\forall i \neq j \in [m]$, $|S_i \cap S_j| \...

**2**

votes

**4**answers

236 views

### What is the correct term for “co-covering” designs

An (n, k, l) covering design is a family of k-subsets of an n-element set such that every l-subset is contained in at least one of them. Now, what is the correct term for a family of k-subsets such ...

**2**

votes

**1**answer

274 views

### Existence of Steiner system designs given $n,k,t$

I am familiar with the recent Keevash paper here which proves that given some $t,n,k,\lambda$ then provided standard divisibility conditions hold, and $n$ is suitably large, there exists a $t-(n,k,\...

**6**

votes

**2**answers

776 views

### Combinatorial designs textbook recommendation

Good evening, I am currently taking a class which has combinatorial designs as the first topic, we are using Peter Cameron's book Designs, Graphs, Codes and their Links which I am finding extremely ...

**2**

votes

**2**answers

519 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**4**

votes

**2**answers

468 views

### covering designs of the form $(v,k,2)$

A covering design $(v,k,t)$ is a family of subsets of $[v]$ each having $k$ elements such that given any subset of $[v]$ of $t$ elements it is a subset of one of the sets of the family. A problem is ...

**38**

votes

**2**answers

1k views

### How close can one get to the missing finite projective planes?

This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...

**4**

votes

**0**answers

168 views

### Reduction argument from a general vertex set V(G) to a prime power in Prof. Keevash's proof on the Existence of Designs

The proof flow of the paper "On the Existence of Designs" by Prof. Keevash as I understand it is the following:
-- Reduction from the general case to $V = \mathbb{F}_{p^a}$ (Lemma 6.3)
-- Covering ...

**35**

votes

**1**answer

713 views

### What measurable quantity can constrain the number of odors human can discriminate?

This is not a very typical MO question, but I hope you bear with me. It concerns a recent disagreement in the biology literature about how many different odors humans can discriminate. The authors of ...

**0**

votes

**1**answer

109 views

### All $2$-designs arising from the action of the affine linear group on the field of prime order

Let $p$ be a prime and $\mathbb{Z}_p$ denote as usual the field of order $p$. Let $AL(p)$ be the affine linear group $\{x\mapsto ax+b \;|\; a\in \mathbb{Z}_p\setminus \{0\}, b\in\mathbb{Z}_p\}$. For a ...

**4**

votes

**0**answers

136 views

### Number of cyclic difference sets

A subset $D=\{a_1,\ldots,a_k\}$ of $\mathbb{Z}/v\mathbb{Z}$ is said to be a $(v,k,\lambda)$-cycic difference set if for each nonzero $b\in\mathbb{Z}/v\mathbb{Z}$, there are exactly $\lambda$ ordered ...

**1**

vote

**1**answer

136 views

### Number of points in an intersecting linear hypergraph

I first asked the question below at math.stackexchange.com ( https://math.stackexchange.com/questions/920442/number-of-points-in-an-intersecting-linear-hypergraph ) but somebody suggested I ask it in ...