Mathematics Department - Discrete Math - Spring 2015

Discrete Math - Spring 2015


Jeffry Kahn, Jacob D Baron, Patrick Devlin


Upcoming Talks

Monday, February 2nd

Yuval Filmus, IAS

"A Nice Basis for the Slice"

Time: 11:00 AM
Location: Core 431
Abstract: The slice is the set of vectors in {0,1}^n of Hamming weight k. Consider the following three questions: (1) I have a function on the slice. What is the correct way to extend it to {0,1}^n and beyond? (2) Is there a Fourier basis for the slice? (3) Is there an explicit orthogonal basis of eigenvectors for the Kneser and Johnson graphs? Surprisingly, all these questions are connected. We answer them by giving a nice basis for functions on the slice, derived from Young's orthogonal basis for the symmetric group.

Monday, February 9th

Guangda Hu, Princeton

"Sylvester-Gallai for Arrangements of Subspaces"

Time: 11:00 AM
Location: Core 431
Abstract: In this work we study arrangements of k-dimensional subspaces V_1,...,V_n subset C^ell. Our main result shows that, if every pair V_a,V_b of subspaces is contained in a dependent triple (a triple V_a,V_b,V_c contained in a 2k-dimensional space), then the entire arrangement must be contained in a subspace whose dimension depends only on k (and not on n). The theorem holds under the assumption that V_a cap V_b = {0} for every pair (otherwise it is false). This generalizes the Sylvester-Gallai theorem (or Kelly's theorem for complex numbers), which proves the k=1 case. Our proof also handles arrangements in which we have many pairs (instead of all) appearing in dependent triples, generalizing the quantitative results of Barak et. al. [BDWY-pnas]. One of the main ingredients in the proof is a strengthening of a Theorem of Barthe [Bar98] (from the k=1 to k>1 case) proving the existence of a linear map that makes the angles between pairs of subspaces large on average. Such a mapping can be found, unless there is an obstruction in the form of a low dimensional subspace intersecting many of the spaces in the arrangement (in which case one can use a different argument to prove the main theorem). Joint with Zeev Dvir.

This page was last updated on August 29, 2014 at 01:59 pm and is maintained by
For questions regarding courses and/or special permission, please contact
For questions or comments about this site, please contact
© 2015 Rutgers, The State University of New Jersey. All rights reserved.