HOME    »    SCIENTIFIC RESOURCES    »    Volumes
Abstracts and Talk Materials
Probabilistic and Extremal Combinatorics
September 8 - 12, 2014

Noga Alon (Tel Aviv University)

Bipartite Decomposition of Graphs

Keywords of the presentation: Bipartite decomposition, Random graphs, Stein-Chen method

For a graph G, let bc(G) denote the minimum possible number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to (exactly) one of them. The study of this quantity and its variants received a considerable amount of attention and is related to problems in communication complexity and geometry. After a brief discussion of the background and earlier results on the subject I will focus on the problem of determining the typical value of bc(G) for the binomial random graph G=G(n,p), showing that a conjecture of Erdos about it is (slightly) false, and suggesting an alternative one.

Jozsef Balogh (University of Illinois at Urbana-Champaign)

On the Applications of Counting Independent Sets in Hypergraphs

Keywords of the presentation: extremal combinatorics, counting discrete structures

Recently, Balogh-Morris-Samotij and Saxton-Thomason developed a method of counting independent sets in hypergraphs. During the talk, I show a recent application of the method; solving the following Erdos problem: What is the number of maximal triangle-free graphs?

If there is some extra time in the talk, I will survey some other recent applications.

These applications are partly joint with Das, Delcourt, Liu, Mycroft, Petrickova, Sharifzadeh and Treglown.

Charles David Burnette (Drexel University)

Representing Random Permutations as a Product of Two Involutions

Endow S_n with the uniform probability measure. Given a permutation s of [n], let N(s) denote the number of ways that s can be written as a product of two involutions of [n]. We will identify several properties of the random variable N, including:

(1) An elementary derivation of the exact formula for N(s) in terms of the cycle lengths of s.

(2) The minimum, maximum, and expected values of N over S_n.

(3) The asymptotic distribution of log N, which resolves a conjecture of M. Lugo.

In particular, N is asymptotically lognormal. The proof of this draws on connections between N(s) and B(s), the product of the cycle lengths of s, along with the Erdős-Turán law, which states that B itself is asymptotically lognormal.

Maria Chudnovsky (Columbia University)

Coloring Graphs with Forbidden Induced Subgraphs

Keywords of the presentation: graph coloring, induced subgraphs, graph structure

Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Due to results of Kaminski and Lozin, and Hoyler, the problem remains NP-complete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixed-length induced path forbidden has received considerable attention. Only one case of that problem remains open for k-coloring when k>=4, and that is the case of 4-coloring graphs with no induced 6-vertex path. However, little is known for 3-coloring. Recently we settled the first open case for 3-coloring; namely we showed that 3-coloring graphs with no induced 7-vertex paths can be done in polynomial time. We also made progress on the 4-coloring question. In this talk we will discuss some of the ideas of the algorithms, and related problems.

This is joint work with Peter Maceli, Juraj Stacho and Mingxian Zhong.

David Conlon (University of Oxford)

Ramsey Multiplicity

Keywords of the presentation: Ramsey theory

Ramsey's theorem states that for any graph H there exists an n such that any 2-colouring of the complete graph on n vertices contains a monochromatic copy of H. Moreover, for large n, one can guarantee that there are at least c_H n^v copies of H, where v is the number of vertices in H. In this talk, we investigate the problem of optimising the constant c_H, focusing in particular on the case of complete graphs.

Jacob Fox (Massachusetts Institute of Technology)

Extremal Combinatorics, Geometry, and Algebra

Keywords of the presentation: Extremal combinatorics, geometric graph theory, semi-algebraic relations

Famous Ramsey, Turan, and Szemeredi-type results prove the existence of certain patterns in graphs and hypergraphs under mild assumptions. We survey recent results which show much stronger/larger patterns for graphs and hypergraphs that arise from geometry or algebra.

Zoltan Furedi (Hungarian Academy of Sciences (MTA))

Turan Numbers of Expanded Forests

Keywords of the presentation: Extremal hypergraphs, forests, Erdos-Sos conjecture, Erdos-Ko-Rado theorem

The Turan number ex(n,H) of an r-graph H is the largest size of an n-vertex r-graph that does not contain H. The famous Erdos-Sos conjectrure concerns the Turan number of a tree T of k vertices. The difficulty lies in the fact that there could be very different extremal families, disjoint cliques of sizes k-1 or in some cases a graph with (k-2)/2 vertices of degree n-1.

