Mathematics Department - Discrete Math - Spring 2015

Discrete Math - Spring 2015


Jeffry Kahn, Jacob D Baron, Patrick Devlin


Upcoming Talks

Monday, April 27th

June Huh, Princeton

"Log-concavity conjectures and the tropical Laplacian"

Time: 11:00 AM
Location: Core 431
Abstract: A conjecture of Rota predicts that the coefficients of the chromatic polynomial of a matroid form a log-concave sequence. A related conjecture of Welsh predicts that the number of independent subsets of given size form a log-concave sequence for any matroid. The known proofs for realizable matroids uses algebric geometry in an essential way, and the conjecture is open in its full generality. I will give a survey of known results, and introduce a stronger conjecture that a certain Laplacian matrix associated to a matroid has exactly one negative eigenvalue.

Past Talks

Monday, April 20th

Eyal Lubetzky, NYU

"Random walks on the random graph"

Time: 11:00 AM
Location: Core 431
Abstract: We study random walks on the giant component of the ErdH{o}s-R'enyi random graph $G(n,p)$ where $p= lambda / n$ for $lambda > 1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $log^2 n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(log n)$ and concentrates it (the cutoff phenomenon occurs).

Joint work with N. Berestycki, Y. Peres and A. Sly.

Monday, April 13th

Richard Ehrenborg, Princeton and University of Kentucky

"Title: The Law of Aboav--Weaire and its analogue in three dimensions"

Time: 11:00 AM
Location: Core 431
Abstract: When investigating the structure of metals it is known that the atoms lie in a lattice structure. However, the lattice property only holds locally, that is, in a three dimensional cell called a grain. Bordering the grain is a boundary where the atoms lie chaotically, and beyond that is a new grain where the lattice has a different orientation. The structure of these grains amounts to a three dimensional simple subdivision of space.

Looking at the two dimensional analogue, one observes that grains with a small number of sides tend to be surrounded by grains with a large number of sides, and vice versa. The Law of Aboav--Weaire states that the average number of sides of the neighbors of an n-sided grain should be roughly 5+6/n. By introducing the correct error term we prove this law of Material Science and discuss its extension to three dimensions.

This is joint work with Menachem Lazar and Jeremy Mason. Moreover, selected work of von Neumann, MacPherson and Srolovitz will be presented.

Monday, April 6th

Van Vu, Yale

"Random matrices have simple spectrum"

Time: 11:00 AM
Location: Core 431
Abstract: A symmetric matrix has simple spectrum if all eigenvalues are different. In 1980s. Babai conjectured that random graphs have simple spectrum with probability tending to 1.

Confirming this conjecture, we prove the simple spectrum property for a large class of random matrices. If time allows, we will discuss the harder problem of bounding the spacings between consecutive eigenvalues, with motivation from mathematical physics and numerical linear algebra.

Several open questions will also be presented.

Joint work with H. Nguyen (OSU) and T. Tao (UCLA).

Monday, March 30th

Sivakanth Gopi, Princeton

"On the number of rich lines in truly high dimensional sets"

Time: 11:00 AM
Location: Core 431
Abstract: We prove a new upper bound on the number of r-rich lines (lines with at least r points) in a 'truly' d-dimensional configuration of points v_1,...,v_n over the complex numbers. More formally, we show that, if the number of r-rich lines is significantly larger than n^2/r^d then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor r^d can be replaced with a tight r^{d+1}. If true, this would generalize the classic Szemeredi-Trotter theorem which gives a bound of n^2/r^3 on the number of r-rich lines in a planar configuration. This conjecture was shown to hold in R^3 in a seminal work of Guth and Katz (2010) and was recently proved over R^4 (under some additional restrictions) by Solomon and Sharir. Although our bound is not optimal, it is the first to hold in arbitrary dimension. For the special case of arithmetic progressions (r collinear points that are evenly distanced) we give a bound that is tight up to low order terms, showing that a d-dimensional grid achieves the largest number of r-term progressions. We will also discuss some subsequent work by Zahl, Hablicsek and Scherr which made progress on our conjecture.

Joint work with Zeev Dvir (Princeton).

Monday, March 23rd

Yufei Zhao, MIT

"Large deviations in random graphs"

Time: 11:00 AM
Location: Core 431
Abstract: What is the probability that the number of triangles in an ErdH{o}s--R'enyi random graph $G(n,p)$ exceeds its mean by a constant factor? In this talk, I will survey some recent progress on this problem.

Already the order in the exponent of the tail probability was a long standing open problem until a few years ago when it was solved by DeMarco and Kahn, and independently by Chatterjee. We now wish to determine the exponential rate of the tail probability. Thanks for the works of Chatterjee--Varadhan (dense setting) and Chatterjee--Dembo (sparse setting), this large deviations problem reduces to a natural variational problem on the space of graphons. We solve this variational problem asymptotically, thereby determining the large deviation rate, which is valid at least for $p geq n^{-alpha}$ for some $alpha > 0$.

Based on joint work with Eyal Lubetzky.

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

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.