László Lovász - Spectra of graphs and geometric representations

Consider a weighted adjacency matrix $M$ of a graph $G$ (we allow negative edge-weights and arbitrary diagonal elements). There is natural embedding of $G$ in the nullspace of $M$, and this embedding connects interesting graph-theoretic properties with spectral properties of $M$. For example, for a $3$-connected planar graph such an embedding yields a representation of the graph as the skeleton of the convex $3$-polytope, provided $M$ has exactly one negative eigenvalue. However, it is not easy to find weighted adjacency matrices with appropriately large nullspace.

We describe some old and new results of this kind, including polynomial algorithms for the computation of appropriate matrices and connections with rigidity theory.
Back

Yuval Peres - Pinpointing mixing time and distance profiles in expanders

The Alon-Boppana bound yields the smallest possible value for the second eigenvalue of a d-regular graph; when this lower bound is (asymptotically) attained, the graph is called (weakly) Ramanujan. We determine precisely the mixing time of random walk on a d-regular (weakly) Ramanujan d-regular graph, and show it is the time it takes the walk to reach the maximum distance from its starting point. These walks exhibit cutoff: a sharp decrease of the total variation distance to the stationary measure in a relatively short time interval (for random $d$-regular graphs this was proved in 2010 by Lubetzky and Sly.) We deduce new information on typical distances in Ramanujan graphs. On the other hand, we show that for random graphs with a given (non-degenerate) degree distribution on ${3,4,...}$, mixing occurs long after the maximal distance from the starting point is reached; this is explained via a dimension drop for random walks on Galton-Watson trees. (Talk based on joint works with Eyal Lubetzky and with Berestycki-Lubetzky-Sly).
Back

Gil Kalai - Polymath

"A polymath (Greek: πολυμαθής, polymathēs, "having learned much") is a person whose expertise spans a significant number of different subject areas; such a person is known to draw on complex bodies of knowledge to solve specific problems" (Wikipedea).
The idea of the polymath was expressed by Leon Battista Alberti (1404–1472), in the statement, most suitable to Noga Alon, "a man who can do all things if he will". Very recently the term polymath is also used for studying mathematical problems collectively and openly over the Internet.

My lecture will be devoted to reflections on joint and related endeavors with Noga, and on the polymath10 project targeting the Erdos-Rado sunflower conjecture.
Back

Peter Sarnak - Diameters of Arithmetic Ramanujan Graphs and strong approximation

In terms word length and navigation,what are the most efficient generators of $PGL(2,F_p)$ and $PU(2)$? We review and discuss some recent developments concerning "golden" generators coming from arithmetic .They are close to optimal and yield a continued fraction like algorithm for $PU(2)$ and corresponding universal quantum gates .

Back

Tamar Ziegler - Concatenating cubic structures

Cubic structures play an important role in understanding the obstructions to finding algebraic configurations in subsets of integers. A major obstacle in finding polynomial progressions is that the cubic structures that appear are at short scales. We describe how one can concatenate short scale cubic structures to (higher order) long scale cubic structure. We give several applications including a local to global principle for the existence of some families of polynomial configurations in primes.
Back

Vojtěch Rödl - Extremal problems for uniformly dense hypergraphs

Extremal problems for hypergraphs concern the maximum density of large hypergraphs $H$ that do not contain a copy of a given hypergraph $F$. Estimating the so-called Turán-densities is a central problem in combinatorics. However, despite a lot of effort precise estimates are only known for very few hypergraphs $F$. We consider a variation of the problem, where the large hypergraphs $H$ satisfy additional hereditary density conditions. We present recent progress based on joint work with Reiher and Schacht for $3$-uniform hypergraphs. In particular, we established a computer-free proof of a recent result of Glebov, Král, and Volec on the Turán-density of the $3$-uniform hypergraph with three edges on four vertices for hypergraphs that are hereditarily dense on large vertex sets.
Back

Béla Bollobás - Counting connected hypergraphs by the probabilistic method

