## Organizer(s) | Jeffry Kahn, Jacob D Baron, Patrick Devlin | ## Archive |

## Upcoming Talks

## Monday, March 27th |

## Van Vu, |

## "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, |

## "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 , |

## "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, |

## "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, |

## "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, |

## "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, |

## "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, |

## "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, |

## "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 |