Speaker: Joe Briggs
Title: Extremal collections of $k$-uniform vectors
Abstract: Where extremal combinatorialists wish to optimise a discrete
parameter over a family of large objects, probabilistic combinatorialists
study the statistical behaviour of a randomly chosen object in such a
family. In the context of representable matroids (i.e. the columns of a
matrix) over F_2, one well-studied distribution is to fix a small k and
large m and randomly generate m columns with k 1's. Indeed, when k=2, this
is the graphic matroid of the Erdos-Renyi random graph G_{n,m}.
We turn back to the simplest corresponding extremal question in this
setting. What is the maximum number of weight-k columns a matrix of rank ≤
n can have? We show that, once n≥N_k, one cannot do much better than taking
only n rows and all available weight-k columns. This partially confirms a
conjecture of Ahlswede, Aydinian and Khachatrian, who believe one can take
N_k=2k.
This is joint work with Wesley Pegden.