Organizer(s) | Jeffry Kahn, Jacob D Baron, Patrick Devlin | Archive |
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. |