School of Mathematics

An Isoperimetric Inequality for the Hamming Cube and Integrality Gaps in Bounded-Degree Graphs

Siavosh Benabbas
Institute for Advanced Study
November 21, 2011
In 1970s Paul Erdos asked the following question: Consider all the boolean strings of length n. Assume that one has chosen a subset S of the strings such that no two chosen strings are different in precisely n/4 (or its closest even integer) coordinates. How big can the set of chosen strings be? Erdos conjectured that the answer is small (in a precise sense) and put a $250 prize for a solution. In 1987 Frankl and Rodl proved a strong form of this conjecture showing that such a set has to be exponentially smaller than the set of all strings of length n.

Orientability and Open Gromov-Witten Invariants

Penka Georgieva
Princeton University
November 11, 2011

I will first discuss the orientability of the moduli spaces of J-holomorphic maps with Lagrangian boundary conditions. It is known that these spaces are not always orientable and I will explain what the obstruction depends on. Then, in the presence of an anti-symplectic involution on the target, I will give a construction of open Gromov-Witten disk invariants. This is a generalization to higher dimensions of the works of Cho and Solomon, and is related to the invariants defined by Welschinger


Around the Davenport-Heilbronn Function

Enrico Bombieri
Institute for Advanced Study
November 10, 2011

The Davenport-Heilbronn function (introduced by Titchmarsh) is a linear combination of the two L-functions with a complex character mod 5, with a functional equation of L-function type but for which the analogue of the Riemann hypothesis fails. In this lecture, we study the Moebius inversion for functions of this type and show how its behavior is related to the distribution of zeros in the half-plane of absolute convergence. Work in collaboration with Amit Ghosh.

Vertex Sparsification: An Introduction, Connections and Applications

Ankur Moitra
Massachusetts Institute of Technology; Institute for Advanced Study
November 8, 2011

The notion of exactly (or approximately) representing certain combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are given a graph $G = (V, E)$ and a set of terminals $K \subset V$ and our goal is to find one single graph $H = (K, E_H)$ on just the terminal set so that $H$ approximately preserves the minimum cut between every bi-partition of the terminals.

Strong and Weak Epsilon Nets and Their Applications

Noga Alon
Tel Aviv University; Institute for Advanced Study
November 7, 2011

I will describe the notions of strong and weak epsilon nets in range spaces, and explain briefly some of their many applications in Discrete Geometry and Combinatorics, focusing on several recent results in the investigation of the extremal questions that arise in the area, and mentioning some of the remaining open problems.

How Bad is Forming Your Own Opinion

Sigal Oren
Cornell University
November 7, 2011

A long-standing line of work in economic theory has studied models by which a group of people in a social network, each holding a numerical opinion, can arrive at a shared opinion through repeated averaging with their neighbors in the network. Motivated by the observation that consensus is rarely reached in real opinion dynamics, we study a related sociological model in which individuals’ intrinsic beliefs counterbalance the averaging process and yield a diversity of opinions.