# Rutgers Discrete Math Seminar 2009

For directions to the Hill Center you may wish to consult this page, which is maintained by the Rutgers Department of Mathematics. Room 525 is on the 5th floor, turning right twice as you exit the elevator.

## Tuesday, February 3 2009

 Speaker: Mike Neiman, Department of Mathematics, Rutgers University. Title: Negative correlation inequalities Abstract: I will talk about negative correlation inequalities for some discrete probabilistic models, along the way mentioning a few results and several interesting open problems. Time: 2pm Venue: Hill 425

## Tuesday, February 10 2009

 Speaker: Julia Wolf, Department of Mathematics, Rutgers University. Title: Monochromatic structures in the integers Abstract: Our main goal will be to derive an upper and a lower bound on the minimum number of monochromatic 4-term arithmetic progressions in any 2-colouring of Z/pZ. We will touch on the subject of quadratic Fourier analysis as well as a related question in graph theory along the way. The talk aims to be accessible to graduate students, and will include several interesting open problems. Time: 2pm Venue: Hill 425

## Tuesday, February 17 2009

 Speaker: Gabor Kun, DIMACS and School of Mathematics, Institute for Advanced Study. Title: The asymptotical version of the Bollobas-Catlin-Eldridge conjecture Abstract: We say that the graphs G and H with n vertices pack if G and H can be embedded to the same vertex with no overlapping edges. Bollobas, Eldridge and independently Catlin conjectured that if that if (M(G)+1)(M(H)+1) < n+2 holds for the maximal degress then G and H pack. Aigner and Brandt and independently Alon and Fischer proved this in the case M(G),M(H)<3, Csaba, Shokoufandeh and Szemeredi if M(G),M(H)<4. Bollobas, Kostochka and Nakprasit settled the case when one of the graphs is degenerate. Kaul, Kostochka and Yu showed that if M(G)M(H)<3/5n and the maximal degrees are large enough then G and H pack. We prove an asymptotic version of the conjecture: For every epsilon > 0 there is D that if M(G),M(H)>D and M(G)M(H)<(1-epsilon)n then G and H pack. Time: 2pm Venue: Hill 425

## Tuesday, February 24 2009

 Speaker: Jacob Fox, Department of Mathematics, Princeton University. Title: Hypergraph Ramsey Numbers Abstract: The Ramsey number r_k(s,n) is the minimum N such that every red-blue coloring of the k-tuples of an N-element set contains either a red set of size s or a blue set of size n, where a set is called red (blue) if all k-tuples from this set are red (blue). In this talk we present new estimates for several hypergraph Ramsey problems. We give a new upper bound for r_k(s,n) for k > 2 and s fixed. In particular, we show that r_3(s,n) \leq 2^{n^{s-2}\log n}, which improves by a factor of n^{s-2}/polylog n the exponent of the previous upper bound of Erdos and Rado from 1952. Next we obtain a new lower bound for these numbers, showing that r_3(s,n) > 2^{c sn \log (n/s)} for all 3 < s < n. When s is a constant, it gives the first superexponential lower bound for r_3(s,n), answering an open question posed by Erdos and Hajnal in 1972. Finally, if time permits, we report on progress which we made on related hypergraph Ramsey problems. Joint work with David Conlon and Benny Sudakov. Time: 2pm Venue: Hill 425

