Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
46 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 ...
3
votes
1answer
102 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$...
2
votes
1answer
115 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 ...
6
votes
1answer
288 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 ...
3
votes
2answers
131 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 ...
5
votes
2answers
148 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$-...
2
votes
1answer
76 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?
2
votes
1answer
185 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 ...
2
votes
0answers
62 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 ...
0
votes
0answers
87 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 \...
4
votes
3answers
315 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 ...
2
votes
0answers
150 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}$ ...
3
votes
0answers
83 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
0answers
65 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
2answers
135 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 ...
9
votes
2answers
554 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
0answers
171 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
2answers
165 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
2answers
207 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
1answer
137 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
2answers
292 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
1answer
310 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 ...
6
votes
1answer
262 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
1answer
39 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
0answers
321 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
0answers
117 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
4answers
218 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
1answer
255 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
2answers
563 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
2answers
423 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
2answers
394 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 ...
37
votes
2answers
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
0answers
165 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
1answer
676 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
1answer
108 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
0answers
127 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
1answer
124 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
1answer
286 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
1answer
944 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
1answer
376 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 advance.
5
votes
2answers
398 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
1answer
168 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
0answers
64 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 \...
4
votes
3answers
324 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
votes
2answers
233 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
1answer
65 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
2answers
200 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
3answers
390 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
1answer
583 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
1answer
231 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 ...