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