Program

Friday:


Saturday:



Abstracts

Speaker: Noga Alon, Tel Aviv University
Title: Optimal universal graphs and digraphs
Abstract:

What is the minimum number of vertices of a graph that contains every k-vertex graph as an induced subgraph ? Improving earlier estimates by Moon, by Bollobas and Thomason and by Alstrup, Kaplan, Thorup and Zwick, I will show that the answer is (1+o(1))2^{(k-1)/2}. Following the tradition of Joel Spencer, a crucial argument in the proof is probabilistic (but some tools from group theory are used as well). The technique, which I'll try to sketch, supplies similar tight bounds for the analogous questions for tournaments, digraphs, oriented graphs and more.

Speaker: János Pach, EPFL, Lausanne and Rényi Institute, Budapest
Title: The right brain of Joel Spencer
Abstract:

Erdos's 1946 questions about the distribution of distances among n points in the plane have generated a lot of research in combinatorics and combinatorial geometry, culminating in the "polynomial method" of Guth and Katz that almost completely settled one of the basic problems. In joint work with Beck, Szemeredi, and Trotter, Joel Spencer also made some important contributions to the subject, that have not been surpassed yet. I will give a strongly biased view of the present landscape.

Speaker: Ron Graham, UCSD
Title: Joel, Frank and Uncle Paul
Abstract:

In this talk I will describe a variety of classical results and open problems in one of Joel's favorite areas, namely, Ramsey theory.

Speaker: Svante Janson, Uppsala University
Title: Successive minimum spanning trees
Abstract:

Consider the complete graph K_n with i.i.d. U(0,1) costs (weights) on the edges. Let T_1 be the minimum spanning tree. Alan Frieze (1985) has shown that, as n tends to infinity, the cost of T_1 converges to zeta(3). Now take a second spanning tree T_2, edge-disjoint from T_1, with minimum cost among all such trees. Continue and take greedily disjoint spanning trees T_3, ... (as long as possible). We show that for each fixed k, the cost of T_k converges to some constant gamma_k as n tends to infinity. The proof is based on growing the spanning trees dynamically.

(Joint work with Gregory Sorkin.)

Speaker: Ioana Dumitriu, University of Washington
Title: Two clustering problems in random graphs
Abstract:

TBA

Speaker: Peter Winkler, Dartmouth College
Title: Permutation Limits
Abstract:

In recent work of Lovasz and others, analytic techniques were employed to study large graphs, via limit objects called graphons. In some respects this approach works even better on permutations, where the limit objects are doubly stochastic measures. We will explain how a variational principle can be used to determine what large random permutations look like, in particular permutations with given pattern densities.

This is joint work with Rick Kenyon (Brown), Dan Kral (Warwick), and Charles Radin (Texas), begun at ICERM last spring.

Speaker: Laura Florescu, NYU
Title: The range of rotor walk revisited
Abstract:

In a rotor walk, or deterministic random walk on a graph, the exits from each vertex follow a prescribed periodic sequence. Previously, it was shown that the range of this walk in t steps on the d-dimensional lattice is at least t^{d/d+1}. In ongoing work, we show the range on the hypercube is at least t/(log^2 t).

Speaker: Matan Harel, University of Geneva
Title: When More Information Reduces the Speed of Learning
Abstract:

Consider two Bayesian agents attempting to estimate a random variable based on exogenous information, as well as each other's action. Our main finding is that increased interaction between the agents can dramatically increase the probability of estimating the variable incorrectly: when both agents observe each other, learning is significantly slower than it is when the observation is one-sided. This slowdown is driven by a process in which early consensus on the wrong action causes the agents to discount new contrary evidence. This is joint work with Elchanan Mossel, Phillippe Strack, and Omer Tamuz.

Speaker: Will Perkins, University of Birmingham
Title: Occupancy Fractions, Independent Sets, and Matchings
Abstract:

I will show that over all d-regular graphs, the complete d-regular bipartite graph maximizes the "occupancy fraction" of both the hard-core model and the monomer-dimer model of a random independent set and matching respectively. With some calculus, this gives a strengthening of the theorem of Kahn and Zhao that unions of K_d,d's maximize the total number of independent sets in d-regular graphs and proves that such graphs also maximize the total number of matchings. Based on joint work with Ewan Davies, Matthew Jenssen, and Barnaby Roberts.

Speaker: Jennifer Chayes, Microsoft Research
Title: Graphons and Machine Learning: Modeling and Estimation of Sparse Massive Networks - Part I
Speaker: Christian Borgs, Microsoft Research
Title: Graphons and Machine Learning: Modeling and Estimation of Sparse Massive Networks - Part II
Abstract:

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. In this talk, we first review the theory of graphons, developed over the last decade to describe limits of dense graphs, and the more the recent theory describing sparse graphs of unbounded average degree, including power-law graphs. We then show how to use these graphons as non-parametric models for sparse networks. Finally, we show how to get consistent estimators of these non-parametric models, and moreover how to do this in a way that protects the privacy of individuals on the network.