## Tuesday, March 3 2009

 Speaker: Russell Impagliazzo, Department of Computer Science, UCSD, and IAS. Title: Algorithmic versions of dense model theorems Abstract: Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler showed some general conditions under which such a model exists. Reingold, Trevisan, Tulsiani and Vadhan give a quantitatively improved characterization obtained using an argument based on the Impagliazzo hard-core set theorem from computational complexity. Gowers independently obtained a similar improvement. Recent work by Trevisan, Tulsiani and Vadhan gives a generalization that implies versions of both the hard-core set theorem and the dense model theorem, and gives several applications. Here, we show that the condition under which such models exist can be generalized with a concept we call pseudo-density. We also show that the existence of models can be reduced directly to the improved hardcore distribution results of Holenstein. Using Holenstein's uniform proof of an optimal density hard-core set theorem, we show that the dense models that one derives have a canonical form, with models being (sampleable from) functions defined in terms of tests from the original class. We also give general conditions under which (descriptions of) such models can be efficiently computed. We give some applications, several of which are versions of known results. 1. An immediate application is the connection between computational pseudo-density and pseudo-min-entropy, for distributions of high pseudo-min-entropy. This connection was first observed by Barak, Shaltiel, and Wigderson and implies the dense model theorems. 2. Following RTTV08 and TTV08, we look at tests that are cuts in graphs to get conditions on when a sparse graph looks like'' a dense graph. We reprove and generalize results of Kohayakawa (Koh97) and Alon, Coja-Oghlan, Han, Kang, Rodl, and Schacht (ACHKRS07). 3. As toy examples, we apply the general results to sets of tests consisting of monomials or small juntas. For example, we show that for each k, C there are l, delta so that for any distribution D over the hypercube, either there is an l-junta that has at least a delta probability of being true under the uniform distribution and is C times as likely under D as it is in the uniform distribution, or there is a distribution D' delta-indistinguishable from D by k-juntas, where D' has relative measure at least delta within the uniform distribution, and D'(x_1,..x_n) only depends on at most l of its coordinates. Time: 2pm Venue: Hill 425

## Tuesday, March 10 2009

 Speaker: Mario Szegedy, Department of Computer Science, Rutgers University. Title: A new line of attack on the dichotomy conjecture Abstract: A well known result of Ladner says that under P not= NP there are problems in NP that are neither NP hard nor polynomial time solvable. For the (sub)class of constraint satisfaction problems (CSP), however, nothing excludes the above dichotomy. In fact, Feder and Vardi conjecture that every constraint satisfaction problem is either NP complete or polynomial time solvable. We give an entirely new set of ideas to tacle this conjecture, and reprove the Hell-Nesetril theorem, which states that every CSP with a single symmetric binary relation is either polynomial time solvable or NP complete. Time: 2pm Venue: Hill 425

Spring Break.

## Tuesday, March 24 2009

 Speaker: Po-Shen Loh, Department of Mathematics, Princeton University. Title: Maximizing the number of colorings Abstract: Let P_G(q) denote the number of proper q-colorings of a graph G. This function, called the chromatic polynomial of G, was introduced by Birkhoff in 1912, who sought to attack the famous four-color problem by minimizing P_G(4) over all planar graphs G. Since then, motivated by a variety of applications, much research was done on minimizing or maximizing P_G(q) over various families of graphs. In this work, we study an old problem of Linial and Wilf, to find the graphs with n vertices and m edges which maximize the number of q-colorings. We provide the first approach which enables one to solve this problem for many nontrivial ranges of parameters. Using our machinery, we show that for each q leq 4 and sufficiently large m < kappa_q n^2 where kappa_q \approx 1/(q \log q), the extremal graphs are complete bipartite graphs minus the edges of a star, plus isolated vertices. Moreover, for q=3, we establish the structure of optimal graphs for all large m \leq n^2/4, confirming (in a stronger form) a conjecture of Lazebnik from 1989. Joint work with Oleg Pikhurko and Benny Sudakov. Time: 2pm Venue: Hill 425

DIMACS workshop.

## Tuesday, April 7 2009

 Speaker: Derrick Hart, Department of Mathematics, Rutgers University. Title: Sums and products in C[x] Abstract: Suppose that A is a finite subset of real numbers. A conjecture of Erdos and Szemeredi says that either the set of sums or the set of products of A, must be at least |A|^(2-o(1)), where the o(1) tends to 0 as |A| tends to infinity. We will present some results concerning an analogue of this conjecture in the case that A is a subset of the monic polynomials in C[x]. (Joint work with Ernie Croot.) Time: 2pm Venue: Hill 425

