Mathematics Department - Discrete Math - Spring 2017

# Discrete Math - Spring 2017

### Organizer(s)

Jeffry Kahn, Jacob D Baron, Patrick Devlin

## Monday, April 24th

### "Extremal problems for paths in graphs and hypergraphs"

Time: 2:00 PM
Location: Hill 705
Abstract: The ErdH{o}s--Gallai Theorem states that any $n$-vertex graph without a $k$-edge path has at most $frac{1}{2}(k-1)n$ edges. In this talk, various generalizations of this theorem for graphs and hypergraphs will be discussed, using a number of novel combinatorial, geometric and probabilistic methods. A representative of our results is the following generalization of the ErdH{o}s--Gallai Theorem. A {em tight $k$-path} is the hypergraph comprising edges ${i,i + 1,dots,i + r - 1}$, where $1 leq i leq k$. We give a short proof that if $H$ is an $r$-uniform $n$-vertex hypergraph not containing a tight $k$-path, then [ |H| leq frac{k-1}{r}{n choose r - 1}.] As noted by Kalai, equality holds whenever certain Steiner systems exist. This result proves a conjecture of Kalai for tight paths. We conclude with a number of open problems. One particular open problem, posed by V. S'{o}s and the speaker at AIM, is whether the maximum number of edges in an $r$-uniform $n$-vertex hypergraph containing no {em tight cycle} is at most ${n - 1 choose r - 1}$. Joint work with Z. F"{u}redi, T. Jiang, A. Kostochka and D. Mubayi.

## Monday, April 17th

### "A spectral gap precludes low-dimensional embeddings."

Time: 2:00 PM
Location: Hill 705
Abstract: We prove that if an $n$-vertex $O(1)$-expander graph embeds with average distortion $D$ into a finite dimensional normed space $X$, then necessarily the dimension of $X$ is at least $n^{c/D}$ for some universal constant $c>0$. This is sharp up to the value of the constant $c$, and it improves over the previously best-known estimate $mathrm{dim}(X)> c(log n)^2/D^2$.

## Monday, April 10th

### "Two proofs of the existence of Ramanujan graphs"

Time: 2:00 PM
Location: Hill 705
Abstract: This talk will review two results showing the existence of Ramanujan graphs. While both methods employ the method of interlacing polynomials, they are thematically quite different. The goal will be to highlight some of the commonalities and differences, as these might suggest when each proof technique might be usable in other problems. The talk is based on joint work with Dan Spielman and Nikhil Srivastava.

## Monday, April 3rd

### "Embedding Large Graphs in Random Graphs"

Time: 2:00 PM
Location: Hill 705
Abstract: In this talk, we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $Deltageq 5$, $varepsilon > 0$ and let $H$ be a graph on $(1-varepsilon)n$ vertices and with maximum degree $Delta$. We show that a random graph $G_{n,p}$ with high probability contains a copy of $H$, provided that $pgg (n^{-1}log^{1/Delta}n)^{2/(Delta+1)}$. Our assumption on $p$ is optimal up to the $polylog$ factor. Time permitting, we will discuss recent progress on the "universality" problem, which entails finding the threshold for all graphs of degree at most $Delta$ to appear in $G_{n,p}$ emph{simultaneously}.

## Monday, March 27th

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

## Monday, March 20th

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

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

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

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

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

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

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

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