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.
110
questions
0
votes
1
answer
150
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}$, ...
- 239
1
vote
0
answers
71
views
Bounds for smallest non-trivial designs
Given $s>t\ge 2$, let $N(s,t)$ be the smallest integer $n>s$ such that there exists an “$(n;s;t;1)$-design” (i.e., a collection of $s$-subsets $e_1,\dots,e_m$ of $[n]:=\{1,\dots,n\}$, such that ...
- 2,322
1
vote
1
answer
108
views
On the existence of symmetric matrices with prescribed number of 1's on each row
We are considering the following problem:
Given an integer $n$ and a sequence of integers $r_i,\ 1\le i\le n$, with $0\le r_i\le n-1$ does there exists a symmetric matrix $A$ such that the diagonal ...
- 13
6
votes
1
answer
129
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 ...
- 231
9
votes
1
answer
268
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 ...
- 231
11
votes
2
answers
638
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.2k
3
votes
1
answer
143
views
Cycling through a general combinatorial design on $\omega$
This is a generalisation of an older question inspired by a football tournament (which does not have an answer yet).
Let $\frak P$ be a partition of $\omega$ into blocks, that is, pairwise disjoint ...
- 42.5k
1
vote
0
answers
93
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\} \...
- 42.5k
1
vote
1
answer
127
views
3-partition of a special set
$S_5$ is a set consisting of the following 5-length sequences $s$: (1) each digit of $s$ is $a$, $b$, or $c$; (2) $s$ has and only has one digit that is $c$.
$T_5$ is a set consisting of the following ...
- 25
5
votes
0
answers
785
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 ...
- 2,777
8
votes
3
answers
402
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
4
votes
1
answer
73
views
k-partite design
Is the following true? For every $n \geq 1, k\geq 2$, there is a set $S \subseteq [n]^k$ of size $|S| = n^2$ such that every two $k$-tuples in $S$ have at most one common entry.
Does anyone know if ...
- 408
1
vote
0
answers
53
views
Are sharper lower bounds known for these potentials on the sphere?
Fix a positive integer $\ell$. For $x_1,\dotsc,x_n\in S^{d-1}$, Venkov proved that
$$
\sum_{i=1}^n\sum_{j=1}^n(x_i\cdot x_j)^{2\ell}\geq\frac{(2\ell-1)!!(d-2)!!}{(d+2\ell-2)!!}\cdot n^2,
$$
with ...
- 7,325
3
votes
0
answers
49
views
Cliques in Incomplete block designs
I'm interested in inequalities that guarantee the presence of cliques in incomplete block designs. Here's the set-up:
I have an incidence structure $(V, B)$ which is an incomplete block design: $V$ is ...
- 10.9k
3
votes
0
answers
126
views
Linear combinations of special matrices
I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm.
Given an integer n, we want to combine some square input-matrices of size n in a way that is ...
- 63
4
votes
3
answers
504
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
1
vote
0
answers
46
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 ...
- 143
12
votes
1
answer
184
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., $ \...
- 445
11
votes
5
answers
485
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 ...
- 13.9k
3
votes
1
answer
125
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)$ ...
- 645
3
votes
1
answer
67
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 ...
- 131
1
vote
1
answer
64
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.
- 11
2
votes
0
answers
80
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 $\...
- 203
4
votes
3
answers
227
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 ...
- 379
5
votes
2
answers
181
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
3
votes
0
answers
128
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 ...
- 2,381
10
votes
2
answers
344
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
2
votes
1
answer
52
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
- 29
4
votes
1
answer
80
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 ...
- 503
3
votes
1
answer
113
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$...
- 20.6k
2
votes
1
answer
126
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 ...
- 9,108
8
votes
2
answers
522
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 ...
- 6,756
3
votes
2
answers
202
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 ...
- 241
7
votes
2
answers
334
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
2
votes
1
answer
89
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?
user91523
2
votes
1
answer
204
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 ...
- 53
2
votes
0
answers
74
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 ...
- 151
0
votes
0
answers
89
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 \...
- 42.5k
4
votes
3
answers
615
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 ...
- 1,616
2
votes
0
answers
185
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}$ ...
- 18.6k
3
votes
0
answers
90
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 $$
...
- 451
0
votes
0
answers
67
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 ...
- 607
1
vote
2
answers
141
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 ...
- 455
10
votes
2
answers
614
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
7
votes
0
answers
197
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 ...
- 18.8k
2
votes
2
answers
205
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 \} = \...
- 21
7
votes
2
answers
280
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 $...
- 18.8k
1
vote
1
answer
290
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
301
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 ...
- 94.7k
5
votes
1
answer
426
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 ...
