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.
120
questions
3
votes
0
answers
91
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
68
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
148
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
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 $...
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 ...
2
votes
2
answers
211
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
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 $...
1
vote
1
answer
307
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
304
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
464
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 ...
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 ...
0
votes
1
answer
49
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
345
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
125
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
287
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
305
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
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 ...
2
votes
2
answers
790
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
601
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 ...
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} $ ...
4
votes
0
answers
170
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
768
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
111
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
156
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
158
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 ...
7
votes
1
answer
483
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 ...
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 ...
11
votes
2
answers
800
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 ...
5
votes
2
answers
571
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 ...
2
votes
1
answer
207
views
Hitting sets (aka covers aka transversals) of Steiner triple systems
Does there exist a constant $c$ so that the lines of every Steiner
triple system on $v$ points can be covered by $cv$ points?
That is if $D \in STS(v)$ with point set $T=\{1,2,\ldots,v\}$ then ...
2
votes
0
answers
67
views
Point sets with tangents through every point
Let $D=(P,L)$ be either a $(v,k,\lambda)$-design or a near-linear space (or, more generally, any incidence structure with "points" and sets of points which are called "blocks" or "lines") and let $S \...
6
votes
3
answers
448
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 ...
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 ...
4
votes
1
answer
69
views
Balancing out edge multiplicites in a graph
Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge).
Is there some simple graph $H$ such that the $t$-fold ...
4
votes
2
answers
218
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$, ...
8
votes
3
answers
416
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 ...
1
vote
1
answer
809
views
Known results on cyclic difference sets
Is there any infinite family of $v$ for which all the $(v,k,\lambda)$-cyclic difference sets with $k-\lambda$ a prime power coprime to $v$ have been determined?
A subset $D=\{a_1,\ldots,a_k\}$ of $\...
0
votes
1
answer
238
views
a block design question: Does every special 1-design admit a partition which respects enough of the blocks?
Is it possible to show that every 1-design $D$ with $\lambda=4,k=4$ on $v$ points (for $v$ that is a multiple of $3$) contain some 1-design $Q$ with $\lambda=1,k=3$ on $v$ points such that every block ...
3
votes
1
answer
414
views
Ranks of higher incidence matrices of designs
In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is
$$
Rk_{2}(N)=v-(d_{p}+1),
$$
where $d_{p}$ is the ...
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 ...
9
votes
1
answer
530
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 $\...
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?
22
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), ...
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 ...
7
votes
0
answers
186
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 ...
2
votes
1
answer
164
views
Lower bounds on cardinality of a union of blocks in a design
Let $D$ be a $(v,k,\lambda)$-design (repeated blocks are allowed). I would like to get a lower bound on the cardinality of the union of $s$ blocks. A naive application of inclusion-exclusion gives $sk-...
4
votes
2
answers
609
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)$ ...
2
votes
2
answers
283
views
Resolvable designs from projective space
Resolvable designs are block designs with the additional property that the blocks can be partitioned into partitions of the points. It is easy to see that lines in affine space form a resolvable ...
3
votes
3
answers
684
views
Orthogonal Latin Square 6*6
I need to make remarks about Tarry's Proof for the nonexistence of 6x6 Latin Squares as part of my final exam for a class I'm in. Problem is, I can't find it ANYWHERE on the internet. I can only find ...
1
vote
5
answers
352
views
Pairwise balanced designs with $r=\lambda^{2}$
A while ago I asked how to construct an infinite family of $(v,b,r,k,\lambda)$-designs satisfying $r=\lambda^{2}$ and got very good answers from Yuichiro Fujiwara and Ken W. Smith.
Now I'd like to up ...