## Tuesday, April 14 2009

 Speaker: Kevin O'Bryant, Department of Mathematics, CUNY. Title: Sets without long arithmetic progressions Abstract: A k-term arithmetic progression is a set of integers of the form a+d, a+2d, ..., a+kd, with d>0. We will present the thickest known construction of subsets of {1,2,...,N} (for large N) that do not contain k-term arithmetic progressions. This construction is based on earlier constructions of Behrend, Rankin, Elkin, and Green & Wolf. Details are available at arXiv:0811.3057. Time: 2pm Venue: Hill 425

## Tuesday, April 21 2009

 Speaker: Emanuel Milman, School of Mathematics, Institute for Advanced Study. Title: Isoperimetric and Concentration Inequalities, and their applications Abstract: The classical isoperimetric inequality in Euclidean space asserts that among all sets of given Lebesgue measure, the Euclidean ball minimizes surface area. Using a suitable generalization of surface area, isoperimetric inequalities may be investigated on general metric spaces equipped with a measure, such as Euclidean space equipped with the standard Gaussian measure. In the discrete setting, a prime example is given by expander graphs. One important reason for studying isoperimetric inequalities is that they easily imply concentration inequalities, which are very useful in applications. The latter do not provide infinitesimal information on boundary measure of sets, but are rather concerned with large-deviation information, bounding above the measure of sets separated from sets having half the total measure, as a function of their mutual distance in the large. In general, concentration inequalities cannot imply back isoperimetric inequalities. We will show that under a suitable (possibly negative) lower bound on an appropriate curvature tensor (combining information from both the geometry of the space and the associated measure), completely general concentration inequalities imply back their isoperimetric counterparts, up to dimension independent bounds, which is crucial for applications. Contrary to previous attempts which could only produce dimension dependent bounds, our method is entirely geometric, following the approach set forth by M. Gromov and recently adapted by F. Morgan. We will also mention several applications of the main result to Spectral Geometry and Statistical Mechanics, involving estimation and stability of spectral gap and log-Sobolev inequalities. Although our results are formulated in the continuous setting, we will make sure to indicate possible analogies and extensions to the graph setting throughout the talk. Time: 2pm Venue: Hill 425

## Tuesday, April 28 2009

 Speaker: Wesley Pegden, Department of Mathematics, Rutgers University. Title: Highly nonrepetitive sequences: winning strategies from the Local Lemma Abstract: A theorem of J. Beck, proved probabilistically with the Lovasz Local Lemma, asserts that there is an infinite binary sequence in which any long identical blocks are exponentially far apart: more precisely, for any eps, there is an N_eps such that any identical blocks of length n > N_eps lie at distance > (2-eps)^n. We prove that a similar result can be achieved even with only limited control over the sequence---that is, we prove that if two players take turns selecting binary digits to form an unending sequence, Player 1 has a strategy to ensure that there will be no identical blocks of length n > N_eps within distance (2-eps)^{n/2} of each other, even if Player 2 is trying to achieve that there are such close long identical blocks. The existence of Player 1's winning strategy is proved probabilistically, via an extension of the Local Lemma which can dramatically reduce the number of edges needed in a dependency graph when there is an ordering underlying the significant dependencies of events. The same method allows us to prove other theorems with the same theme; for example, we show that for sufficiently large base c (e.g. c \geq 37), Player 1 has a strategy which avoids repetition of any blocks of lengths \geq 2 in the c-ary sequence game, giving a natural game-theoretic analog to Thue's original theorem on nonrepetitive sequences. These results appear to represent the first successful application of a Local Lemma to games. Time: 2pm Venue: Hill 425