This This talk is about some recent work I have done with Oliver Riordan of Oxford. In 1990, Bender, Canfield and McKay proved an asymptotic formula for the number $C_2(n,m)$ of connected graphs on $n$ labelled vertices with $m$ edges covering the entire range $n - 1 \leq m \leq \binom{n}{2} $. The corresponding problem for $r$-graphs (with $r\ge 3$ fixed) is considerably harder. After substantial results of Karoński and Łuczak, Andriamampianina and Ravelomanana, and Behrisch, Coja-Oghlan and Kang, recently Riordan and I completed the proof of an asymptotic formula for $C_r(n,m)$ for the entire range of $m$. Our main result is essentially equivalent to a local limit theorem for the number of vertices and edges of the largest component of an appropriate random hypergraph. In the talk I shall sketch the history of this problem, state the main results, and illustrate the method by a simple proof of an old result.
Back

Terence Tao - The Erdos discrepancy problem

The discrepancy of a sequence $f(1), f(2), ...$ of numbers is defined to be the largest value of $|f(d) + f(2d) + ... + f(nd)|$ as $n,d$ range over the natural numbers. In the 1930s, Erdos posed the question of whether any sequence consisting only of $+1$ and $-1$ could have bounded discrepancy. In 2010, the collaborative Polymath5 project showed (among other things) that the problem could be effectively reduced to a problem involving completely multiplicative sequences. Recently, using recent breakthroughs in the asymptotics of completely multiplicative sequences by Matomaki and Radziwill, as well as a surprising application of the Shannon entropy inequalities, the Erdos discrepancy problem was solved completely. In this talk I will discuss this solution and its connection to the Chowla and Elliott conjectures in number theory.
Back

Endre Szemerédi - The Shifting Method

The shifting method is a counting technique. To understand it we are going to illustrate the method with three examples.
    1. Arithmetic progressions of length $3$.
    2. Ramsey-­‐type problem in additive combinatorics.
    3. Giving a tight bound for the size of a set $S \subset [N]$ having the property that for every
         $ x,y \in S, x+y \neq z^2$ No prior knowledge is assumed.
 Back

Alexander Schrijver - The partially disjoint paths problem

The partially disjoint paths problem asks for paths $P_1,...,P_k$ between given pairs of terminals, while certain pairs of paths $P_i,P_j$ are required to be disjoint. With the help of combinatorial group theory, we show that, for fixed $k$, this problem can be solved in polynomial time for planar directed graphs. We also discuss related problems.
Back

Joel Spencer - The Strange Logic of Galton-Watson Trees

The classic equation for a Galton-Watson tree being infinite has two solutions, only one of which is "correct." What about other properties? (Example: Some node has precisely two children.) We show that when the property is first order than there is a unique solution to the corresponding equation, and that that solution is the fixed point of a contracting transformation. We further consider "tree automata" and the situation for monadic second order properties.
Back

Jaroslav Nešetřil - All the Ramsey Classes

Ramsey classes are top of the line of Ramsey properties. Recently there is a renewed interest in this area of structural Ramsey theory, motivated by model theory and topological dynamics connection. As a result many new examples were found.
We survey and disscuss this recent development.
Back

Nati Linial - High-dimensional permutations

The subject of this lecture is part of our ongoing work on high-dimensional combinatorics. We equate between a permutation and its permutations matrix. Namely, an $n \times n$ array of zeros and ones where every line (row or column) contains exactly one $1$. So, we define a two-dimensional permutation as an $n \times n \times n$ array of zeros and ones where every line (row, column or shaft) contains exactly one $1$. It is easily seen that this is synonymous with an order $n$ Latin square. It should be clear now how we define a $d$-dimensional permutation. This perspective leads to many beautiful questions, some of which we can answer while many other remain open. The subject of this lecture is part of our ongoing work on high-dimensional combinatorics. We equate between a permutation and its permutations matrix. Namely, an $n \times n$ array of zeros and ones where every line (row or column) contains exactly one 1. So, we define a two-dimensional permutation as an $n \times n \times n$ array of zeros and ones where every line (row, column or shaft) contains exactly one $1$. It is easily seen that this is synonymous with an order $n$ Latin square. It should be clear now how we define a $d$-dimensional permutation. This perspective leads to many beautiful questions, some of which we can answer while many other remain open.

