Talk information

Date: Sunday, January 12, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Noga Alon (Princeton University and Tel Aviv University)
Title: On designs and partial designs

Abstract:

A family of subsets (called blocks) $A_1,A_2, …,A_m$ of a finite set $X$ is a (balanced incomplete) block design if every pair of distinct elements of $X$ belongs to exactly one block $A_i$. It is a partial design if every such pair belongs to at most one block.

The following two problems were raised by Erdős.

(1) Is there an absolute constant $C$ so that if $|X|=n$ and every block $A_i$ in a partial design is of size $\Omega(\sqrt n)$, then there is a subset $B$ of $X$ that intersects each block by at least 1 and at most $C$ elements ?

(2) Is there an absolute positive constant $c$ so that the number of ordered sequences $n \geq x_1 \geq x_2 … \geq x_m \geq 2$ such that there is a block design on a set $X$ of size $n$ in which the ordered sequence of sizes of the blocks is $x_1,x_2,…,x_m$ is at least $e^{c\sqrt n\log n}$?

I will settle both problems and discuss some related results and open problems.