## Thursday, September 10 2009

 Speaker: Van Vu, Rutgers University Title: Random matrices: Universality of local eigenvalue statistics Abstract: One of the main goals of the theory of random matrices is to establish the limiting distributions of the eigenvalues. In the 1950s, Wigner proved his famous semi-cirle law (subsequently extended by Anord, Pastur and others), which established the global distribution of the eigenvalues of random Hermitian matrices. In the last fifty years or so, the focus of the theory has been on the local distributions, such as the distribution of the gaps between consecutive eigenvalues, the k-point correlations, the local fluctuation of a particular eigenvalue, or the distribution of the least singular value. Many of these problems have connections to other fields of mathematics, such as combinatorics, number theory, statistics and numerical linear algebra. Most of the local statistics can be computed explicitly for random matrices with gaussian entries (GUE or GOE), thanks to Ginibre's formulae of the joint density of eigenvalues. It has been conjectured that these results can be extended to other models of random matrices. This is generally known as the Universality phenomenon, with several specific conjectures posed by Wigner, Dyson, Mehta etc. In this talk, we would like to discuss recent progresses concerning the Universality phenomenon, focusing on a recent result (obtained jointly with T. Tao), which asserts that all local statistics of eigenvalues of a random matrix are determined by the first four moments of the entries. This (combining with results of Johansson, Erdos-Ramirez-Schlein-Yau and many others) provides answers to several old problems. Time: 2pm Venue: Hill 705 NOTE: *JOINT WITH MATHEMATICAL PHYSICS SEMINAR!*

## Thursday, September 17 2009

 Speaker: Van Vu, Rutgers University Title: Some problems with random Bernoulli matrices Abstract: I will discuss the state of the art of several well-known problems concerning random Bernoulli matrices (both symmetric and non-symmetric models). There will be many open questions. The topics include: (1) The singularity problem: How often is a random matrix singular ? (2) The determinant problem: How large is the typical determinant of a random matrix ? How is it distributed ? (3) The permanent problem: How large is the typical permanent of a random matrix and how often is it equal zero ? (4) The eigenvector problems: How does a typical eigenvector look like ? (5) The permanent estimating problem: One can use a random determinant to estimate the permanent of a deterministic matrix. How accurate is this estimator ? Time: 2pm Venue: Hill 525

## Thursday, September 24 2009

 Speaker: Maria Chudnovsky, Columbia University Title: Large cliques and stable sets in graphs with no 4-edge paths or 5-edge antipaths Abstract: For every fixed graph H, if a graph G does not contian H as a minor, then one can say a lot about the structure and properties of H. Unfortunately, results of that kind do not seem to be true if we replace the minor containment by induced subgraph containment. One of the few conjectures about general behavior of graphs with certian induced subgraphs forbidden is the Erdos Hajnal Conjecture. It states that for every fixed graph H there exists a constant δ(H), such that if a graph G has no iduced subgraph isomorphic to H, then G contains a big clique or a big stable set of size |V(G)|^δ(H). The Erdos Hajal Conjecture is known to be true for graphs H on at most four vertices, but there are some five-vertex graphs for which the conjecture is still open. One of such graphs is a path of length four (edges). We prove that if a graph G does not contain as induced subgraphs a path of length four or the complement of a path of length five, then G contains a clique or a stable set of size |V(G)|^(1/6). This is joint work with Yori Zwols. Time: 2:20pm Venue: Hill 525 NOTE: *SPECIAL TIME!*

## Thursday, October 1 2009

 Speaker: Hamed Hatami, Institute for Advanced Study Title: Graph norms and Sidorenko's conjecture Abstract: I will prove some results in the direction of answering a question of Lovasz about the norms defined by certain combinatorial structures. Inspired by the similarity of the definitions of L_p norms, trace norms, and Gowers norms, we introduce and study a wide class of norms containing these, as well as many other norms. It will be proven that every norm in this class must satisfy a Cauchy-Schwarz-Gowers type inequality. I will show an application of this inequality to a conjecture of Sidorenko about subgraph densities. Time: 2pm Venue: Hill 525

## Thursday, October 8 2009

No seminar. IPAM workshop.

## Thursday, October 15 2009

 Speaker: Liviu Ilinca, Rutgers University Title: The number of 3-SAT functions Abstract: A k-SAT function is a Boolean function representable by a k-SAT formula in, say, disjunctive normal form. Let G(k,n) be the number of k-SAT functions of n variables. We show that G(3,n) is asymptotic to 2^{n + {n \choose 3}}, a strong form of a conjecture of Bollobas, Brightwell and Leader. (Joint with Jeff Kahn) Time: 2pm Venue: Hill 525

