Rutgers Discrete Math Seminar Spring 2009

the way mentioning a few results and several interesting open problems.

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.

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.

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.

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.

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.

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.

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.)

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.

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.

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.