1. How many $d$-dimensional permutations of order $n$ are there? We proved an upper bound which is conjectured to be tight. (joint with Zur Luria).
2. One defines $d$-stochastic arrays in analogy with bi-stochastic matrices. Clearly the set of such arrays forms a polytope and $d$-dimensional permutations are vertices in this polytope. But in contrast with the Birkhoff von-Neumann theorem, in dimension $2$ these vertices are a negligible minority of all vertices (joint with Luria).
3. As in the Erdos-Szekeres theorem, every $d$-dimensional permutation contains $\Omega(\sqrt{n})$ 1-entries whose coordinates are monotone in all dimensions. The bound is tight up to a multiplicative constant. But unlike the classical case, for almost every $d$-dimensional permutation, the longest monotone subsequence has length $\Theta(n^{d/(d+1)})$. (joint with Michael Simkin).
4. The Furedi-Hajnal conjecture (proved by Marcus-Tardos who resolved the Stanley-Wilf conjecture) states that for every permutation $\pi \in S_k$ there is a constant $c$ such that every $n \times n$ $0/1$ matrix with at least $cn$ ones contains a copy of $\pi$. In higher dimension the corresponding bound is super-linear. (with Ruth Malka).
5. What is the lowest discrepancy of a $d$-dimensional permutation w.r.t. combinatorial boxes? We have some answers and many open questions. Interestingly, the Latin square corresponding to the multiplication table of a finite group has substantially worse discrepancy than most Latin squares. (with Luria).

Back

Assaf Naor - Lipschitz extension from finite subsets

Suppose that $X$ is a metric space and $x_1,...,x_n$ are n points in $X$. Every $1$-Lipschitz function from ${x_1,...,x_n}$ to a normed space $Z$ can be extended to a $Z$-valued function that is defined on all of $X$ and has Lipschitz constant that is bounded from above by a quantity that depends only on $n$. It is a longstanding open question to determine the best possible asymptotic dependence on n here. In this talk we will explain the long line of works on this question starting from the early 1980s, involving a variety of probabilistic and geometric techniques. We shall then proceed to explain recent progress that involves combinatorial argument that rely on (modifications of) expander graphs and discrete Sobolev-type inequalities.
Back

Avi Wigderson - Disguised lower bound problems

In the hope of tempting the audience, I will present a collection of mathematical problems, the solution of each will likely lead to some computational hardness result.
Back

Jennifer Chayes - Graphons and Machine Learning: Estimation of Sparse Massive Networks

There are numerous examples of sparse massive networks, in particular the Internet, WWW and online social networks. How do we model and learn these networks? In contrast to conventional learning problems, where we have many independent samples, it is often the case for these networks that we can get only one independent sample. How do we use a single snapshot today to learn a model for the network, and therefore be able to predict a similar, but larger network in the future? In the case of relatively small or moderately sized networks, it’s appropriate to model the network parametrically, and attempt to learn these parameters. For massive networks, a non-parametric representation is more appropriate. Here I first review the theory of graphons, developed over the last decade, to describe limits of dense graphs and certain sparse graphs of unbounded degree, such as power-law graphs. I then show how to use these graphons to give consistent estimators of non-parametric models of sparse networks, and moreover how to do this in a way that protects the privacy of individuals on the network.
Back

János Pach - The Good, The Bad, and the Ugly: Transversals

I will illustrate by a biased random sample from the Oeuvre of Noga Alon his influence on geometric and combinatorial transversal theory. Some recent results related to epsilon-nets, Vapnik-Chervonenkis dimension, and semi-algebraic combinatorics will also be discussed.
Back

Jacob Fox - Combinatorics of Permutations

fundamental question in enumerative combinatorics asks: how many permutations on n letters avoid a given permutation? The Stanley-Wilf conjecture states that the answer grows exponentially in n. Alon and Friedgut proved a result which gets extremely close to settling this well-known conjecture. Marcus and Tardos proved this conjecture a decade ago with a remarkably simple argument. It was widely believed that the exponential constant, known as the Stanley-Wilf limit, grows quadratically in the size of the given permutation. We disprove this conjecture, showing that it grows exponentially in a power of the permutation size for almost all permutations. The proof utilizes tools from extremal and probabilistic combinatorics.
Back

Zoltán Füredi - Turan type problems and algebraic constructions

Let  ${\cal F}$  be a (finite) class of $k$-uniform hypergraphs, and let $ex(n,{\cal F})$ denote its Turan number, i.e., the maximum size of the ${\cal F}$-free, $n$-vertex, $k$-uniform hypergraphs. In this lecture some Turan-type problems are considered, when the forbidden class is obtained from coding problems. In this range when Razborov’s method usually could not be used. We emphasise constructions applying algebraic tools with some additional twists. Among others, a recent result is discussed (a joint work with P. Frankl), an explicit construction of a $k$-uniform hypergraph $F$ such that $ex(n,F)= o(n^{k-1})$ but it exceeds $n^{k-1-h}$ for every $h>0$ for $n>n(k,h)$, where  $k \geq 5$ is odd. Finding hyper graphs with non-polynomial Turan numbers for even $k$ remains open.
Back

