Mathematics Department - Discrete Math - Fall 2015

Discrete Math - Fall 2015


Jeffry Kahn, Jacob D Baron, Patrick Devlin


Past Talks

Monday, October 5th

Krzysztof Choromanski, Google Research

"The Erdos-Hajnal Conjecture, structured non-linear graph-based hashing and b-matching anonymization via perfect matchings counting"

Time: 2:00 PM
Location: Hill 425
Abstract: The goal of this talk is to show three new combinatorial techniques that led to some recent advances in discrete mathematics and computer science in general.

The first one regards the celebrated open conjecture of Erdos and Hajnal from 1989 stating that families of graphs not having some given graph H as an induced subgraph contain polynomial-size cliques/stable sets (in the undirected setting) or transitive subsets (in the directed setting). Recent techniques that I will be talking about in this part of the talk provided the proof of the conjecture for new infinite classes of graphs. Furthermore, they gave tight asymptotics for the Erdos-Hajnal coefficients for many classes of prime tournaments as well as the proof of the weaker version of the conjecture for trees on at most six vertices and all but one tournament on at most six vertices.

Structured non-linear graph-based hashing is motivated by applications in neural networks, where matrices of linear projections are constrained to have a specific structured form. This drastically reduces the size of the model and speeds up computations. I will show how the properties of the underlying graph encoding correlations between entries of these matrices (such as its chromatic number) imply the quality of the entire non-linear hashing mechanism. Furthermore, I will explain how general structured matrices that very recently attracted researchers attention naturally lead to the underlying graph theory description.

The last topic covers combinatorial results regarding the number of perfect matchings containing some fixed partial matching in the bipartite graph. Those results provide theoretical guarantees regarding privacy level achieved by several new graph-based anonymization algorithms such as b-matching.

Monday, September 28th

Elchanan Mossel, U Penn

"Strong contraction and influences in tail spaces"

Time: 2:00 PM
Location: Hill 425
Abstract: Various motivations recently led Mendel and Naor, Hatami and Kalai to study functions in tail spaces - i.e. function all of whose low level Fourier coefficients vanish. I will discuss the questions and conjectures that they posed and our recent work which resolves some of these questions and conjectures. Based on a joint work with Steven Heilman and Krzysztof Oleszkiewicz.

Monday, September 21st

Toby Johnson, USC

"The second eigenvalue of dense random regular graphs"

Time: 2:00 PM
Location: Hill 425
Abstract: Consider a random d-regular graph on n vertices. Its second eigenvalue is closely related to its expansion properties, and bounding it has been a major topic of research over the last thirty years. It's conjectured by Van Vu that as n and optionally d tend to infinity, the second eigenvalue is bounded by C*sqrt(d) with probability tending to 1, so long as d remains between 3 and n-3. This is currently known to hold only if d = o(n^(1/2)). We show that it holds so long as d remains smaller than n^(2/3). We use the Kahn-Szemeredi approach, which is based on showing concentration for Rayleigh quotients of the graph's adjacency matrix. We develop new techniques based on Stein's method for proving these concentration results. Our machinery gives proofs vastly simpler than previous ones based on martingales. This is joint work with Nicholas Cook and Larry Goldstein.

This page was last updated on August 29, 2014 at 05: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.