## Friday, October 30 2009

 Speaker: Ben Green, University of Cambridge and Radcliffe Institute at Harvard University Title: The inverse conjectures for the Gowers norms Abstract: For the last 5 years or so Terry Tao and I have been working on a programme to prove certain conjectures of Hardy and Littlewood concerning the number of primes vectors p = (p_1,...,p_n) in some box which satisfy the equation Ap = b. The number of such solutions should be determined, asymptotically, by "local" considerations and our aim is to prove this provided that A is "nondegenerate" (which, sadly, means we do not propose to resolve the twin prime or Goldbach conjectures). In 2006 we reduced this task to that of proving two families of conjectures. We established the first of these in 2007, leaving the task of proving the second family of conjectures, known as the "inverse conjectures for the Gowers norms". There is one of these for each of the so-called Gowers norms U^2,U^3,U^4,... The inverse conjecture for the U^2 norm can be proved by about one line of harmonic analysis, and the inverse conjecture for the U^3 norm was proved in a 70-page paper of Tao and I. Recently, with Tammy Ziegler, we appear to have established the general case, although we have only worked out and written up all the details in the case of the U^4 norm. The paper handling this case is a mere 40 pages long, and I propose to talk about some aspects of this result. I shall not dwell on details of the proof, being more concerned with giving an overview of the area. I will not assume that the audience knows much (anything) about the subject at all (for example, I shall not be assuming the definition of Gowers norm). Time: 4pm Venue: Hill 705 NOTE: *THIS IS A DEPARTMENT COLLOQUIUM! SPECIAL DATE, TIME AND VENUE!*

## Thursday, November 5 2009

 Speaker: Zeev Dvir, Institute for Advanced Study Title: New bounds on the size of Kakeya sets in finite fields and applications Abstract: A Kakeya set is a set in (F_q)^n (the n dimensional vector space over a field of q elements) which contains a line in every direction. In this talk I will present a recent result which gives a lower bound of (q/2)^n on the size of such sets. This bound is tight to within a multiplicative factor of two from the known upper bounds. The proof extends the polyomial methods used in [Dvir 08, Saraf Sudan 08] and uses polynomials of unbounded degree. This new bound can be used to derive new results on randomness mergers and extractors which are of interest in computational complexity. In the talk I will show the proof of the improved Kakeya bound and discuss the applications/connections to computer science. Based on Joint work with S. Kopparty, S. Saraf and M. Sudan. Time: 2pm Venue: Hill 525

## Thursday, November 12 2009

 Speaker: Hoi Nguyen, Rutgers University Title: An optimal version of the inverse Littlewood-Offord theorem Abstract: Let V={v_1,..,v_n} be a multiset of n real numbers. Let eta_i be i.i.d. Bernoulli random variables. The concentration probability P(V) of V is defined as P(V):=sup_v P(eta_1 v_1+..+eta_n v_n = v). A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the v_i are non-zero, then the concentration probability of V is O(n^{-1/2}). In the reverse direction, Tao and Vu proved that any set of large concentration probability must have structure. In this talk, we will provide a general approach that gives an almost best possible characterization for all such V. This allows us to recover several previous forward Littlewood-Offord results, including a significant result of Stanley from the 1980s on the optimal value of P(V) when v_i are distinct. (Joint with Van Vu, Rutgers University) Time: 2pm Venue: Hill 525

## Thursday, November 19 2009

 Speaker: Linh Tran, Rutgers University Title: Piercing random boxes Abstract: Consider a set of n random axis parallel boxes in the unit hyper-cube in R^d, where d is fixed and n tends to infinity. We show that the minimum number of points one needs to pierce all these boxes is, with high probability, at least Omega_d(sqrt{n}(log n)^{d/2-1}) and at most O_d(sqrt{n}(log n)^{d/2-1} loglog n). Time: 2pm Venue: Hill 525

## Thursday, November 26 2009

No seminar. Thanksgiving.

## Thursday, December 3 2009

No seminar. Another IPAM workshop.

This page was last updated 2nd September 2009.