Collection Model Theory and Combinatorics
Organizer(s)
Date(s)
26/01/2018
- 02/02/2018
Rank Bounds for Design Matrices and Applications
By Abdul Basit
A (q, k, t)-design matrix is an m by n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: Each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. Dvir–Saraf—Wigderson showed a lower bound of n − ntq(q − 1)/k on the rank of such matrices over fields of characteristic zero (or sufficiently large finite characteristic). Rank bounds of design matrices have been used to study various problems in discrete geometry, such as rigidity theory, geometric incidences and Sylvester–Gallai type problems. In this talk, I will give a survey of the method as well as some of its applications.