A hypergraph H is a hypergraph forest if its edges can be ordered as {E_1,..., E_m} such that for all i>1 there exits an alpha(i) < i such that the intersection of E_i with earlier members contained entirely in E_{alpha(i)}. Many extremal set theoretic results, such as the Erdos-Ko-Rado theorem, can be described in terms of Turan numbers of very specific r-forests, or partial r-forests. In this work we are looking for the possible widest class of hypergraph forests where the extremal family is kind of concentrated, it consists of a few high degree vertices. For all rgeq 4, we show that if H is a partial r-forest such that each edge has at least two degre 1 vertices then

ex(n,H)=(s(H)-1) {n choose r-1} + O(n^{r-2})

where s(H) is the minimum size of a 1-cross-cut of H. Using structural stability we also obtain exact results implying many recent asymptotic bounds. Most of the new results presented are joint with Tao Jiang (Miami University, Ohio).

Jie Han (Georgia State University)

The Deterministic Problem for Perfect Matchings in Dense k-uniform Hypergraphs

For any r>0, Keevash, Knox, and Mycroft constructed a polynomial-time algorithm to determine the existence of perfect matchings in any n-vertex k-uniform hypergraph whose minimum codegree is at least n/k+rn.

We construct a polynomial-time algorithm to determine the existence of a perfect matching for any k-uniform hypergraph with minimum codegree at least n/k. This solves a problem of Karpiński, Ruciński and Szymańska completely.

Our proof is short and uses a lattice-based absorbing method.

Keivan Hassani Monfared (University of Wyoming)

Existence of a Nowhere-Zero Eigenbasis in an SIEP, or How to Find More Needles in Nearby Haystacks

In his 1989 paper (Linear Algebra and Its Applications, 113:173--182), Duarte solves an structured inverse eigenvalue problem, and Hassani Monfared in his PhD dissertation (2014) solves similar problems using the Jacobian method. In particular, it was shown that for any set of n distinct real numbers, and a given graph G, there is a real symmetric matrix A whose graph is G and its eigenvalues are the given numbers. It is also shown that if the graph G is connected, then the matrix A with above properties can be chosen such that all the eigenvectors of A are nowhere-zero (that is, none of eigenvectors has a zero entry). There is a belief that the later result could be proved using probabilistic methods.

Jeff N. Kahn (Rutgers, The State University of New Jersey)

On Erdos-Ko-Rado for Random Hypergraphs

Keywords of the presentation: Erdos-Ko-Rado, random hypergraph

One of the more interesting of recent combinatorial directions has been the attempt to understand the extent to which various classical facts remain true in a random setting. The present talk will mostly discuss what we know about this question when the ``classical fact" is the Erdos-Ko-Rado Theorem. (Joint with Arran Hamm.)

Mihyun Kang (Technische Universität Graz)

Phase Transitions in Random Hypergraphs

Keywords of the presentation: giant component, hypergraphs, Galton-Watson branching process

The study of phase transitions in random graphs was initiated by Erdos and Renyi in 1960. They proved among other things that a uniform random graph undergoes a drastic change in the size and structure of the largest component, caused by altering a critical edge density. Since the seminal work of Erdos and Renyi, various random graph models have been introduced and studied over the last five decades. In this talk I will discuss some recent results in phase transitions in random hypergraphs. (Joint work with Oliver Cooley and Christoph Koch.)

Alexandr Kostochka (University of Illinois at Urbana-Champaign)

Cycles in Triangle-free Graphs with Large Chromatic Number

Keywords of the presentation: Triangle-free, chromatic number, cycle lengths

Erdos conjectured that a triangle-free graph with chromatic number k contains cycles of almost quadratically many different lengths, as k tends to infinity. We prove a somewhat stronger inequality for the number of consecutive lengths of cycles in k-chromatic graphs. The bound has the best possible order of magnitude because of Kim's construction of ``small'' triangle-free graphs with chromatic number k. We also give new lower bounds on the circumference and the number of different cycle lengths for k-chromatic graphs in other monotone classes, in particular, for graphs with bounded clique number and for graphs without odd cycles of a given length. This is joint work with Benny Sudakov and Jacques Verstraete.

Michael Krivelevich (Tel Aviv University)

The Phase Transition in Site Percolation on Pseudo-Random Graphs

Keywords of the presentation: site percolation, pseudo-random graphs, giant component

We establish the existence of the phase transition in site percolation on pseudo-random d-regular graphs. Let G=(V,E) be an (n,d,lambda)-graph, that is, a d-regular graph on n vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most lambda in their absolute values. Form a random subset R of V by putting every vertex v in V into R independently with probability p. Then for any small enough constant epsilon>0, if p=(1-epsilon)/d, then with high probability all connected components of the subgraph of G induced by R are of size at most logarithmic in n, while for p=(1+epsilon)/d, if the eigenvalue ratio lambda/d is small enough as a function of epsilon, then typically R contains a connected component of size at least epsilon n/d and a path of length proportional to epsilon^2n/d.

