Mathematics Department - Discrete Math - Spring 2017

Discrete Math - Spring 2017



Organizer(s)

Jeffry Kahn, Jacob D Baron, Patrick Devlin

Archive



Upcoming Talks


Monday, March 27th

Van Vu, Yale University

"Littlewood-Offord-Erdos type inequalities for polynomials of random variables"

Time: 2:00 PM
Location: Hill 705
Abstract: Let Q = a_1x_1 + ....+a_n x_n where a_i are non-zero real numbers, and x_i are +-1 random variables. A classical result of Littlewood-Offord-Erdos showed that Pr (Q=0) is O( n^{-1/2} ). We are going to discuss the general case when Q is a polynomial (in the x_i) with arbitrary degree. We will present several new results/methods together with applications in various fields and a few open questions.





Past Talks


Monday, March 20th

June Huh, Princeton University

"Negative correlation and Hodge-Riemann relations"

Time: 2:00 PM
Location: Hill 705
Abstract: All finite graphs satisfy the two properties mentioned in the title. I will explain what I mean by this, and speculate on generalizations and interconnections. This talk will be non-technical.


Monday, March 6th

Ferdinand Ihringer , University of Regina

"Large Erdos-Ko-Rado Sets in Vector and Polar Spaces"

Time: 2:00 PM
Location: Hill 705
Abstract: An Erdos-Ko-Rado set (EKR set) Y of { 1, ..., n } is a family of k-sets, which pairwise intersect non-trivially. A non-trivial problem is to provide tight upper bounds on Y and classify all examples, which obtain that bound. Erdos, Ko and Rado proved |Y| = 2k. Equality holds for n = 2k+1 if and only if Y is the family of all k-sets, which contain one fixed element.

If one considers { 1, ..., n } as the vector space over the field with 1 element, then it is natural to generalize the concept of EKR sets to vector spaces over finite fields. Here an EKR set of a vector space of dimension n is a family of k-spaces, which pairwise meet non-trivially. If we equip a vector space over a finite field of order q with a reflexive, non-degenerate sesquilinear form, then the subspaces that vanish on this form constitute a highly symmetric geometric structure, a polar space.

The talk will introduce the audience to some aspects of EKR sets in vector and polar spaces. In particular we will elaborate on classification results that use spectral techniques.


Monday, February 27th

Maria Chudnovsky, Princeton University

"Induced cycles and coloring"

Time: 2:00 PM
Location: Hill 705
Abstract: The Strong Perfect Graph Theorem states that graphs with no induced odd cycle of length at least five, and no complement of one behave very well with respect to coloring. But what happens if only some induced cycles (and no complements) are excluded? Gyarfas made three 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 the recent solutions of these conjectures.

This is joint work with Alex Scott, Paul Seymour and Sophie Spirkl.


Monday, February 20th

Pat Devlin, Rutgers University

"Proof of an entropy conjecture of Leighton and Moitra"

Time: 2:00 PM
Location: Hill 705
Abstract: Suppose F is a random (not necessarily uniform) permutation of {1, 2, ... , n} such that |Prob(F(i) < F(j)) -1/2| > epsilon for all i,j. We show that under this assumption, the entropy of F is at most (1-delta)log(n!), for some fixed delta depending only on epsilon [proving a conjecture of Leighton and Moitra]. In other words, if (for every distinct i,j) our random permutation either noticeably prefers F(i) < F(j) or prefers F(i) > F(j), then the distribution inherently carries significantly less uncertainty (or information) than the uniform distribution. Our proof relies on a version of the regularity lemma, a combinatorial bookkeeping gadget, and a few basic probabilistic ideas. The talk should be accessible for any background, and I'll gently recall any relevant notions (e.g., entropy) as we go. Those dissatisfied with the talk will not be refunded the cost of admission, and those tremendously dissatisfied won't like my defense either. This is from a recent paper joint with Huseyin Acan and Jeff Kahn.


Monday, February 13th

Oanh Nguyen, Yale University

"Roots of random polynomials"

Time: 2:00 PM
Location: Hill 705
Abstract: Random polynomials, despite their simple appearance, remain a mysterious object with a large number of open questions that have attracted intensive research for many decades. In this talk, we will discuss some properties of random polynomials including universality and asymptotic normality. I will also talk about some interesting open questions.

The talk is based on joint works with Yen Do, Hoi Nguyen, and Van Vu.


Monday, February 6th

Abdul Basit, Rutgers University

"On the number of ordinary lines determined by sets in complex space"

Time: 2:00 PM
Location: Hill 705
Abstract: Consider a set of n points in R^d. The classical theorem of Sylvester-Gallai says that, if the points are not all collinear then there must be a line through exactly two of the points. We call such a line an "ordinary line". In a recent result, Green and Tao were able to give optimal linear lower bounds (roughly n/2) on the number of ordinary lines determined n non-collinear points in R^d. In this talk we will consider the analog over the complex numbers. While the Sylvester-Gallai theorem as stated above is known to be false over the field of complex numbers, it was shown by Kelly that for a set of n points in C^d, if the points don’t all lie on a 2-dimensional plane then the points must determine an ordinary line. Using techniques developed for bounding the rank of design matrices, we will show that such a point set must determine at least 3n/2 ordinary lines, except in the trivial case of n−1 of the points being contained in a 2-dimensional plane.

Joint work with Z. Dvir, S. Saraf and C. Wolf


Monday, January 30th

Rafael Oliveira, Princeton University

"Operator Scaling: Theory & Applications, and the simplest algorithm for the linear matroid intersection problem ever designed!"

Time: 2:00 PM
Location: Hill 705
Abstract: In this talk we shall explore quantum operators, the operator scaling problem and its myriad incarnations in commutative and non-commutative algebra, computational complexity, optimization and quantum information theory. We will describe an efficient algorithm solving the operator scaling problem and all these related problems, and how its analysis combines ideas from all these areas. The problem these algorithms solve is non-convex, and we hope they will have many other applications.

As a combinatorial bonus, we will see the shortest algorithm for the linear matroid intersection problem ever designed!

Joint work with Ankit Garg, Leonid Gurvits and Avi Wigderson.


Monday, January 23rd

Zeev Dvir, Princeton University

"Rank bounds for design matrices with block entries and geometric applications"

Time: 2:00 PM
Location: Hill 705
Abstract: Design matrices are sparse matrices in which the supports of different columns intersect in a few positions. Such matrices come up naturally when studying problems involving point sets with many collinear triples. In this work we consider design matrices with block (or matrix) entries. Our main result is a lower bound on the rank of such matrices, extending the bounds proven in [BDWY12, DSW14] for the scalar case. As a result we obtain several applications in combinatorial geometry. The main application involves extending the notion of combinatorial rigidity from pairwise distance constraints to three wise collinearities. The main technical tool in the proof of the rank bound is an extension of the technique of matrix scaling to the setting of block matrices. We generalize the definition of doubly stochastic matrices to matrices with block entries and derive sufficient conditions for a doubly stochastic scaling to exist. Joint work with Ankit Garg, Rafael Oliveira and Jozsef Solymosi


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