Vitali Milman - Algebraic Related Structures and the Reason behind Some Classical Constructions in Convex Geometry (and Analysis)

The main goal of the talk is to show how some classical constructions in Geometry and Analysis appear (and in a unique way) from elementary and very simple properties. For example, the polarity relation and support functions are very important and well known constructions in Convex Geometry, but what elementary properties uniquely imply these constructions, and what would be their functional versions, say, in the class of log-concave functions? It turns out that they are uniquely defined also for this class, as well as for many other classes of functions. Another example: How can one identify the "square root of a convex body"? It turns out that this is possible (however, "the square of a convex body" does not exist in general). In this talk we will mostly deal with Geometric results of this nature. Additionally, we will characterize the Fourier transform (on the Schwartz class in $R^n$) as, essentially, the only map which transforms the product to the convolution, and discuss a very surprizing rigidity of the Chain Rule Operator equation (which characterizes the derivation operation). These will be our examples pointing to an exciting continuation of this direction in Analysis.
Back

Micha Sharir - Eliminating cycles, cutting lenses, and bounding incidences

The talk covers two unrelated topics in combinatorial geometry that has recently reached a confluence: incidences between points and curves in the plane, and elimination of cycles in the depth relation of lines in $3$-space. Recent progress on the latter problem, inspired by the new algebraic machinery of Guth and Katz, has yielded a nearly tight bound, of roughly $n^{3/2}$, on the number of cuts needed to eliminate all cycles for a set of $n$ lines in $3$-space. This in turn leads to a similar bound on the number of cuts that are needed to turn a collection of $n$ constant-degree algebraic arcs in the plane into a collection of pseudo-segments (i.e., each pair of the new subarcs intersect at most once). This leads, among several other applications, to improved incidence bounds between points and algebraic arcs in the plane, which are better than the bound of Pach and Sharir, for any number of "degrees of freedom" of the curves. Joint work with Boris Aronov and Joshua Zahl.
Back

Uriel Feige - On the effect of randomness on planted 3-coloring models

The random planted 3-coloring model generates a 3-colorable graph $G$ by first generating a random host graph $H$ of average degree $d$, and then planting in it a random 3-coloring (by giving each vertex a random color and dropping the monochromatic edges). For a sufficiently large constant $c$, Alon and Kahale [SICOMP 1997] presented a spectral algorithm that finds (with high probability) the planted 3-coloring of such graphs whenever $d > c\log n$. Perhaps more surprisingly, they also extend this algorithm to handle the case $d > c$, where in this regime it finds a legal 3-coloring (not necessarily the planted one).

It is natural to ask whether the algorithm of Alon and Kahale works whenever the host graph $H$ is a $d$-regular spectral expander (chosen by an adversary). Likewise, one may ask whether the planted 3-coloring needs to be random, or may we allow an adversary to plant a balanced 3-coloring of his choice after seeing $H$. In this talk we shall review the algorithm of Alon and Kahale, while addressing questions of the above nature.
Back

Moshe Tennenholtz - Sequential Commitment Games

We study an implementation problem of Pareto efficiency as a subgame perfect equilibrium outcome in extensive form games, faced by a mediator who is ignorant about the payoff structure of the game. We introduce a novel class of sequential commitment games, where players make voluntary unconditional commitments in a prescribed order. Our main result is surprisingly positive: We show that a particular type of order can implement a Pareto efficient outcome in every such two-player game structure regardless of the actual payoffs. We also show an impossibility result for the case of four players or more. Joint work with Itai Arieli and Yakov Babichenko.
Back

Saharon Shelah - Random graph: stronger logic but with the zero one law

We like to find a logic stronger than first order such that: on the one hand it satisfies the 0-1 law, e.g. for the random graph $G_{n,1/2}$, and on the other hand there is a formula $\varphi(x)$ such that for no first order $\psi(x)$ do we have: for every random enough $G_{n,1/2}$ are the formulas $\varphi(x),\psi(x)$ are equivalent in it.
Back

---