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.
20
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} $ ...
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?
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$. ...
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$.
10
votes
2
answers
625
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 $...
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?
9
votes
1
answer
303
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 ...
7
votes
0
answers
207
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 ...
7
votes
2
answers
298
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 $...
6
votes
3
answers
641
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 ...
6
votes
1
answer
143
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 ...
5
votes
5
answers
545
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 ...
5
votes
0
answers
883
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 ...
4
votes
1
answer
1k
views
Solving a Diophantine equation related to Algebraic Geometry, Steiner systems and $q$-binomials?
The short version of my question is:
1)For which positive integers $k, n$ is there a solution to the equation $$k(6k+1)=1+q+q^2+\cdots+q^n$$ with $q$ a prime power?
2) For which positive ...
2
votes
3
answers
308
views
Constructions of $2-(v,3,3)$-designs
I am looking for ways to construct an infinite family of designs with parameters $2-(v,3,3)$ and apart from some doubling-type recursive constructions (such as in this paper) I haven't found anything ...
2
votes
2
answers
299
views
A graphic representation of classical unitals on 28 points
I would like to understand the geometry of the classical unitals.
They are block designs containing $q^3+1$ points and whose blocks have cardinality $q+1$, where $q$ is a prime power. For $q=2$ (if I ...
1
vote
0
answers
101
views
On a combinatorial design inspired by a football (soccer) tournament
Real-world inspiration. My younger son was playing a micro football (soccer) tournament this afternoon with $3$ other friends. Let's label the $4$ kids $0,1,2,3$. They played $3$ matches:
$\{0,1\} \...
0
votes
1
answer
157
views
"JigSaw Puzzle" on Set Family
One of my research problem can be reduced to a question of the following form
Given a set family $\mathcal{F}$ of $[n]$ , such that every element of $[n]$ lies in exactly $K$ sets in $\mathcal{F}$, ...