Workshop on Probabilistic and Extremal Combinatorics

The workshop on Probabilistic and Extremal Combinatorics will take place February 5-9, 2018 at the Center of Mathematical Sciences and Applications, located at 20 Garden Street, Cambridge, MA.

Extremal and Probabilistic Combinatorics are two of the most central branches of modern combinatorial theory. Extremal Combinatorics deals with problems of determining or estimating the maximum or minimum possible cardinality of a collection of finite objects satisfying certain requirements. Such problems are often related to other areas including Computer Science, Information Theory, Number Theory and Geometry. This branch of Combinatorics has developed spectacularly over the last few decades. Probabilistic Combinatorics can be described informally as a (very successful) hybrid between Combinatorics and Probability, whose main object of study is probability distributions on discrete structures.

There are many points of interaction between these fields. There are deep similarities in methodology. Both subjects are mostly asymptotic in nature. Quite a few important results from Extremal Combinatorics have been proven applying probabilistic methods, and vice versa. Such emerging subjects as Extremal Problems in Random Graphs or the theory of graph limits stand explicitly at the intersection of the two fields and indicate their natural symbiosis.

The symposia will focus on the interactions between the above areas. These topics include Extremal Problems for Graphs and Set Systems, Ramsey Theory, Combinatorial Number Theory, Combinatorial Geometry, Random Graphs, Probabilistic Methods and Graph Limits.

Participation: The workshop is open to participation by all interested researchers, subject to capacity. Click here to register.

A list of lodging options convenient to the Center can also be found on our recommended lodgings page.

Confirmed participants include:

Co-organizers of this workshop include Benny Sudakov and David Conlon.  More details about this event, including participants, will be updated soon.

Click here for a list of registrants.


Monday Feb. 5

………Time…….. …..Speaker….. Title/Abstract
9:00 – 10:00am  Breakfast
10:00 – 10:45am Yuval Peres Two problems: Bipartite matching in the plane and Trace reconstruction for the deletion channel

Abstract:  In the first part of the talk, I will briefly discuss bipartite matching for random points in the plane:

The optimal  matching was analyzed by Ajtai, Komlos, Tusnady (1984); with N. Holden and A. Zhai we showed that  gravitational matching is almost optimal; and the performance of the greedy algorithm is not understood. In the second (unrelated) part, I will discuss the trace reconstruction problem: an unknown string $x$ of $n$ bits is observed through  the deletion channel, which deletes each bit with some constant probability q, yielding a contracted string.  How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability? The best lower bound known is linear in $n$.  Until 2016, the best upper bound was exponential in the square root of $n$. With  F. Nazarov, we improved the square root to a cube root using statistics of individual output bits and some inequalities for Littlewood polynomials on the unit circle.  This bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently by De, O’Donnell and Servedio).

10:45 – 11:15am Coffee Break
11:15 – 12:00pm Asaf Ferber Some problems in random discrete matrices 

Abstract: In this talk we discuss some interesting problems related to the singularity problem of random discrete matrices. In particular, we discuss the following:

1. What is the largest $m$ for which the span of $m$ randomly chosen vectors in $\{1,-1\}^n$ whp intersects the hypercube in a trivial way (here we slightly extend an old result of Odlyzko).

2. It is known that if we take $m\leq n$ vectors from $\{1,-1\}^n$ uniformly at random, then typically they form an independent set. How many signs does an adversary need to flip for a typical collection of such vectors to form dependencies?  Here we show that as long as $m\leq n-n^{1-\eps}$, the answer is $(1-o(1))n/2$, which is asymptotically optimal. 

Joint work with Kyle Luh, Gweneth McKinley and Wojtek Samotij.

12:00 – 1:30pm Lunch
1:30 – 2:15pm Angelika Steger Resilience of Perfect Matchings and Hamiltonicity in Random Graph Processes

