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 4term arithmetic progressions in any 2colouring 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 BollobasCatlinEldridge 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)<(1epsilon)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 redblue coloring of the ktuples of an Nelement 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 ktuples 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^{s2}\log n}, which improves by a factor of
n^{s2}/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 hardcore 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 hardcore 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 pseudodensity.
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 hardcore 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 pseudodensity and pseudominentropy, for distributions of high pseudominentropy.
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, CojaOghlan, 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 ljunta 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'
deltaindistinguishable from D by kjuntas, 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 HellNesetril 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 
Tuesday, March 17 2009
Spring Break.
Tuesday, March 24 2009
Speaker: 
PoShen Loh, Department of Mathematics, Princeton University. 
Title: 
Maximizing the number of colorings 
Abstract: 
Let P_G(q) denote the number of proper qcolorings of a graph G.
This function, called the chromatic polynomial of G, was
introduced by Birkhoff in 1912, who sought to attack the famous
fourcolor 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
qcolorings. 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 
Tuesday, March 31 2009
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^(2o(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 kterm 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 kterm 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
largedeviation 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 logSobolev
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 > (2eps)^n. We prove that a similar result can be achieved even with only limited control over the sequencethat 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 (2eps)^{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 cary sequence game, giving a natural gametheoretic 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 semicirle 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 kpoint 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, ErdosRamirezSchleinYau 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
wellknown problems concerning random Bernoulli matrices
(both symmetric and nonsymmetric 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 4edge paths or
5edge 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 fivevertex 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 CauchySchwarzGowers 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 3SAT functions 
Abstract: 
A kSAT function is a Boolean function representable by a kSAT formula in, say, disjunctive normal form. Let G(k,n) be the number of kSAT 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 socalled
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 70page 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 LittlewoodOfford 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 LittlewoodOfford and Erdos from the 1940s
asserts that if the v_i are nonzero, 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 LittlewoodOfford 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 hypercube 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/21}) and at most O_d(sqrt{n}(log n)^{d/21} loglog n).

Time: 
2pm 
Venue: 
Hill 525 
Thursday, November 26 2009
No seminar. Thanksgiving.
Thursday, December 3 2009
No seminar. Another IPAM workshop.
