This is a 23-lecture course, with each lecture being 75 minutes, given by Spencer Unger and Assaf Rinot.
This course will present a rigorous study of advanced set-theoretic methods including forcing, large cardinals, and methods of infinite combinatorics and Ramsey theory. An emphasis will be placed on their applications in algebra, topology, and real and functional analysis.
We will discuss some old and new problems and results, mostly of Ramsey-theoretical and number-theoretical nature, which involve the additive and multiplicative structures in ℕ.
We improve the upper bound for diagonal Ramsey numbers to R(k+1,k+1) ≤ exp(-c(log k)2)(2k)!/(k!)2 for k ≥ 3. To do so, we build on a quasirandomness and induction framework for Ramsey numbers introduced by Thomason and extended by Conlon, demonstrating optimal 'effective quasirandomness' results about convergence of graphs. This optimality represents a natural barrier to improvement.
The breakthrough result of Chattopadhyay and Zuckerman gives a reduction from the construction of explicit non-malleable extractors to the construction of explicit two-source extractors and bipartite Ramsey graphs. However, even assuming the existence of optimal explicit non-malleable extractors only gives a two-source extractor (or a Ramsey graph) for poly(log n) entropy, rather than the optimal O(log n). In this paper we modify the construction to solve the above barrier. Using the currently best explicit non-malleable extractors we get an explicit bipartite Ramsey graphs for sets of size 2k, for k=O(log n log log n). Any further improvement in the construction of non-malleable extractors would immediately yield a corresponding two-source extractor. Intuitively, Chattopadhyay and Zuckerman use an extractor as a sampler, and we observe that one could use a weaker object - a somewhere-random condenser with a small entropy gap and a very short seed. We also show how to explicitly construct this weaker object using the Raz et al. error reduction technique, and the constant degree dispersers of Zuckerman that also work against extremely small tests.
Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bit. However, most sources of randomness in nature are defective and at best, only contain some amount of entropy. This leads to the area of randomness extraction, where an extractor is a deterministic procedure to produce pure random bits from a weak source. A central open problem (from the 80s) in this area is to extract from 2 independent weak sources (it is known that it is impossible to extract from just 1 weak source). In joint work with David Zuckerman, we resolve this problem. I will discuss the main ideas we use to solve this problem.
As a corollary of our 2-source extractor, we obtain exponential improvements in explicit constructions of Ramsey graphs, a central object in extremal combinatorics. This is in a line of work spanning the last 70 years in an attempt to meet Erdős's challenge of matching the probabilistic method.
You must be logged in to post a comment.