Mathematics Department - Discrete Math - Fall 2015

Discrete Math - Fall 2015


Jeffry Kahn, Jacob D Baron, Patrick Devlin


Upcoming Talks

Monday, November 30th

Boris Bukh, CMU

"Ranks of matrices with few distinct entries"

Time: 2:00 PM
Location: Hill 425
Abstract: Many applications of linear algebra method to combinatorics rely on the bounds on ranks of matrices with few distinct entries and constant diagonal. In this talk, I will explain some of these application. I will also present a classification of sets L for which no low-rank matrix with entries in L exists.

Past Talks

Monday, November 23rd

Ameera Chowdhury, Rutgers

"Inclusion Matrices and the MDS Conjecture"

Time: 2:00 PM
Location: Hill 425
Abstract: Let F_q be a finite field of order q with characteristic p. An arc is an ordered family of vectors in (F_q)^k in which every subfamily of size k is a basis of (F_q)^k. The MDS conjecture, which was posed by Segre in 1955, states that if k <= q, then an arc in (F_q)^k has size at most q+1, unless q is even and k=3 or k=q-1, in which case it has size at most q+2.

We propose a conjecture which would imply that the MDS conjecture is true for almost all values of k when q is odd. We prove our conjecture in two cases and thus give simpler proofs of the MDS conjecture when k <= p, and if q is not prime, for k <= 2p-2. To accomplish this, given an arc G of (F_q)^k and a nonnegative integer n, we construct a matrix M_G^{uparrow n}, which is related to an inclusion matrix, a well-studied object in combinatorics. Our main results relate algebraic properties of the matrix M_G^{uparrow n} to properties of the arc G and may provide new tools in the computational classification of large arcs.

Monday, November 16th

Jed Yang, U. Minnesota

"Tiling with triangles is hard"

Time: 2:00 PM
Location: Hill 425
Abstract: Knutson, Tao, and Woodward introduced puzzle pieces consisting of two triangles and a rhombus (with edge labels). They proved that tilings by these puzzle pieces (allowing rotations) of triangular regions (with edge labels) are counted by Littlewood-Richardson coefficients, which are numbers that appear naturally in many contexts.

Together with the saturation conjecture, proved by Knutson and Tao, this means, in particular, that tileability of triangular regions by puzzle pieces can be decided in polynomial time. In this talk, we will discuss the problem of tiling arbitrary regions with these puzzle pieces. Regardless of whether reflections are allowed when tiling, the problem is NP-complete.

Joint work with Igor Pak.

Monday, November 9th

Huseyin Acan, Rutgers

"Indecomposability threshold for random permutations"

Time: 2:00 PM
Location: Hill 425
Abstract: A permutation of n is indecomposable if no proper initial segment is a permutation of an integer less than n. Consider a permutation a(n,m) chosen uniformly at random from the set of permutations of n with exactly m inversions. This permutation is decomposable for small m and indecomposable for large m (with probability approaching 1 as n tends to infinity). I will talk about a threshold m(n) around which the transition from 'being decomposable' to 'being indecomposable' occurs and also the number of indecomposable components a(n,m) when m is slightly below the threshold.

Joint work with Boris Pittel.

Monday, November 2nd

Jan Vondrak, IBM/IAS

"Algorithmic proof of the Lovasz Local Lemma via resampling oracles"

Time: 2:00 PM
Location: Hill 425
Abstract: For a collection of events on a probability space with specified dependencies, the Lovasz Local Lemma ("LLL") gives a sufficient condition for the existence of a point avoiding all the events. Following Moser's discovery of an efficient algorithm for many applications of the Lovasz Local Lemma, there has been extensive research on various extensions of this result. We present a unifying algorithmic proof of the Lovasz Local Lemma (and its stronger variants such as Shearer's Lemma), independent of the underlying probability space, using what we call "resampling oracles". As a consequence, we obtain efficient algorithms for the known settings where the LLL applies (independent random variables, random permutations, perfect matchings, spanning trees). We present some new applications, in particular a new result on packings of rainbow spanning trees. ​

​ (joint work with Nick Harvey)

Monday, October 26th

Noga Alon, Tel Aviv University and IAS, Princeton

"Coloring and Girth"

Time: 2:00 PM
Location: Hill 425
Abstract: The study of graphs with high girth and high chromatic number had a profound influence on the history of Combinatrics and Graph Theory, and led to the development of sophisticated methods involving tools from topology, number theory, algebra and combinatorics.

I will discuss the topic focusing on a recent new explicit construction of graphs (and hypergraphs) of high girth and high chromatic number, in joint work with Kostochka, Reiniger, West and Zhu.TBA

Monday, October 19th

Maria Chudnovsky, Princeton University

"Induced cycles and coloring"

Time: 2:00 PM
Location: Hill 425
Abstract: The Strong Perfect Graph Theorem states that graphs with no induced odd cycle of length at least five, and no complements of one behave very well with respect to coloring. But what happens if only some induced cycles (and no complements) are excluded? Gyarfas made a number of conjectures on this topic, asserting that in many cases the chromatic number is bounded by a function of the clique number. In this talk we discuss recent progress on some of these conjectures.

This is joint work with Alex Scott and Paul Seymour.

Monday, October 12th

John Kim, Rutgers

"A Cauchy-Davenport theorem for linear maps"

Time: 2:00 PM
Location: Hill 425
Abstract: We prove a version of the Cauchy-Davenport theorem for general linear maps. For subsets A and B of the finite field F_p, the classical Cauchy-Davenport theorem gives a lower bound for the size of the sumset A+B in terms of the sizes of the sets A and B. Our theorem considers a general linear map L:F_p^n -> F_p^m and subsets A_1, ..., A_n of F_p, and gives a lower bound on the size of L(A_1 x A_2 x ... x A_n) in terms of the sizes of A_1, ..., A_n. Our proof uses Alon's Combinatorial Nullstellensatz and a variation of the polynomial method.

Joint work with Simao Herdade and Swastik Kopparty

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 October 12, 2015 at 03:30 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.