Mathematics Department - Discrete Math - Spring 2017

Discrete Math - Spring 2017



Organizer(s)

Jeffry Kahn, Jacob D Baron, Patrick Devlin

Archive



Upcoming Talks


Monday, January 23rd

Zeev Dvir, Princeton University

"Rank bounds for design matrices with block entries and geometric applications"

Time: 2:00 PM
Location: Hill 705
Abstract: Design matrices are sparse matrices in which the supports of different columns intersect in a few positions. Such matrices come up naturally when studying problems involving point sets with many collinear triples. In this work we consider design matrices with block (or matrix) entries. Our main result is a lower bound on the rank of such matrices, extending the bounds proven in [BDWY12, DSW14] for the scalar case. As a result we obtain several applications in combinatorial geometry. The main application involves extending the notion of combinatorial rigidity from pairwise distance constraints to three wise collinearities. The main technical tool in the proof of the rank bound is an extension of the technique of matrix scaling to the setting of block matrices. We generalize the definition of doubly stochastic matrices to matrices with block entries and derive sufficient conditions for a doubly stochastic scaling to exist. Joint work with Ankit Garg, Rafael Oliveira and Jozsef Solymosi


This page was last updated on February 09, 2016 at 10:04 am and is maintained by webmaster@math.rutgers.edu.
For questions regarding courses and/or special permission, please contact ugoffice@math.rutgers.edu.
For questions or comments about this site, please contact help@math.rutgers.edu.
© 2017 Rutgers, The State University of New Jersey. All rights reserved.