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.

Filter by
Sorted by
Tagged with
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} $ ...
Gjergji Zaimi's user avatar
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?
Olga Dmitrieva's user avatar
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$. ...
David E Speyer's user avatar
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$.
Serifo  Blade's user avatar
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 $...
Gil Kalai's user avatar
  • 24.2k
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?
Igor Demidov's user avatar
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 ...
Matteo Cati's user avatar
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 ...
James Propp's user avatar
  • 19.4k
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 $...
James Propp's user avatar
  • 19.4k
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 ...
Jim Slattery's user avatar
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 ...
Matteo Cati's user avatar
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 ...
Taras Banakh's user avatar
  • 40.7k
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 ...
Alex Ravsky's user avatar
  • 4,092
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 ...
Daniel Litt's user avatar
  • 22.1k
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 ...
Felix Goldberg's user avatar
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 ...
Taras Banakh's user avatar
  • 40.7k
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\} \...
Dominic van der Zypen's user avatar
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}$, ...
abacaba's user avatar
  • 344