Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

May 31, 2010

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
10623 Berlin
room MA 041

Lecture - 14:15

Prasad Tetali - School of Mathematics and School of Computer Science, Georgia Tech

Combinatorial approach to an interpolation method and scaling limits for sparse random graphs

We establish the existence of free energy limits for several sparse random hypergraph models corresponding to certain combinatorial models on Erd{\"o}s-R\'{e}nyi graph $G(N,c/N)$ and random $r$-regular graph $G(N,r)$. For a variety of models, including independent sets, MAX-CUT, Coloring and K-SAT, we prove that the free energy both at a positive and zero temperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. In the zero temperature case, this is interpreted as the existence of the scaling limit for the corresponding combinatorial optimization problem. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p., thus resolving an open problem mentioned by several experts: Wormald '99, Aldous-Steele 2003, Bollob\'as-Riordan 2008, as well as Janson-Thomason 2008.

Our approach is based on extending and simplifying the Guerra-Toninelli interpolation method, as well as extending the work of Franz-Leone and Montanari. We provide a simpler combinatorial approach and work with the zero temperature case (optimization) directly both in the case of Erd{\"o}s-R\'{e}nyi graph $G(N,c/N)$ and random regular graph $G(N,r)$, while the previous authors handled the zero temperature case (for other models) by taking limits of positive temperature models. In addition we establish the large deviations principle for the satisfiability property for constraint satisfaction problems such as Coloring, K-SAT and NAE-K-SAT.

This is joint work with D. Gamarnik (MIT) and M. Bayati (Stanford).

Colloquium - 16:00

Gabriel Nivasch - Zürich

Weak epsilon-nets and the inverse Ackermann function

Let S be a finite point set in R^d, and let epsilon < 1 be a parameter. A "weak epsilon-net" for S ("for convex sets") is another set of points N which intersects the convex hull of every subset of S of size at least epsilon*|S|. It is known that the size of N need only depend on epsilon (and on d), but not on |S|. Let r = 1/epsilon.

We examine a special case where the given set S is "intrinsically one-dimensional", namely when S lies on a convex curve. (A convex curve in R^d is a curve that intersects every hyperplane at most d times, e.g. the moment curve..) We improve the previous bounds for this case (which were of the form O(r * polylog(r))), and prove that in this case there exists a weak 1/r-net N of size O(r * 2^poly(alpha(r))), where alpha(x) is the extremely slow-growing inverse Ackermann function.

We also prove a lower bound: For every fixed d>=3 and every r>1 there exists an S lying on a convex curve, for which every weak 1/r-net has size Omega(r * 2^poly(alpha(r))). The difference between the upper and the lower bound is that in the former, the polynomial in the exponent is of degree ~d^2/4, while in the latter it is of degree ~d/2.

The set S that achieves the lower bound is actually very simple: It is just a point set suitably "stretched out".

Joint work with Noga Alon, Boris Bukh, Haim Kaplan, Jiri Matousek, Micha Sharir, and Shakhar Smorodinsky.

Letzte Aktualisierung: 06.05.2010