Part I of this talk reviews the theory of graph convergence for dense and sparse graphs. Part II uses the results of Part I to model and estimate massive networks.

Speaker: Fan Chung, UCSD
Title: Discrepancies of Sequences of Numbers
Abstract:

We will discuss some old and new problems/results on various notions of discrepancies of sequences of numbers.

Speaker: Alan Frieze, Carnegie-Mellon University
Title: Minimum weight spanning trees with random costs
Abstract:

We discuss some old and new results on the following problem. Given a graph with independent uniform [0,1] random edge weights, what can we say about the length of the minimum spanning tree?

Speaker: Sasho Nikolov, University of Toronto
Title: Factorization Norms and Hereditary Discrepancy
Abstract:

Hereditary discrepancy is a robust version of combinatorial discrepancy, introduced by Lovasz, Spencer, and Vesztergombi. We expect that hereditary discrepancy is much better behaved than discrepancy: for example, Spencer conjectured that hereditary discrepancy can be efficiently approximated, while discrepancy admits no non-trivial efficient approximation algorithm, unless P=NP. In this work, we show that the classical $gamma_2$ factorization norm of an operator from $\ell_1$ to $\ell_\infty$ approximates hereditary discrepancy up to poly-logarithmic factors. Since $\gamma_2$ is polynomial-time computable, this gives a polynomial-time approximation algorithm for hereditary discrepancy. We then demonstrate on several examples the power of the $\gamma_2$ norm as a tool for proving lower and upper bounds in discrepancy theory. Most notably, we prove a new lower bound of $\Omega(\log^{d-1} n)$ for the $d$-dimensional Tusnady problem, asking for the combinatorial discrepancy of an $n$-point set in $\R^d$ with respect to axis-parallel boxes. For $d>2$, this improves the previous best lower bound, which was of order approximately $\log^{(d-1)/2}n$, and it comes close to the best known upper bound of $O(\log^{d+1/2}n)$, for which we also obtain a new, very simple proof.

Based on joint work with Jiri Matousek and Kunal Talwar.

Speaker: Roberto Oliveira, Instituto Nacional de Matemática Pura e Aplicada (IMPA)
Title: Sub-Gaussian Concentration by Design
Abstract:

An i.i.d. sample is given from a distribution P. If you want to estimate the mean of P, what should you do? Usually one takes the sample mean, but this may or may not concentrate strongly around the expectation, depending on the tail of P. In this talk we will show that you can do much better. By designing a different estimator, we can guarantee sub-Gaussian concentration around the expectation of P for huge families of distributions. In this festive occasion, we will focus on pretty proofs. A less pretty but more thorough treatment of this problem, with many positive and negative results, can be found in "Sub-Gaussian Mean Estimators" (joint with L. Devroye, M. Lerasle and G. Lugosi, to appear in Ann. Stat.).

Speaker: Endre Szemeredi, Renyi Institute and Rutgers University
Title: Embedding Spanning Trees
Abstract:

In this talk we will consider the following tree embedding question. What is the minimum degree of a graph G on n vertices that guarantees that G contains every spanning tree T with maximum degree m? We show that there exist constants c and K = K(c) such that whenever m <= cn / log n and delta(G) >= n/2 + K m log n then T is contained in G. This result is sharp if m is bounded or m = Theta(n/log n). The proof uses absorbing and the connecting method combined with probabilistic ideas. This is joint work with Bela Csaba and Asif Jamshed.

Speaker: Carl Pomerance, Dartmouth College
Title: Random number theory
Abstract:

No, it's not the theory of random numbers, though that's a part of it. Probabilistic methods have played a role in number theory for close to 90 years, if not longer. This lecture will highlight some of this history from Schoenberg to Turan, and the Erdos collaborations with Wintner and Kac. In the 1950's Erdos helped get the "probabilistic method" off the ground with his study of Sidon sequences. In the modern era, randomness has played an essential part in number-theoretic algorithms and in the way we think of the distribution of prime numbers. We will end our tour with the role of probability in the abc conjecture, the Erdos covering congruences problem, and the Catalan--Dickson conjecture.

Speaker: Moumanti Podder, Courant Institute
Title: First Order Probabilities in Galton-Watson Trees
Abstract:

For any fixed finite tree T_0, we show that T_0 is almost surely contained as a subtree in a random Galton-Watson tree, conditioned on it being infinite. This in turn implies, for any given positive integer k, that an infinite Poisson(lambda) Galton-Watson tree will almost surely contain a *universal* subtree UNIV(k) sufficiently far from the root. All first order sentences of quantifier depth k are then determined by a local neighbourhood of the root. We then discuss a recursive procedure to compute the probabilities of these local neighbourhoods of the root, conditioned on the tree being infinite. We give a nearly complete characterization of these probabilities and show that they are nicely expressible as functions of lambda.