Tomasz Luczak (Adam Mickiewicz University)

What Does it Mean to Be Free?

Unfortunately, because of the format of the talk, most probably we will not be able to address the fascinating question stated in the title in its full depth and generality. Thus, instead, we concentrate on the specific problem of finding the threshold function for the `freeness' for Zuk's model of triangular random group which was recently settled in the affirmative by Sylwia Antoniuk, Tomasz Prytuła, Piotr Przytycki, Bartosz Zaleski and the speaker.

János Pach (École Polytechnique Fédérale de Lausanne (EPFL))

My Happy Ending Problem

Keywords of the presentation: multiple covering, decomposition, hypergraph coloring

A set system is a k-fold covering of space if every point is contained in at least k sets. A 1-fold covering is called simply a covering. In 1980, motivated by a question of Laszlo Fejes Toth, I raised the following question. Given a plane convex set C, does there exist an integer k=k(C) such that every k-fold covering of the plane splits into 2 coverings? The same question makes sense in higher dimension. This problem has turned out to be relevant in sensor network scheduling and has generated a lot of research during the past 3 and a half decades.

In this talk, I will summarize the curious history of the problem, and give a survey of the most important results and related open problems.

Guillem Perarnau (McGill University)

Acyclic Edge Colourings of Graphs with Large Girth

An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours. We show that for every eps>0, there exists a g=g(eps) such that if G has maximum degree D and girth at least g then it admits an acyclic edge colouring with at most (1+eps)D colours. This is a joint work with X. S. Cai, B. Reed and A. B. Watts.

Alexey Pokrovskiy (Technische Universität Berlin)

Connectedness and Linkedness in Tournaments

A (possibly directed) graph is k-linked if for any two disjoint sets of vertices {x1,...,xk} and {y1,...,yk} there are vertex disjoint paths P1,...,Pk such that Pi goes from xi to yi. A theorem of Bollobás and Thomason says that every 22k-connected (undirected) graph is k-linked. It is desirable to obtain analogues for directed graphs as well. Although Thomassen showed that the Bollobás-Thomason Theorem does not hold for general directed graphs, he proved an analogue of the theorem for tournaments - there is a function f(k) such that every strongly f(k)-connected tournament is k-linked. The bound on f(k) was reduced to O(k log k) by Kühn, Lapinskas, Osthus, and Patel, who also conjectured that a linear bound should hold. We'll present the ideas behind a proof of this conjecture, that every strongly 452k-connected tournament is k-linked.

Alexander Razborov (University of Chicago)

Flag Algebras: An Interim Report

Keywords of the presentation: Extremal problems, Turan densities, flag algebras

Flag Algebras is a general method for proving results in asymptotic extremal combinatorics that can be loosely described as ``systematic counting based on semi-definite programming''. The concrete results proven via this method can be (again, loosely) classified into two groups of unequal size. Brute-force applications use counting only; the role of a human being reduced to finding a tractable problem and doing a bit of programming. In other applications of the method, more advanced concepts and tools from the general theory are used to help in finding a ``flag algebra-assisted'' proof.

This talk will mostly be a survey of concrete results in extremal combinatorics obtained with the help of flag algebras provided in either of these two modes. But instead of giving a plain and unannotated list of results, we will try to divide our account into several connected stories that often include historical background, motivations and results obtained via other methods.

Bruce Reed (McGill University)

The Cost of Knowing Your Roots

Keywords of the presentation: Minors, Rooted Minors

We discuss the edge-density required to force H as a minor, especially when H is sparse. We also discuss analogous results for rooted minors. This includes joint work with Gwenael Joret, Dieter Rautenbach, Alex Scott, David Wood, and Hehui Wu.

John Roger Schmitt (Middlebury College)

Warning’s Second Theorem with Restricted Variables

We present a restricted variable generalization of Warning's Second Theorem (a result giving a lower bound on the number of solutions of a low degree polynomial system over a finite field, assuming one solution exists). This is analogous to Schauz’s (and later Brink’s) restricted variable generalization of Chevalley's Theorem (a result giving conditions for a low degree polynomial system emph{not} to have exactly one solution). Just as Warning's Second Theorem implies Chevalley's Theorem, our result implies Schauz's Theorem. We include several combinatorial applications, enough to show that we have a general tool for obtaining quantitative refinements of combinatorial existence theorems.

This is joint work with Pete L. Clark (U. Georgia) and Aden Forrow (M.I.T.).

Joel Spencer (New York University)

Finding Needles in Exponential Haystacks

Keywords of the presentation: Erdos Magic, Lovasz Local Lemma, Brownian Motion

We discuss two recent methods in which an object with a certain property is sought. In both, using of a straightforward random object would succeed with only exponentially small probability. The new randomized algorithms run efficiently and also give new proofs of the existence of the desired object. In both cases there is a potentially broad use of the methodology.

(i) Consider an instance of k-SAT in which each clause overlaps (has a variable in common, regardless of the negation symbol) with at most d others. Lovasz showed for certain d,k (regardless of the number of variables) the conjunction of the clauses was satisfiable. The new approach due to Moser is to start with a random true-false assignment. In a WHILE loop, if any clause is not satisfied we "fix it" by a random reassignment. The analysis (due, basically, to Don Knuth) of the algorithm is unusual, connecting the running of the algorithm with certain Tetris patterns, and leading to some algebraic combinatorics. [These results apply in a quite general setting with underlying independent "coin flips" and bad events (the clause not being satisfied) that depend on only a few of the coin flips.]

(ii) No Outliers. Given n vectors n-space with all coefficients between -1 and +1 one wants a vector x with all coordinates -1 or +1 so that its dot products with all the n vectors are at most K times the square root of n in absolute value, K an absolute constant. A random x would make the dot product Gaussian but there would be outliers. The existence of such an x was first shown by the speaker. The first algorithm was found by Nikhil Bansal. The approach here, due to Lovett and Meka, is to begin with x the all zero vector and let it float in a kind of restricted Brownian Motion until all the coordinates hit the boundary.

Angelika Steger (ETH Zürich)

Connectivity Thresholds for Bounded Size Rules

Keywords of the presentation: Random Graph Processes, Achlioptas Process, Connectivity Threshold

In an Achlioptas processes, starting with a graph that has n vertices and no edge, in each round d edges are drawn uniformly at random, and using some rule exactly one of them is chosen and added to the evolving graph. For the class of Achlioptas processes we investigate how much impact the rule has on one of the most basic properties of a graph: connectivity. Our main results are twofold. First, we study the prominent class of bounded size rules, which select the edge to add according to the component sizes of its vertices, treating all sizes larger than some constant equally. For such rules we provide a ne analysis that exposes the limiting distribution of the number of rounds until the graph gets connected, and we give a detailed picture of the dynamics of the formation of the single component from smaller components. Second, our results allow us to study the connectivity transition of all Achlioptas processes, in the sense that we identify a process that accelerates it as much as possible.

Joint work with Hafsteinn Einarsson, Johannes Lengler, Frank Mousset, and Konstantinos Panagiotou

Tibor Szabó (Freie Universität Berlin)

On the Minimum Degree of Minimal Ramsey-Graphs

Keywords of the presentation: Ramsey graph, extremal problems, Ramsey equivalence

A graph G is a minimal Ramsey-graph for H if every two-colouring of the edges of G contains a monochromatic copy of H, but no proper subgraph of G has this property. Burr, Erdos and Lovasz investigated the extremal values of various graph parameters among minimal Ramsey-graphs for the clique. In particular they determined the smallest minimum degree of minimal Ramsey-graphs for the k-clique. Recently there has been much activity in extending their investigations in various directions, in the talk I survey some of these. This represents joint work with Jacob Fox, Andrey Grinshpun, Anita Liebenau, and Yury Person.

Andrew Thomason (University of Cambridge)

List Colourings of Simple Hypergraphs

Keywords of the presentation: list colourings, hypergraphs

Unlike the ordinary chromatic number, the list chromatic number necessarily grows with the average degree. Indeed, Alon (2000) proved it grows with the logarithm of the average degree. Recently, the same has been shown to be true for uniform hypergraphs, by means of the "container method": we sketch how this works. The question then arises as to the precise value of the minimum list chromatic number. Here the answer turns out to be not what was expected. We attempt to sketch the latest progress, and its implications for containers. (Joint work with David Saxton and Ares Meroueh.)

Matthew Thorpe (University of Warwick)

Variational Methods In Statistical Inference: An Application to Clustering

The k-means method is an iterative clustering algorithm which associates each observation with one of k clusters. It traditionally employs cluster centers in the same space as the observed data. By relaxing this requirement, it is possible to apply the k-means method to infinite dimensional problems, for example smoothing problems in the presence of unknown data association. Via a Gamma-convergence argument, the associated optimization problem is shown to converge in the sense that both the k-means minimum and minimizers converge in the large data limit to quantities which depend upon the observed data only through its distribution.

Ngoc Mai Tran (The University of Texas at Austin)

Zeroes of Random Tropical Polynomials,Random Polytopes and Stick-breaking

Stochastic tropical geometry is the study of linear functionals of random tropical varieties. It is an exciting new field at the interface of algebraic geometry, probability and combinatorics, with connections to many others. In this work, we study the simplest possible case: the number of zeroes of a randomtropical polynomial.

Specifically, if a tropical polynomial has coefficients independent and identically distributed according to some distribution $F$, then its number of zeroes satisfies a central limit theorem. The scaling is governed by how fast $F$ decays near $. This can be seen as a local universality result for zeros ofrandom tropical polynomials.

Our proof draws on connections between random partitions, renewal theory and random polytopes. In this talk, I sketch the main proof ideas and discuss open questions in the field of stochastic tropical geometry.

Joint work with Francois Baccelli

Jacques Verstraete (University of California, San Diego)

Full Subgraphs

Let G be a graph of density p on n vertices. Erdös, Luczak and Spencer defined a subgraph H of G to be full if H has m vertices and every vertex of H has degree at least p(m - 1) in H. Let f(G) denote the largest number of vertices in a full subgraph of G and let fp(n) denote the smallest value of f(G) over all graphs G of density p with n vertices. Erdös, Luczak and Spencer proved √2n ≤ f0:5(n) ≤ 2n2/3 (log n)1/3 and also showed f(G) = (n) when G is the random graph Gn,p.

In this talk, I will show that fp(n) ≥ min {p1/2n + 1; 0:1n2/3} for all p ∈ (0; 1), and for p close to the elements of {1/2, 2/3, 3/4; ::::} we show that fp(n) = O(n2/3), which determines the order of magnitude of fp(n) for infinitely many p. We also discuss the value of f(G) when G is a random or pseudorandom graph, as well as full subgraphs of regular graphs.

The methods include spectral techniques and discrepancy, together with some com- binatorial algorithms to find full subgraphs. Our study was in part originally motivated by questions on bootstrap percolation in graphs. In conclusion, a number of interesting open questions will be presented.

Joint work with Victor Falgas-Ravry and Klas Markstrom during the program on graphs, hypergraphs and computing at Institut Mittag-Leffler in winter 2014.

Van H. Vu (Yale University)

Concentration and Anti-Concentration

Keywords of the presentation: concentration, anti-concentration, small ball probability, inverse theorems, random graphs

In probabilistic combinatorics, one often needs to have some rough estimate for the distribution of a complicated random variable. There are two main kinds of estimates:

(1) Concentration: If one take an interval I far from the mean, then the probability that X in I is very small.

(2) Anti-concentration: If one take a "short" interval I, then the probability that X in I is also very small.

I am going to discuss a few recent results in these areas, together with applications. Most of the talk will be based on my papers "Small Ball Probability" with H. Nguyen, and "Random Weighted projections" with K. Wang, available on the arxiv.

Nick Wormald (Monash University)

Enumeration of Graphs With A Heavy-Tailed Degree Sequence

Keywords of the presentation: asymptotic enumeration, degree sequence, power law

The number of graphs with a given degree sequence is still not known in any convenient form, even asymptotically, for moderately dense graphs. We obtain a formula that includes some heavy-tailed sequences in the sparse case (i.e. where the average degree is rather small). Our general result requires upper bounds on the k-th moment of the degree sequence, for a few small integers k. Special cases include the first asymptotic enumeration results applicable to degree sequences following a power law with parameter between 2 and 3, which is the realm of empirically observed real-world networks. Another special case extends a recent result of Janson. A previous result on sparse graphs applies to a wide range of degree sequences but requires maximum degree M to the power 1/3, where M is the number of edges. Our new result applies in some cases when the maximum degree is almost the 3/5 power of M. The basic method is, as usual, that of estimating a very small probability, of the event that the random configuration model gives a simple graph.

This is joint work with Jane Gao.

Damir Yeliussizov (Kazakh-British Technical University)

Path Decompositions of Digraphs and Their Applications to Weyl Algebra

We consider decompositions of digraphs into edge-disjoint paths. Together with several enumerative and structural results, one of the main interests lies in increasing walks. As we will see there is a connection of decompositions with the n-th Weyl algebra (or differential operators). Like Eulerian tours applicable for the Amitsur-Levitski theorem, this approach helps to study skew-symmetric polynomials on certain subspaces of Weyl algebra. We also discuss some new types of restricted set partitions and generalized Stirling numbers. For instance, G-Stirling functions which enumerate decompositions by sources and sinks of paths.

Connect With Us: