Mathematics Department - Discrete Math - Fall 2013

# Discrete Math - Fall 2013

### Organizer(s)

Jeffry Kahn, Hao Huang

## Tuesday, December 3rd

### "Sum-free subgroups"

Time: 2:00 PM
Location: Hill 525
Abstract: The study of sum and product problems in finite fields motivates the investigation of additive structures in multiplicative subgroups of such fields. It turns out that such subgroups that are sufficiently large with respect to the size of the field must contain rich structures of additive relations, while even prime fields may contain sum-free multiplicative subgroups of substantial size. The study of this topic combines combinatorial techniques with tools from algebraic and analytic number theory. Joint work with Jean Bourgain.

## Tuesday, November 26th - CANCELLED

### "Recent progress in distinct distances problems"

Time: 2:00 PM
Location: Hill 525
Abstract: During 2013, significant progress has been obtained for several problems that are related to the Erdos distinct distances problem. In this talk I plan to briefly describe some of these results and the tools that they rely on. I will focus on the following two results. Let P and P' be two sets of points in the plane, so that P is contained in a line L, P' is contained in a line L', and L and L' are neither parallel nor orthogonal. Then the number of distinct distances determined by the pairs of PxP' is Omega(min{|P|^{2/3}|P'|^{2/3},|P|^2, |P'|^2}). In particular, if |P|=|P'|=m, then the number of these distinct distances is Omega(m^{4/3}), improving upon the previous bound Omega(m^{5/4}) of Elekes. In the second result, we study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set P of n points determines o(n) distinct distances, then no line contains Omega(n^{7/8}) points of P and no circle contains Omega(n^{5/6}) points of P. In both cases, we rely on a bipartite and partial variant of the Elekes-Sharir framework, which has been used by Guth and Katz in their 2010 solution of the general distinct distances problem. We combine this framework with some basic algebraic geometry, with a theorem from additive combinatorics by Elekes, Nathanson, and Ruzsa, and with a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang. The first result is a joint work Micha Sharir (Tel Aviv) and József Solymosi (UBC). The second is a joint work with Joshua Zahl (MIT) and Frank de Zeeuw (EPFL).

## Tuesday, November 19th

### "Breaking the quadratic barrier for 3 query LCCs over the reals"

Time: 2:00 PM
Location: Hill 525
Abstract: Locally Correctable Codes (LCCs) are error correcting codes in which one can recover the values of a possibly corrupted codeword position using a small number of queries to the other positions. Such codes include Reed Muller codes and Hadamard codes and they play an important part in many results in theoretical computer science, including in hardness of approximation, derandomization and PCPs. It is a major open problem to understand the power and limitations of such codes. Until now, the best lower bound on the encoding length of constant query codes with more than 2 queries was quadratic. This was also the case for *linear* codes. We prove that 3-query linear LCCs over the field of real numbers require encoding length which is super quadratic (d^{2.001}). Geometrically, this means that if \$n\$ vectors in \$R^d\$ are such that each vector is spanned by a linear number of disjoint triples of others, then it must be that \$n > d^{2.001}\$. While a modest improvement on the known bounds, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries, possibly over other fields as well. Joint work with Shubhangi Saraf (Rutgers) and Avi Wigderson (IAS).

## Tuesday, November 12th

### "The Green-Tao theorem and a relative Szemerédi theorem"

Time: 2:00 PM
Location: Hill 525
Abstract: The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and discuss our recent simplifications. One of the main ingredients in the proof is a relative Szemerédi theorem, which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. Our main advance is a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition suffices. Based on joint work with David Conlon and Jacob Fox.

## Tuesday, November 5th

### "The structure of graphs with no cycles of length divisible by three"

Time: 2:00 PM
Location: Hill 525
Abstract: For a graph G, let #E(G) be the number of stable sets of even size and let #O(G) be the number of stable sets of odd size. We are interested in the relation between the structure of a graph and the value of |#E(G)-#O(G)|. As it turns out, |#E(G)-#O(G)| has small value in many natural situations, and the simplest examples where |#E(G)-#O(G)| is larger than 1 are complete graphs, and cycles of length divisible by 3. Kalai and Meshulam made a conjecture that if |#E(H)-#O(H)| is bounded for all induced subgraphs H of G, then the chromatic number of G is bounded; they also conjectured that if G has no induced cycle of length divisible by 3, then G has bounded chromatic number. These two conjectures lead us to study the following question: is it true that if a graph G has no induced cycle of length divisible by 3, then |#E(G)-#O(G)| is at most one? In this talk we discuss a special case of this problem, and give a complete structural description of graphs with no cycle of length divisible by 3 (not necessarily induced). The proof of the conjecture in this special case follows directly from the results of the decomposition. Joint work with Maria Chudnovsky, Alex Scott and Paul Seymour.

## Tuesday, October 29th

### "Two approaches to Sidorenko's conjecture"

Time: 2:00 PM
Location: Hill 525
Abstract: Sidorenko's conjecture states that the number of homomorphisms from a bipartite graph H to a graph G is asymptotically at least the expected number of homomorphisms from H to the binomial random graph with the same expected edge density as G. In this talk, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph H with bipartition (A, B) is tree-arrangeable if neighborhoods of vertices in A have a certain tree-like structure. We show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. This generalizes a recent result of Conlon, Fox, and Sudakov that Sidorenko's conjecture holds if A has a vertex adjacent to all vertices in B. Second, we develop a recursive procedure that constructs a new graph that satisfies Sidorenko's conjecture from a graph known to satisfy Sidorenko's conjecture. This approach yields a simple proof of the statement that hypercubes satisfy Sidorenko's conjecture, which was first proven by Hatami. Joint w/ Jeong Han Kim (KIAS) and Joonkyung Lee (Oxford)

## Tuesday, October 22nd

### "Matrix perturbation bounds with random noise and applications"

Time: 2:00 PM
Location: Hill 525
Abstract: Classical matrix perturbation bounds, such as Weyl (for eigenvalues) and David-Kahan (for eigenvectors) have, for a long time, been playing an important role in various areas: numerical analysis, combinatorics, theoretical computer science, statistics, machine learning, etc. In this talk, I am going to discuss a popular setting where the perturbation is random and the original matrix (data) is low rank (or approximately low rank). In this case, we can significantly improve the classical bounds mentioned above. As an application, I will discuss a simple universal approach to several matrix recovery problems, such as the hidden clique problem, the hidden coloring problem, the clustering problem, the Netflix problem, etc. In certain cases, our method leads to results beyond the currently known. Joint work with S. O'rourke (Yale) and K. Wang (IMA)

## Tuesday, October 15th

### "The minimum number of nonnegative edges in hypergraphs"

Time: 2:00 PM
Location: Hill 525
Abstract: An r-unform n-vertex hypergraph H is said to have the Manickam-Miklos-Singhi (MMS) property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H. In this talk I will show that for n>10r^3, every r-uniform n-vertex hypergraph with equal codegrees has the MMS property, and the bound on n is essentially tight up to a constant factor. An immediate corollary of this result is the vector space Manickam-Miklos-Singhi conjecture which states that for n>=4k and any weighting on the 1-dimensional subspaces of F_q^n with nonnegative sum, the number of nonnegative k-dimensional subspaces is at least \${n-1 brack k-1}_q\$. I will also discuss two additional generalizations, which can be regarded as analogues of the Erdos-Ko-Rado theorem on k-intersecting families. This is joint work with Benny Sudakov.

## Tuesday, October 8th

### "What is snapshot randomness?"

Time: 2:00 PM
Location: Hill 525
Abstract: Randomness is not a well-defined mathematical concept (like perpendicularity of lines); nevertheless it is widely used in math and physics as a guiding intuition. The concept of Snapshot Randomness comes up in a natural way of studying the time-evolution of a large closed system (e.g. many point billiards in motion either in a box or on a sphere) as the system goes from far-from-equilibrium to equilibrium. Our basic question is this: how long does it take to reach a stage of ``complete randomness"? If you want to hear an answer--a theorem--come to my talk.

## Tuesday, October 1st

### "Independent sets in graphs with given minimum degree"

Time: 2:00 PM
Location: Hill 525
Abstract: There has been quite a bit of recent research involving extremal problems for the enumeration of certain graph substructures. For example, Kahn used an entropy method to show that the number of independent sets in a d-regular bipartite graph on n vertices is at most \$(2^{d+1}-1)^{n/(2d)}\$. Zhao was able to show that this upper bound holds for general regular graphs. Galvin conjectured that if n >= 2d, then the number of independent sets in a graph with n vertices and minimum degree at least d is at most that in \$K_{d,n-d}\$. Galvin proved that the conjecture is true for a fixed d provided n is large. We were able to prove a strengthened version of Galvin's conjecture, covering the case when n<2d as well. In this talk, we will present the main ideas in the proof of this result. This is joint work with Jamie Radcliffe.

## Wednesday, September 25th

### "The algebraic and topological properties of claw-free graphs"

Time: 3:00 PM
Location: Hill 425
Abstract: We study two parameters that can be associated with a given graph. The first parameter is an algebraic one: the maximal eigenvalue of the Laplacian. The second parameter is a topological one: the connectivity of the simplicial complex of independent sets. These two parameter are useful in studying combinatorial properties of the graph, such as the existence of independent transversals. In a previous work with Aharoni and Meshulam, we showed that these two parameters are related. In this talk we show that for claw-free graphs we can obtained bounds for these parameters that are better than the ones known for general graphs. similar results are obtained for \$K_{1,k}\$-free\$ graphs for any k. This is joint work with Noga Alon and Ron Aharoni.

## Tuesday, September 17th

### "Disjoint Dijoins"

Time: 2:00 PM
Location: Hill 525
Abstract: A ``dijoin'' in a digraph is a set of edges meeting all directed cuts. The Lucchesi-Younger theorem says that if every dijoin has size at least k, then there are k pairwise disjoint directed cuts, and in 1976 Woodall proposed a dual statement, that if every directed cut has size at least k then there are k pairwise disjoint dijoins. This is still open. But Schrijver showed that it becomes false if we give the edges nonnegative integer capacities; it is not always true that if every directed cut has total capacity at least k, then there are k dijoins using each edge at most its capacity. In Schrijver's example, and in all others known, the edges with positive capacity form a disconnected graph, and perhaps the capacitated version is true if they form a connected graph. We have several partial results on this. Joint work with Maria Chudnovsky, Katherine Edwards, Ringi Kim and Alex Scott.