Mathematics Department - Discrete Math - Spring 2016

Discrete Math - Spring 2016


Jeffry Kahn, Jacob D Baron, Patrick Devlin


Upcoming Talks

Monday, February 15th

Eric Vigoda, Georgia Tech

"Spin Systems on Random Regular Graphs"

Time: 2:00 PM
Location: Hill 705
Abstract: We'll look at the behavior of spin systems on random regular, bipartite graphs and how it relates to phase transitions on regular trees. We present a new approach for the analysis of such graphs. This yields new results for hardness of approximating the partition function for the hard-core model on weighted independent sets and for counting the number of k-colorings of a graph.

The talk is based on joint work with Andreas Galanis (Oxford) and Daniel Stefankovic (Rochester).

Monday, February 22nd

Hoi Nguyen, Ohio State and IAS

"Gaussian properties of normal vectors in random discrete matrices"

Time: 2:00 PM
Location: Hill 705
Abstract: Let X_1,.., X_{n-1} be independent vectors in R^n, and X be the normal unit vector of the hyperplane spanned by these vectors. It is clear that if X_i are iid Gaussian, then X has gaussian distribution. In this talk we show that many gaussian properties remain true for X even when X_i have Bernoulli distributions. (partly joint with V. Vu)

Past Talks

Monday, February 8th

Doron Puder, IAS

"Ramanujan Coverings of Graphs"

Time: 2:00 PM
Location: Hill 705
Abstract: Ramanujan graphs are optimal expander graphs, and their existence and construction have been the focus of much research during the last three decades. We prove that every bipartite Ramanujan graph has a d-covering (a.k.a. d-lift) which is also Ramanujan. This generalizes the d=2 case, a recent major breakthrough in the subject due to Marcus, Spielman and Srivastava. The main tools we use are the Peter-Weyl theory in group representations, as well as the theory of interlacing polynomials.

All notions will be explained. Joint work with Chris Hall and Will Sawin.

Monday, February 1st

Karim Adiprasito, Hebrew University/IAS

"From mixed multiplicities to combinatorial geometries to Hodge theory (and log-concavity of the Whitney coefficients)"

Time: 2:00 PM
Location: Hill 705

A conjecture of Read predicts that the coefficients of the chromatic polynomial of any graph form a log-concave sequence. A related conjecture of Welsh predicts that the number of linearly independent subsets of varying sizes form a log-concave sequence for any configuration of vectors in a vector space. Both conjectures are special cases of the famous Rota conjecture asserting the log-concavity of the coefficients of the characteristic polynomial of any matroid.

The recent story of these problems starts in 2010, when June Huh proved Rota's conjecture for the special case of a hyperplane arrangement by identifying the Whitney coefficients with mixed multiplicities of its Jacobian ideal. It subsequently emerged that virtually all proofs we could come up with for this case use nontrivial geometric facts about the arrangement and/or Hodge theory for projective varieties, and the more general conjecture of Rota for possibly "nonrealizable" configurations/matroids remained open until recently.

I will discuss how to extend Hodge theory beyond the classical setting to general matroids, starting with the surprising joint work with Bjorner on Lefschetz theorems for Mikhalkin's p,q-groups, and then discuss the proof of the "Kahler package" for general matroidal fans, which proves the Rota and Welsh conjecture in full generality. All proofs are purely combinatorial, and do not rely on analytifications or projective algebraic geometry, although there are some useful relations I will mention.

Based on joint work with Anders Bjorner and with June Huh and Eric Katz

This page was last updated on February 09, 2016 at 10:04 am and is maintained by
For questions regarding courses and/or special permission, please contact
For questions or comments about this site, please contact
© 2016 Rutgers, The State University of New Jersey. All rights reserved.