Abstract: A graph $G$ is said to be $\alpha$-resilient with respect to some property~${\cal P}$, if for every spanning subgraph $H \subseteq G$ with $\deg_H(v) \le \alpha \deg_G(v)$ for all $v\in V(G)$, the graph $G – H$ still satisfies property~${\cal P}$. Determining the largest possible parameter $\alpha$ for a given property in the case $G = K_n$, the complete graph with $n$ vertices, is one of the central topics in extremal combinatorics, pioneered by Dirac in the 1950s and yielding celebrated results such as the Hajnal-Szemer\’edi theorem. In this talk we complete settle the resilience question for randoms graphs with respect to containing a p a Hamilton cycle.  In particular, we show that for $m \ge (\tfrac16 + o(1))n \log n$ the $2$-core of the random graph $G_{n,m}$ is $(\tfrac12-o(1))$-resilient with respect to being Hamiltonian. Moreover, we show that in the random graph process in which edges are added randomly one at a time, the graph becomes resiliently Hamiltonian as soon as the minimum degree reaches~$2$, a necessary condition for being Hamiltonian. This establishes a resilience version of the classical `hitting-time’ result of Ajtai, Koml\’os, and Szemer\’edi and, independently, Bollob\’as. Similar results are obtained for perfect matchings.

Joint work with Rajko Nenadov and Miloš Trujić.

2:15 – 2:30pm Break
2:30 – 3:15pm Eyal Lubetzky Dynamical random graphs with dependencies: from Erdos-Renyi to Curie-Weiss 

Abstract: We will survey the connection between classical random graph theory and dynamics on models where the edge/vertex variables are dependent, such as the FK/Potts models. We will focus on a recent result which, via random graph analysis, established the exponential mixing time behavior in the 3-color Curie-Weiss model, closing the gap that remained following the seminal work of Gore-Jerrum (1997) and the follow-up works by Galanis et al (2015) and Blanca and Sinclair (2015). (No prior knowledge on statistical physics models will be assumed.)

Joint work with R. Gheissari and Y. Peres.

3:15 – 3:45pm Break
3:45 – 4:30pm Shoham Letzer Path partitions of regular graphs

Abstract: The well-known theorem of Dirac (1952) states that a graph on n vertices with minimum degree at least n/2 contains a Hamilton cycle. As a possible generalisation of Dirac’s result, Magnant and Martin (2009) conjectured that every k-regular graph on n vertices can be partitioned into at most n/(k+1) paths, a bound which is attained by a disjoint union of k+1 cliques. Note that the regularity assumption is needed in order to allow for a partition into a small number of paths, as otherwise a sufficiently unbalanced bipartite graph is a counter example. We prove this conjecture in the case where k is linear in n and n is large.

This talk is based on joint work with Vytautas Gruslys.

4:30 – 6:00pm Welcome Reception

Tuesday Feb. 6

……..Time……… ….Speaker…… Title/Abstract
9:00 – 10:00am Breakfast
10:00 – 10:45am Jeff Kahn More on Shamir

Abstract:  Shamir’s Problem (circa 1980) asks:  for fixed r at least 3 and n a (large) multiple of r, how large should M be so that M random r-subsets of {1 … n} are likely to contain a perfect matching (that is, n/r disjoint r-sets)?About ten years ago Johansson, Vu and the speaker proved the natural conjecture that this is true if M > C n ln n,  for some large C=C(r).  Here we give the asymptotically correct statement:  the same behavior holds for any fixed C> 1/r.

10:45 – 11:15am Coffee Break
11:15 – 12:00pm Rob Morris An asymmetric container lemma

Abstract: A fairly straightforward application of the method of hypergraph containers allows one to determine the threshold at which the structure of a typical $H$-free graph transitions from being “random-like” to being “structured”. For most hereditary graph properties, however, the standard version of this method does not allow one to establish even the existence of such a threshold. In this talk I will discuss a refinement of the container method that takes into account the asymmetry between edges and non-edges in a sparse member of a hereditary graph property. In particular, this allows one to show that the family of induced-$C_4$-free graphs with $n$ vertices and $m$ edges undergoes a phase transition around $m = n^{4/3} (\log n)^{O(1)}$.

Joint work with Wojciech Samotij and David Saxton.

12:00 – 1:30pm Lunch
1:30 – 2:15pm David Zuckerman Explicit Two-Source Extractors, Ramsey Graphs, and Resilient Functions

Abstract: We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n. As a corollary, we explicitly construct a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.
A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1/2 – \delta}.
We also discuss subsequent improvements by other authors.

Joint work with Eshan Chattopadhyay.

2:15 – 2:30 Break
2:30 – 3:15 Bhargav Narayanan Hamiltonian surfaces in 3-graphs

Abstract: I will talk about a recently proved Dirac-type theorem for surfaces: for any connected, closed 2-manifold S, any 3-uniform hypergraph on n vertices in which each pair of vertices belongs to n/3 + o(n) or more edges contains a Hamiltonian copy of S, and this is tight. 

Joint work with Georgakopoulos, Haslegrave and Montgomery.

3:15 – 3:45 Break  
3:45 – 4:30 Problem Session

Wednesday Feb. 7

……….Time……… …..Speaker….. Title/Abstract
9:00 – 10:00am Breakfast
10:00 – 10:45am Michael Krivelevich Embedding large minors in weak expanders and in sparse random graphs

Abstract: A graph G on n vertices is called an alpha-expander if the external neighborhood of every vertex subset U of size |U|<=n/2 in G has size at least alpha|U|. 

Extending and improving the results of Plotkin, Rao and Smith, and of Kleinberg and Rubinfeld from the 90s, we prove that for every alpha>0, an alpha-expander G on n vertices contains every graph H with at most cn/log n vertices and edges as a minor, for c=c(alpha)>0. Alternatively, every n-vertex graph G without sublinear separators contains all graphs with cn/log n vertices and edges as minors. Consequently, a supercritical random graph G(n,(1+epsilon)/n) is typically minor-universal for the class of graphs with cn/log n vertices and edges. The order of magnitude n/log n in the above results is optimal.

A joint work with Rajko Nenadov.

10:45 – 11:15am Coffee Break
11:15 – 12:00pm Alexey Pokryvoskyi Latin squares and rainbow subgraphs

AbstractA subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares. Since then, rainbow structures were focus of extensive research and found applications in design theory and graph decompositions. In this talk we discuss how probabilistic reasoning can be used to attack several old problems in this area.

In particular we show that well known conjectures of Andersen, Ringel, and Graham-Sloane hold asymptotically.

This is joint work with Richard Montgomery and Benny Sudakov.

12:00 – 1:30pm Lunch
1:30 – 2:15pm Peter Keevash More designs

Abstract: We generalise the existence of combinatorial designs to the setting of subset sums in lattices with coordinates indexed by labelled faces of simplicial complexes. This general framework includes the problem of decomposing hypergraphs with extra edge data, such as colours and orders, and so incorporates a wide range of variations on the basic design problem, notably Baranyai-type generalisations, such as resolvable hypergraph designs, large sets of hypergraph designs and decompositions of designs by designs.

2:15 – 2:30pm Break
2:30 – 3:15pm Jacques Verstraete Clique and biclique covering problems

Abstract: For a graph G, let cc(G) (respectively, bc(G)) denote the minimum number of cliques (respectively, bicliques) needed to cover the edges of G. In this talk, I discuss some old and new  results on covering the complement of sparse graphs as well as some extensions to hypergraphs, and conclude with a number of open problems.

3:15 – 3:45pm Break
3:45 – 4:30pm Mathias Schacht Homomorphism thresholds for graphs

Abstract: The interplay of minimum degree and ‘structural properties’ of large graphs with a given forbidden subgraph is a central topic in extremal graph theory. For a given graph $F$ we define the homomorphism threshold as the infimum $\alpha$ such that every $n$-vertex $F$-free graph $G$ with minimum degree at least $\alpha n$ has a homomorphic image $H$ of bounded size (independent of $n$), which is $F$-free as well. Without the restriction of $H$ being $F$-free we recover the definition of thechromatic threshold, which was determined for every graph $F$ by Allen et al. The homomorphism threshold is less understood and we present recent joint work with O. Ebsen on the homomorphism threshold for odd cycles.

Thursday Feb. 8

……….Time……… …..Speaker….. Title/Abstract
9:00 – 10:00am Breakfast
10:00 – 10:45am David Gamarnik Maximum Cut problem on sparse random hypergraphs . Structural results using the interpolation method and the algorithmic implications.

Abstract:  We consider a particular version of the Maximum Cut problem (to be defined in the talk)  on a  sparse random K-uniform hypergraph, when K is even. The goal is to compute the maximum cut value w.h.p., and ideally to find an algorithm which finds a near maximum cut value in polynomial time. Using the interpolation technique we obtain the value of the maximum cut asymptotically as the edge density increases. Specifically, the interpolation method allows us to connect the maximum cut value with the ground state of the associated Sherrington-Kirkpatrick (SK) spin glass model. Furthermore, in the case when K is at least 4, we show that the configurations nearing the ground state in the SK model exhibits the Overlap Gap Property (OGP): every two such configurations are either nearly identical or nearly orthogonal to each other. Using the interpolation method the same is shown to hold for the original Maximum Cut problem. The presence of the OGP implies that no local algorithm defined as a factor of i.i.d., which will be defined in the talk, can succeed in constructing a nearly optimal cut. The existence of a polynomial time algorithm for constructing a nearly optimum cut on a random K-uniform hypergraph remains an open problem.

Joint work with Wei-Kuo Chen,  Dmitry Panchenko and  Mustazee Rahman.

10:45 – 11:15am Coffee Break
11:15 – 12:00pm Asaf Shapira A generalized Turan problem and its applications

Abstract: For fixed integers \ell and k, how many copies of the k-cycle guarantee the appearance of an \ell-cycle? Extending previous results of Bollobas-Gyori-Li and Alon-Shikhelman, we fully resolve this problem by giving tight (or nearly tight) bounds for all values of \ell and k. We also present a somewhat surprising application of the above mentioned estimates to the study of the graph removal lemmas. Prior to this work, all bounds for removal lemmas were either polynomial or there was a tower-type gap between the best known upper and lower bounds. We fill this gap by showing that for every super-polynomial function f(\eps), there is a family of graphs F, such that the bounds for the F removal lemma are precisely given by f(\eps). We thus obtain the first examples of removal lemmas with tight super-polynomial bounds. A special case of this result resolves a problem of Alon and the second author, while another special case partially resolves a problem of Goldreich.

Joint work with L. Gishboliner

12:00 – 1:30pm Lunch
1:30 – 2:15pm Shachar Lovett Linear decision trees for 3-SUM and related problems

Abstract: The 3-SUM problem asks, given n real numbers x_1,…,x_n, whether there exist 3 of them that sum to zero. There is a trivial algorithm that solves it in O(n^2) time, and the best algorithm to date only improves upon it in logarithmic terms. A significantly better algorithm is believed to be impossible (or at least would be very surprising), as it is a bottleneck for many problems in computational geometry and graph theory.

We show that in the linear decision tree model, 3-SUM has a near-linear O(n polylog(n)) algorithm. A linear decision tree is an adaptive algorithm which makes linear queries of the form “sum a_i x_i>0 ?” to the input x, and at the end decides whether a 3-SUM exists. Moreover, the type of queries we use are only *label queries* of the form “x_i+x_j+x_k>0 ?” or *comparison queries* of the form “x_i+x_j+x_k>x_a+x_b+x_c ?”. Thus, the queries are all 6-sparse linear queries with {-1,0,1} coefficients. The same techniques can be applied to many other geometric problems with a combinatorial flavour. For example, given two sets A,B of n real numbers, there exists a linear decision tree which sorts A+B and makes O(n polylog (n)) queries.

The proof relies on a newly introduced combinatorial parameter called the “inference dimension”. It generalizes the classical notion of VC dimension, by allowing for a-symmetry between what a learning algorithm “wants to learn” about the data versus what it can “ask about the data”.

Joint work with Daniel Kane and Shay Moran.

2:15 – 2:30pm Break
2:30 – 3:15pm Lisa Sauerman A proof of a conjecture of Erdős et al. about subgraphs of minimum degree k

Abstract: Erdős, Faudree, Rousseau and Schelp observed the following fact for every fixed integer k\geq 2: Every graph on n\geq k-1 vertices with at least (k-1)(n-k+2)+(k-2)(k-3)/2 edges contains a subgraph with minimum degree at least k. However, there are examples in which the whole graph is the only such subgraph. Erdős et al. conjectured that having just one more edge implies the existence of a subgraph on at most (1-\epsilon_k)n vertices with minimum degree at least k, where \epsilon_k>0 depends only on k.

In this talk, we will sketch a proof of this conjecture. The proof relies on ideas from a paper of Mousset, Noever and Škorić. We will discuss these ideas and how they can be extended to give a proof of the full conjecture.

3:15 – 3:45pm Break
3:45 – 4:30pm Daniela Kuhn A bandwidth theorem for approximate decompositions

Abstract: We provide a degree condition on a regular n-vertex graph G which ensures the existence of a near optimal packing of any family H of bounded degree n-vertex k-chromatic separable graphs into G. In general, this degree condition is best possible.

Here a graph is separable if it has a sublinear separator whose removal results in a set of components of sublinear size. Equivalently, the separability condition can be replaced by that of having small bandwidth. Thus our result can be viewed as a version of the bandwidth theorem of Boettcher, Taraz and Schacht in the setting of approximate decompositions.

In particular, this yields an approximate version of the tree packing conjecture in the setting of regular host graphs G of high degree. Similarly, our result implies approximate versions of the Oberwolfach problem, the Alspach problem and the existence of resolvable designs in the setting of regular host graphs of high degree.

This is joint work with Padraig Condon, Jaehoon Kim and Deryk Osthus.

Friday Feb. 9

……….Time……… …..Speaker….. Title/Abstract
9:00 – 10:00am Breakfast
10:00 – 10:45am Yufei Zhao Efficient arithmetic regularity and removal lemmas for induced bipartite patterns

Abstract: Let G be an abelian group of bounded exponent and A ⊂ G . We show that if the collection of translates of A has bounded VC dimension , then for every ϵ > 0 there is a subgroup H of G of index at most poly(1/ϵ) such that one can add or delete at most ϵ|G| elements to A to make it a union of H -cosets. 
We also establish a removal lemma with polynomial bounds, with applications to property testing, for induced bipartite patterns in a finite abelian group with bounded exponent. 

Joint work with Noga Alon and Jacob Fox.

10:45 – 11:15am Coffee Break
11:15 – 12:00pm Joel Spencer Preferential Attachment when Stable

Abstract:  Book proofs for preferential attachment models are found through continuous time processes with exponential waiting times.  In turning these arguments around we find large deviation results and a description of the process conditional on remaining stable.

Joint work with Svante Janson and  Subhabrata Sen
12:00 – 1:30pm Lunch

Related Posts