Mathematics Department - Discrete Math - Spring 2016

Discrete Math - Spring 2016


Jeffry Kahn, Jacob D Baron, Patrick Devlin


Past Talks

Monday, April 25th

Eyal Lubetzky, NYU


Time: 2:00 PM
Location: Hill 705
Abstract: The notion of noise sensitivity of a Boolean function, introduced in the seminal work of Benjamini, Kalai and Schramm (1999), describes its likelihood to flip under small perturbations of its input. We study noise sensitivity and a natural stronger version of it, addressing the effect of noise given a specific witness in the original input. Our main context is the Erdos-Renyi random graph, where already the property of containing a given graph is sufficiently rich to separate these notions. In particular, our analysis implies (strong) noise sensitivity in settings where the Benjamini-Kalai-Schramm criterion involving the first Fourier level does not apply, e.g., when the threshold goes to 0 as a power of the number of variables. ​

​ Joint work with Jeff Steif.

Monday, April 18th

No seminar this week!


Time: 2:00 PM
Location: Hill 705

Monday, April 11th

Pooya Hatami, IAS

"A characterization of functions with vanishing averages over products of disjoint sets"

Time: 2:00 PM
Location: Hill 705
Abstract: We characterize all complex-valued (Lebesgue) integrable functions f on [0,1]^m such that f vanishes when integrated over the product of m measurable sets which partition [0,1] and have prescribed Lebesgue measures alpha_1,ldots,alpha_m. We characterize the Walsh expansion of such functions f via a first variation argument.

Janson and Sos asked this analytic question motivated by questions regarding quasi-randomness of graph sequences in the dense setting. We use this characterization to answer a few conjectures from [S. Janson and V. Sos: More on quasi-random graphs, subgraph counts and graph limits]. There it was conjectured that certain density conditions of paths of length 3 defines quasi-randomness, we confirm this conjecture by showing more generally that similar density conditions for any graph with twin vertices defines quasi-randomness.

The quasi-randomness results use the language of graph limits. No back-ground on graph limit theory will be assumed, and we will spend a fraction of the talk introducing the graph limits approach in the study of quasi-randomness of graph sequences.

The talk is based on joint work with Hamed Hatami and Yaqiao Li.

Monday, April 4th

Pawel Hitczenko, Drexel University

"Recurrences for generating polynomials"

Time: 2:00 PM
Location: Hill 705
Abstract: In the talk I will describe several recurrences for polynomials that I encountered recently. When interpreted in probabilistic language they are, after suitable normalization, generating polynomials of discrete random variables and thus are useful in studying properties of these random variables.

I will then discuss attempts (mostly unsatisfactory at this point) to extract general statement that would allow to draw conclusions about the asymptotic behavior of the underlying random variables from the form of the recurrences.

As an example of applications I will present some new results on tree-like tableaux, a combinatorial family introduced in 2011. Our results extend those of Laborde Zubieta, and also of Aval, Boussicault and Nadeau.

This is joint work with Amanda Lohss.

Monday, March 28th

Ross Berkowitz, Rutgers

"Robust Positioning Patterns"

Time: 2:00 PM
Location: Hill 705
Abstract: What is the longest binary sequence such that each length k window is unique? The answer to this question is given by De Bruijn sequences, which have length 2^k. We extend the question by not only asking that all windows are distinct, but rather that they are far apart as well. We give constructions which match, up to a constant factor, upper bounds on the rate-distance trade-off.

Monday, March 21st

Ori Parzanchevski, IAS and Hebrew U.

"Random walks on complexes"

Time: 2:00 PM
Location: Hill 705
Abstract: The asymptotic behavior of random walk on a graph is dictated by its connectedness. I will describe several approaches to relate random walks on complexes to high dimensional (homological) connectedness. No previous knowledge is assumed.

Monday, March 7th

Sijian Tang, Rutgers

"Noisy population recovery in polynomial time"

Time: 2:00 PM
Location: Hill 705
Abstract: In the noisy population recovery problem of Dvir et al. [DRWY12], the goal is to learn an unknown distribution f on binary strings of length n from noisy samples. For some parameter mu, a noisy sample is generated by flipping each coordinate of a sample from f independently with probability (1-mu)/2. We assume an upper bound k on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error epsilon.

In this talk I will show that for any fixed mu > 0, one can solve this problem with complexity ploynomial in k, n and 1/epsilon. Which improves the previous best result of poly(k^(log log k), n, 1/epsilon).

Based on joint work with Anindya De and Michael Saks.

Monday, February 29th

Adam Marcus, Princeton

"Interlacing families: a new technique for controlling eigenvalues"

Time: 2:00 PM
Location: Hill 705
Abstract: Matrices are one of the most fundamental structures in mathematics, and it is well known that the behavior of a matrix is dictated by its eigenvalues. Eigenvalues, however, are notoriously hard to control, due in part to the lack of techniques available. In this talk, I will present a new technique that we call the "method of interlacing polynomials" which has been used recently to give unprecedented bounds on eigenvalues, and as a result, new insight into a number of old problems. I will discuss some of these recent breakthroughs, which include the existence of Ramanujan graphs of all degrees, a resolution to the famous Kadison-Singer problem, and most recently an incredible result of Anari and Gharan on the Traveling Salesman problem that has produced an interesting anomaly in computer science.

This talk will be directed at a general mathematics audience and represents joint work with Dan Spielman and Nikhil Srivastava.

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)

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 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.