All Questions
Tagged with design-theory or combinatorial-designs
125 questions
2
votes
0
answers
84
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
91
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 \...
- 48.9k
4
votes
3
answers
781
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,701
2
votes
0
answers
204
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}$ ...
- 20.2k
3
votes
0
answers
92
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
69
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 ...
- 617
1
vote
2
answers
149
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 ...
- 525
10
votes
2
answers
632
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.7k
8
votes
0
answers
210
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.7k
2
votes
2
answers
217
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
307
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.7k
2
votes
1
answer
319
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 ...
- 109k
5
votes
1
answer
485
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 ...
8
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 ...
- 10.4k
0
votes
1
answer
50
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 ...
- 103
4
votes
0
answers
350
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:
...
- 143
3
votes
0
answers
129
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| \...
- 143
2
votes
4
answers
313
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
327
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 ...
- 1,835
2
votes
2
answers
802
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 ...
- 145
4
votes
2
answers
661
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,835
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} $ ...
- 85.6k
4
votes
0
answers
171
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 ...
- 81
35
votes
1
answer
784
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,971
0
votes
1
answer
114
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 ...
- 3,738
4
votes
0
answers
163
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 ...
- 767
1
vote
1
answer
163
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 ...
- 48.9k
7
votes
1
answer
544
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
3
votes
0
answers
317
views
Prime Hadamard matrices
Assume that $n$ is a sufficiently large number. Is there a Hadamard matrix $H_{4n \times 4n}=(h_{ij})$ with the last row and the last cloumn $J$ (thet is, for every $k$, $h_{k,4n}=1$ and $h_{4n, k}=1$)...
- 321
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,581
11
votes
2
answers
856
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
5
votes
2
answers
660
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.9k
2
votes
1
answer
221
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 ...
- 6,962
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,962
6
votes
3
answers
463
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,962
7
votes
2
answers
282
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 ...
- 50.8k
4
votes
1
answer
70
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 ...
- 1,081
4
votes
2
answers
221
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,962
8
votes
3
answers
429
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.4k
1
vote
1
answer
834
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 $\...
- 767
0
votes
1
answer
240
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 ...
- 519
3
votes
1
answer
427
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 ...
- 6,962
2
votes
3
answers
319
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 ...
- 6,962
9
votes
1
answer
531
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,633
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), ...
- 3,761
16
votes
3
answers
2k
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 ...
- 23k
7
votes
0
answers
188
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 ...
- 47.3k