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: The universe size $d = O(\ell)$. There are $\ell^2$ sets in the design, $S_1, \dots, S_{\ell^2} \subseteq [d]$. $(\forall i \in … Read more

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 multigraph H(t) edge-decomposes into copies of G? I believe that Wilson’s theory (under certain hypotheses) gives a solution when H is … Read more

k-partite design

Is the following true? For every n≥1,k≥2, there is a set S⊆[n]k of size |S|=n2 such that every two k-tuples in S have at most one common entry. Does anyone know if this is true? Is there a reference? Answer Assuming that “at most common entry” means that any two tuples (x1,…,xk) and (y1,…,yk) match … Read more

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 are the following: N(n)≤n−1 for all n≥2, with equality if n is a prime power. This is … Read more

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 that every pair of points determines determines a unique line every line contains at least two … Read more

Is there an infinite number of combinatorial designs with r=λ2r=\lambda^{2}

A quick look at Ed Spence’s page reveals two such examples: (7,3,3) and (16,6,3). If there is a known classification and/or name by which such designs go, I’d love to know about them too. EDIT: I am specifically interested in designs where at least one pair of blocks has a nonempty intersection, with multiple blocks … Read more

“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 each problem. After the test, one finds that for every three students, there is one problem to which their answers … Read more

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) contains incidence matrices of symmetric (n,k,λ)-designs, then the minimum permanent on A(k,n) is attained at one of theses incidence matrices. … Read more

covering designs of the form (v,k,2)(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 to find the minimum number of subsets such a family can have. I am interested … Read more