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.
117
questions
55
votes
21
answers
14k
views
Linear algebra proofs in combinatorics?
Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
39
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} $ ...
- 84.6k
35
votes
1
answer
765
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 ...
- 5,928
23
votes
2
answers
3k
views
Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?
The following problem is homework of a sort -- but homework I can't do!
The following problem is in Problem 1.F in Van Lint and Wilson:
Let $G$ be a graph where every vertex
has degree $d$. ...
- 150k
21
votes
1
answer
2k
views
Octonions and the Fano plane.
Does the Fano plane mnemonic for octonion multiplication have any deeper meaning?
http://upload.wikimedia.org/wikipedia/commons/2/2d/FanoPlane.svg
The symmetry group of the Fano plane is PSL(2,7), ...
- 3,681
16
votes
3
answers
1k
views
Fano plane drawings: embedding PG(2,2) into the real plane
By a drawing of the Fano plane I mean a system of seven simple curves and
seven points in the real plane such that
every point lies on exactly three curves, and every curve contains
exactly three ...
- 22.6k
13
votes
2
answers
775
views
Is there a tournament schedule for 18 players, 17 rounds in groups of 6, which is balanced in pairs?
We are interested in a solution to the following scheduling problem, or any information about how to find it or its existence. This one comes from real life, so you will not only be helping a ...
- 233
12
votes
5
answers
563
views
Intersecting 4-sets
Is it possible to have more than $N = \binom{\lfloor n/2\rfloor}{2}$ subsets of an $n$-set, each of size 4, such that each two of them intersect in 0 or 2 elements?
To see that $N$ is achievable, ...
- 37k
12
votes
4
answers
3k
views
What are the major open problems in design theory nowaday?
I gather that the question whether the Bruck-Chowla-Ryser condition was sufficient used to top the list, but now that that's settled - what is considered the most interesting open question?
12
votes
3
answers
3k
views
Status of Hadamard matrix conjecture
I would like to know if any progress has been made on Hadamard conjecture :
Hadamard matrix of order $4k$ exists for every positive integer $k$.
- 121
12
votes
1
answer
190
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., $ \...
- 479
11
votes
4
answers
5k
views
Constructing Steiner Triple Systems Algorithmically
I want to create STS(n) algorithmically. I know there are STS(n)s for $n \cong 1,3 \mod 6$. But it is difficult to actually construct the triples. For STS(7) it is pretty easy and but for larger n I ...
- 133
11
votes
2
answers
773
views
On the Steiner system $S(4,5,11)$
Is there a nice way to partition the edges of the complete $5$-uniform hypergraph
on $11$ vertices into $7$ copies of the Steiner system $S(4,5,11)$? If this is
obvious or elementary, I apologize in ...
user48028
11
votes
5
answers
489
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 ...
- 14.1k
11
votes
2
answers
652
views
$\mathbb Z/p\mathbb Z=A\cup(A-A)$?
$\newcommand{\Z}{\mathbb Z/p\mathbb Z}$
Can one partition a group of prime order as $A\cup(A-A)$ where $A$ is a subset of the group, $A-A$ is the set of all differences $a'-a''$ with $a',a''\in A$, ...
- 22.6k
11
votes
1
answer
295
views
Has every finite affine plane the Doubling Property?
Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms:
Any distinct points $x,y\...
- 40.2k
11
votes
1
answer
866
views
Which Steiner systems come from algebraic geometry?
This question is motivated by the ongoing discussion under my answer to this question. I wrote the following there:
A $(p, q, r)$ Steiner system is a collection of $q$-element subsets $A$ (called ...
- 21.9k
10
votes
4
answers
5k
views
Maximum determinant of $\{0,1\}$-valued $n\times n$-matrices
What's the maximum determinant of $\{0,1\}$ matrices in $M(n,\mathbb{R})$?
If there's no exact formula what are the nearest upper and lower bounds do you know?
- 101
10
votes
2
answers
618
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 $...
- 24.1k
10
votes
2
answers
352
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 ...
- 598
9
votes
1
answer
527
views
Does $(\mathbb{Z}/n\mathbb{Z})^2$ ever admit a difference set when $n$ is odd?
A difference set of a group $G$ is a subset $D\subseteq G$ with the property that there exists an integer $\lambda>0$ such that for every non-identity member $g$ of $G$, there exist exactly $\...
- 7,525
9
votes
1
answer
299
views
Construction of skew-Hadamard matrix of order 292
I am currently looking into how to construct a skew-Hadamard matrix of order 292. Where can I find such construction?
According to multiple papers (e.g. Koukouvinos and Stylianou - On skew-Hadamard ...
- 241
8
votes
3
answers
411
views
Latin squares with one cycle type?
Cross posting from MSE, where this question received no answers.
The following Latin square
$$\begin{bmatrix}
1&2&3&4&5&6&7&8\\
2&1&4&5&6&7&8&3\\...
- 168
8
votes
3
answers
414
views
colorings of ${\mathbb Z}^d$ with constraints
For a lattice $\mathbb Z^d$, denote by lattice line any line that contains two (and thus infinitely many) lattice points.
For $2\le k<n$, define a $(n,k)$-coloring, or $C_d(n,k)$ for short, as ...
- 13.1k
8
votes
2
answers
549
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 ...
- 7,100
7
votes
2
answers
370
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$-...
- 337
7
votes
2
answers
295
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 $...
- 19.1k
7
votes
1
answer
462
views
Is there a simple proof that there is no five mutually orthogonal Latin squares of order 6?
It is well known that there is a projective plane of order $n$ if and only if
there exist a set of $n-1$ mutually orthogonal Latin squares. The first nontrivial
case is $n=6$, which fails because of ...
- 333
7
votes
1
answer
1k
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 ...
- 9,818
7
votes
2
answers
278
views
Nonextendable partial Hadamard matrices
An $m\times n$ matrix with entries $\pm 1$ is said to be partial
Hadamard if any two rows are orthogonal. See
Reference for partial Hadamard matrices. Given $n\equiv
0\,(\mathrm{mod}\,4)$, what is the ...
- 48.7k
7
votes
0
answers
205
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 ...
- 19.1k
7
votes
0
answers
185
views
Tenacious structure
Let $\def\A{\mathbb A}\def\F{\mathbb F}\F_3$ be the Galois field with three elements and let $\A^d=\A^d(\F_3)$ be the affine space of dimension $d$ over $\mathbb F_3$ —the subject is combinatorics and ...
- 46.5k
6
votes
2
answers
1k
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 ...
- 1,825
6
votes
3
answers
440
views
Isomorphism testing in STS(13)
What is the simplest isomorphism invariant which can distinguish between the two non-isomorphic Steiner triple systems on $13$ points?
Train structure and cycle structure, as described here, do the ...
- 6,832
6
votes
1
answer
142
views
How to construct a skew Hadamard matrix of order 756?
Where can I find the construction for a skew Hadamard matrix of order 756?
According to multiple papers (e.g. Koukouvinos and Stylianou - On skew-Hadamard matrices and Seberry - On skew Hadamard ...
- 241
6
votes
3
answers
636
views
Meeting management
A friend wants to have ten meetings of six people every day for five days with no pair of people meeting twice. Is this possible? It appears to be a question about maximal decomposition of a complete ...
- 69
6
votes
0
answers
3k
views
A generalization of covering designs and lottery wheels
This question is inspired by a recent problem . A $(v,k,t)$ covering design is a pair $(V,B)$ where $V$ is a set of $v$ points and $B$ is a family of $k$ point subsets (called blocks) such that ...
- 29.9k
5
votes
5
answers
495
views
Is every uniform hyperbolic linear space infinite?
I start with definitions.
Definition 1. A linear space is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ satisfying three axioms:
(L1) for any distinct ...
- 40.2k
5
votes
2
answers
544
views
Can we sometimes define the parity of a set?
Suppose that ${n\choose k}, {n-1\choose k-1}, \ldots, {n-k+1\choose 1}$ are all even. (This happens for example if $k=2^\alpha-1$ and $n=2k$.) In this case, can we select ${n\choose k}/2$ sets of size ...
- 18.7k
5
votes
1
answer
2k
views
What is the largest number of k-element subsets of a given n-element set S such that…
Given a set S of n elements. What is the largest number of k-element subsets of S such that every pair of these subsets has at most one common element?
5
votes
1
answer
453
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 ...
5
votes
1
answer
306
views
Block design question
Given fixed values for $d \leq k \leq v$. I would like to find a set $B$ of $d$-sets of $[v]$ with the following properties:
Every $k$-set of $[v]$ contains at least one element of $B$
Every element ...
- 3,397
5
votes
2
answers
191
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 ...
- 409
5
votes
0
answers
881
views
The existence of big incompatible families of weight supports
In 2018 Mario Krenn posed this originated from recent advances in quantum physics question on a maximum number of colors of a monochromatic graph with $n$ vertices. Despite very intensive Krenn’s ...
- 3,997
4
votes
2
answers
568
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 ...
- 1,825
4
votes
3
answers
232
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 ...
- 381
4
votes
2
answers
607
views
Is Ryser's conjecture on permanent minimizers still open?
Let $A(k,n)$ be the set of $\{0,1\}$ matrices of order $n$ with all their line sums equal to $k$.
Conjecture number 5 on the list from Minc's book, attributed to Ryser, says that if $A(k,n)$ ...
- 6,832
4
votes
2
answers
216
views
Is the domination number of a combinatorial design determined by the design parameters?
Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$.
Is $\gamma(L(D))$ determined only by $v,k$, ...
- 6,832
4
votes
3
answers
663
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 ...
- 43
4
votes
1
answer
1k
views
"Codes" in which a group of words are pairwise different at a certain position
I read the following problem, claimed to be in the IMO shortlist in 1988:
A test consists of four multiple choice problems, each with three options, and the students should give an unique answer to ...
- 2,521