Mathematics Department - Discrete Math - Spring 2015

Discrete Math - Spring 2015


Jeffry Kahn, Jacob D Baron, Patrick Devlin


Upcoming Talks

Monday, March 9th

Margaret A. Readdy, Princeton University and University of Kentucky

"Euler Enumeration"

Time: 11:00 AM
Location: Core 431
Abstract: The flag vector contains all the face incidence data of a polytope, and in the poset setting, the chain enumerative data. It is a classical result that for face lattices of polytopes, and more generally, Eulerian graded posets, the flag vector can be written as a cd-index, a non-commutative polynomial which removes all the linear redundancies among the flag vector entries. This holds for regular CW complexes. We relax the regularity conditions to show the cd-index exists for manifolds whose boundary has a Whitney stratification. We also indicate how the setting of Whitney stratifications expands the nature of questions in the area of flag enumeration.

No prior knowledge of polytopes, topology, etc. will be assumed. The only prerequisite is knowing how to count.

This is joint work with Richard Ehrenborg and Mark Goresky

Past Talks

Monday, February 23rd

Leonid Gurvits, CCNY

"On the complexity of the mixed volume of parallelograms"

Time: 11:00 AM
Location: Core 431
Abstract: I will first review the only and inherently randomized poly-time algorithm to approximate the mixed volume $MV(K_1,...,K_n)$ of $n$ convex bodies $K_1,...,K_n$ in $R^n$ within the relative error $e^n$. If the affine dimensions of the $K_i$'s are at most 2 then the algorithm approximates within the relative error $(1 + sqrt{2})^n$. If the $K_i$'s are parallelograms then their mixed volume is essentially the exponential sum $sum_{S subset {1,...,n}} |det(A_{S})|$, where $A$ is some matrix and $A_{S}$ are its principal submatrices.

I will explain a few hardness and universality results that prohibit "natural" approaches and will describe a deterministic poly-time algorithm to compute the mixed volume of parallelograms within the relative error $2^n$.

Some open problems will be stated.

Monday, February 16th

Laura Florescu, NYU

"Range of a rotor walk and recurrence of directed lattices"

Time: 11:00 AM
Location: Core 431
Abstract: In a emph{rotor walk} the exits from each vertex follow a prescribed periodic sequence. On an infinite Eulerian graph embedded periodically in $R^d$, we show that any simple rotor walk, regardless of rotor mechanism or initial rotor configuration, visits at least on the order of td/(d+1) distinct sites in t steps. We prove a shape theorem for the rotor walk on the comb graph with i.i.d. uniform initial rotors, showing that the range is of order t2/3 and the asymptotic shape of the range is a diamond. Using a connection to the mirror model and critical percolation, we show that rotor walk with i.i.d. uniform initial rotors is recurrent on two different directed graphs obtained by orienting the edges of the square grid, the Manhattan lattice and the F-lattice. 

Joint work with Lionel Levine and Yuval Peres.

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.

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.

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.