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

Solving a Diophantine equation related to Algebraic Geometry, Steiner systems and qq-binomials?

The short version of my question is: 1)For which positive integers k,n is there a solution to the equation k(6k+1)=1+q+q2+⋯+qn with q a prime power? 2) For which positive integers k,n is there a solution to the equation (3k+1)(2k+1)=1+q+q2+⋯+qn with q a prime power? Now for some motivation. In this question I ask for an … 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

Best strategy for a combinatorial game

Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball. Now suppose we are given 5 chances to pick 20 out of 100 boxes. Let’s say that each time we choose 20 boxes, they form a group … Read more