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
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 $$ ...
unknown's user avatar
  • 451
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 ...
guigux's user avatar
  • 607
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 ...
coolpapa's user avatar
  • 455
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
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
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 \} = \...
Lior's user avatar
  • 21
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
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. ...
Robert Bailey's user avatar
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 ...
Fedor Petrov's user avatar
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 ...
Meysam Ghahramani's user avatar
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 ...
kodlu's user avatar
  • 10k
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 ...
Rasmus Pagh's user avatar
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: ...
Xi Wu's user avatar
  • 143
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| \...
Xi Wu's user avatar
  • 143
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 ...
Bogdan Chornomaz's user avatar
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,\...
Baron Crinkle's user avatar
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 ...
Gorka's user avatar
  • 1,825
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 ...
Jim's user avatar
  • 145
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 ...
Gorka's user avatar
  • 1,825
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
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 ...
Sankeerth's user avatar
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 ...
Yoav Kallus's user avatar
  • 5,926
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 ...
Alireza Abdollahi's user avatar
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 ...
Binzhou Xia's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Arimakat's user avatar
  • 333
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 ...
Hao Chen's user avatar
  • 2,541
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 ...
user avatar
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 ...
domotorp's user avatar
  • 18.3k
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 ...
Felix Goldberg's user avatar
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 \...
Felix Goldberg's user avatar
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 ...
Felix Goldberg's user avatar
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 ...
Richard Stanley's user avatar
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 ...
Peter Dukes's user avatar
  • 1,071
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$, ...
Felix Goldberg's user avatar
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 ...
Wolfgang's user avatar
  • 13.2k
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 $\...
Binzhou Xia's user avatar
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 ...
j.s.'s user avatar
  • 519
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 ...
Felix Goldberg's user avatar
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
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 $\...
Dustin G. Mixon'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
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), ...
Drew Armstrong's user avatar
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 ...
Seva's user avatar
  • 22.8k
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 ...
Mariano Suárez-Álvarez's user avatar
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-...
Felix Goldberg's user avatar
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)$ ...
Felix Goldberg's user avatar
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 ...
Dustin G. Mixon's user avatar
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 ...
user32970's user avatar
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 ...
Felix Goldberg's user avatar