All Articles

Extremal collections of $k$-uniform vectors

Author:

Speaker – Joe Briggs (Technion Israel Institute of Technology)

 

Send RSVP to Bernard Licicky (lidicky@iastate.edu) to receive the event link.

 

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.