# European Institute for Statistics, Probability, Stochastic Operations Research and their Applications

About | Research | Events | People | Reports | Alumni | ContactHome

January 6-10, 2014

Workshop on

Probability and Graphs

 SUMMARY REGISTRATION SPEAKERS PROGRAMME ABSTRACTS

SUMMARY

This workshop will be the kickoff for the Stochastic Activity Month on  Combinatorics and Probability.
We aim to bring together researchers working on the interplay between probability theory and graphs, with a focus on Graph Limits, the  Probabilistic Method for Graphs, and Random Graphs. We are very happy to  announce that Joel Spencer, one of the founding fathers of the area, will be participating.

## ORGANISERS

 Nikhil Bansal TU Eindhoven Jan Draisma TU Eindhoven Remco van der Hofstad TU Eindhoven/Eurandom Ross Kang Utrecht University / Radboud University Nijmegen Julia Komjathy TU Eindhoven Tobias Müller Utrecht University

## LIST OF INVITED PARTICIPANTS

 Louigi Addario-Berry McGill University, Canada Andrew Beveridge Macalaster College, USA Tom Bohman Carnegie Mellon University, USA Christian Borgs Microsoft/Uni of Washington, USA Graham Brightwell London School of Economics, UK Nicolas Broutin INRIA, France Peter Cameron St. Andrews/Queen Mary University of London, UK Guillaume Chapuy Université Paris Diderot-Paris 7, France Steffen Dereich Westfälische Wilhelms-Universität, Germany Josep Diaz Universitat Politecnica de Catalunya, Spain Benjamin Doerr Ecole Polytechnique, France Andrzej Dudek Western Michigan University, USA Martin Dyer University of Leeds, UK Asaf Ferber ETH Zurich, Switzerland Stefanie Gerke Royal Holloway University of London, UK Christina Goldschmidt University of Oxford, UK Simon Griffiths University of Oxford, UK Danny Hefetz University of Birmingham, UK Cecilia Holmgren Stockholm University, Sweden Mihyun Kang TU Graz, Austria Linyuan Lu University of South Carolina, USA Malwina Luczak Queen Mary University of London, UK Gábor Lugosi Pompeu Fabra University, Spain Colin McDiarmid University of Oxford, UK Viresh Patel Queen Mary University of London, UK Oleg Pikhurko University of Warwick, UK Pawel Pralat Ryerson University , Canada Bruce Reed McGill University, Canada Daniel Reichman Weizmann Institute of Science, Israel Miki Simonovits Alfréd Rényi Institue of Mathematics, Hungary Jozef Skokan London School of Economics, UK Greg Sorkin London School of Economics, UK Joel Spencer New York University, USA Miloš Stojaković University of Novi Sad, Serbia Anusch Taraz TU Hamburg, Germant Danny Vilenchik The Weizmann Institute, Israel Lutz Warnke University of Cambridge, UK

MONDAY JANUARY 6

 09.00 - 09.10 Opening Remco van der Hofstad 09.10 - 10.00 Joel Spencer Finding Needles in Exponential Haystacks 10.00 - 10.30 Break 10.30 - 11.00 Guillaume Chapuy On the diameter of random planar graphs 11.00 - 11.30 Asaf Ferber Universality of random graphs and rainbow embedding 11.30 - 12.00 Danny Hefetz Random directed graphs are robustly Hamiltonian 12.00 - 13.30 Lunch 13.30 - 14.20 Peter Cameron Acyclic orientations 14.20 - 14.50 Break 14.50 - 15.20 Graham Brightwell Extinction Times in the Stochastic Logistic Epidemic 15.20 - 15.50 Cecilia Holmgren 15.50 - 16.20 Benjamin Doerr Tight Analysis of Randomized Rumor Spreading in Complete Graphs

TUESDAY JANUARY 7

 09.10 - 10.00 Martin Dyer The chromatic number of a random hypergraph 10.00 - 10.30 Break 10.30 - 11.30 Miklos Simonovits Embedding trees into graphs 11.30 - 12.00 Greg Sorkin The Satisfiability Threshold for k-XORSAT 12.00 - 13.30 Lunch 13.30 - 14.20 Mihyun Kang Phase transitions in random graphs 14.20 - 14.50 Break 14.50 - 15.20 Viresh Patel A domination algorithm for $\{0,1\}$-instances of the travelling salesman problem 15.20 - 16.20 talks by PhD students (20 min each) Tamas Hubai: Matchings in Benjamini-Schramm convergent graph sequences Laura Florescu: The range of rotor walk and recurrence of directed lattices Marcin Witkowsky: Hamilton cycles in random lifts of graphs 18.30 - Conference Dinner

WEDNESDAY JANUARY 8

 09.10 - 10.00 Tom Bohman Dynamic Concentration in random greedy processes 10.00 - 10.30 Break 10.30 - 11.00 Simon Griffiths 11.00 - 11.30 Pawel Pralat A few random open problems, some of them for random graphs 11.30 - 12.00 Daniel Reichman The layers model with applications 12.00 - 13.30 Lunch 13.30 - 14.20 Gábor Lugosi Connectivity properties of random geometric irrigation graphs 14.20 - 14.50 Break 14.50 - 15.20 Andrew Beveridge 15.20 - 15.50 Andrzej Dudek On Hamiltonicity of Random Hypergraphs 15.50 - 16.20 Jozef Skokan Improved counting relative to pseudorandom graphs

THURSDAY JANUARY 9

 09.10 - 10.00 Anusch Taraz On the tree-packing conjecture of Gyarfas and Lehel 10.00 - 10.30 Break 10.30 - 11.00 Stefanie Gerke Maximum matchings in random bipartite graphs with degree constraints 11.00 - 11.30 Danny Vilenchik 11.30 - 12.00 Linyuan Lu High Order Phase Transition in Random Hypergraphs 12.00 - 13.30 Lunch 13.30 - 14.20 Bruce Reed / Yuditsky The structure of a typical H-free Graph 14.20 - 14.50 Break 14.50 - 16.30 5 talks by PhD students (20 min each) Anne Hildebrand: Edge-Coloured Degree Sequences of Forests and Unicyclic Graphs Guillem Perarnau: Large H-free subgraphs Liana Yepremyen: Lagrangian of r-intersecting families Joonkyung Lee: Two Approached to Sidorenko’s Conjecture Robert Fitzner: Nearest-neighbour percolation shows mean-field behaviour in d>14.

FRIDAY JANUARY 10

 09.10 - 10.00 Christian Borgs Convergence of sparse graphs as a problem at the intersection of graph theory, statistical physics and probability 10.00 - 10.30 Break 10.30 - 11.00 Josep Diaz 11.00 - 11.30 Steffen Dereich Condensation in Preferential Attachment Models with Fitness 11.30 - 12.00 Lutz Warnke Phase transitions in random graphs with dependencies 12.00 - 13.30 Lunch 13.30 - 14.20 Colin McDiarmid Random graphs from a minor-closed class 14.20 - 14.50 Break 14.50 - 15.20 Malwina Luczak SIR epidemics on random graphs with a given degree sequence 15.20 - 15.50 Miloš Stojaković Threshold for Maker-Breaker H-game 15.50 - 16.20 Oleg Pikhurko Measurable edge-colourings of graphings

*****************************************************************************************************************************************

ABSTRACTS

Andrew Beveridge

Maker-Breaker Games on Random Geometric Graphs

In a Maker-Breaker game on a graph $G$, Breaker and Maker alternately claim edges of $G$. Maker wins if, after all edges have been claimed, the graph induced by his edges has some desired property. We consider three Maker-Breaker games played on the Random Geometric Graph. For each game, we show that if we add edges between $n$ points chosen uniformly at random in the unit square by order of increasing edge-length then, with probability tending to one as $n \rightarrow \infty$, the graph becomes Maker's win the very moment it satis
fies a simple necessary condition. In particular, with high probability, Maker wins the connectivity game as soon as the minimum degree of is at least 2; Maker wins the Hamilton cycle game as soon as the minimum degree is at least 4; and Maker wins the perfect matching game as soon as the minimum degree is at least 2 and every edge has at least 3 neighboring vertices.

Christian Borgs

Convergence of sparse graphs as a problem at the intersection of graph theory, statistical physics and probability

Many real-world graphs  are large and growing.  This naturally raises the question of a suitable concept of graph convergence.  For graphs with average degree proportional to the number of vertices (dense graphs), this question is by now quite well-studied.  But real world graphs tend to be sparse, in the sense that the average or even the maximal degree is bounded by some reasonably small constant.  In this talk, I study several notions of convergence for graphs of bounded degree and show that, in contrast to dense graphs, where various a priori different notions of convergence are equivalent, the corresponding notions are not equivalent for sparse graphs.  I then describe a notion of convergence formulated in terms of a large deviation principle which implies all previous notions of convergence

Graham Brightwell

Extinction Times in the Stochastic Logistic Epidemic

The stochastic logistic process is a well-known birth-and-death process, often used to model the spread of an epidemic within a population of size $N$. We survey some of the known results about the time to extinction for this model. Our focus is on new results for the "subcritical'' regime, where the recovery rate exceeds the infection rate by more than $N^{-1/2}$, and the epidemic dies out rapidly with high probability. Previously, only a first-order estimate for the mean extinction time of the epidemic was known, even in the case where the recovery rate and infection rate are fixed constants: we derive precise asymptotics for the distribution of the extinction time throughout the subcritical regime. In proving our results, we illustrate a technique for approximating certain types of Markov chain by differential equations over long time periods.
(joint work with Malwina Luczak)

Peter Cameron

Acyclic orientations

The number of acyclic orientations of a graph is the evaluation of the chromatic polynomial at $-1$. This is hard to calculate exactly and it is not known whether it can be approximated efficiently. However, there is a Markov chain available for exploring the acyclic orientations of a given graph. One possible use is for colouring heuristics. Given an acyclic orientation, assign the first available colour to all sources, delete the sources, and repeat. It would be interesting to know more about the distribution of the number of colours required, or to direct the Markov chain towards colourings with few colours. Another open question concerns the distribution of the number of acyclic orientations of graphs with a given number of vertices and edges. The average and minimum numbers are known, and there are some conjectures about the maximum number. For complete bipartite graphs the conjecture involves poly-Bernoulli numbers.

Guillaume Chapuy

On the diameter of random planar graphs

We show that the diameter of a random planar graph of size n chosen uniformly is equal to n^{1/4+o(1)} with high probability. This result builds on the fact that random planar maps (=embedded planar graphs) are very well understood and that both models coincide at the 3-connected level via Whitney's embedding theorem. Rather than focusing on (heavy) technical details I will try to explain how this works, focusing on the description of {1,2,3}-connected components and their sizes. I'll say a word on higher genus surfaces if I have time.
(joint work with Eric Fusy, Omer Gimenez, and Marc Noy)

PRESENTATION

Steffen Dereich

Condensation in Preferential Attachment Models with Fitness

Preferential attachment models with fitness show an intriguing phase transition as observed by Bianconi and Barabasi in 2001 and rigorously verified by Borgs et al. in 2007.  In contrast to ordinary preferential attachment models the individual vertices are assigned independent fitnesses, say $\mu$-distributed, that have a linear effect on their attractivity in the network formation.
In the condensation phase, in the limit, there is a comparably small set of vertices (the condensate) that attracts a constant fraction of new links established by new vertices. The fitness of the vertices in the condensate gradually converges to the essential supremum of $\mu$, which is in our case finite. In the talk we discuss the dynamics of this process.

Josep Diaz

Recent results on infections and mutations

This talks quickly survey some recent results and open problems for the SIS model for infinite graphs and for the Lieberman,Huet and Nowak model of evolutionary dynamics on graphs.

Benjamin Doerr

Tight Analysis of Randomized Rumor Spreading in Complete Graphs

We present a very tight analysis of the basic randomized rumor spreading process introduced by Frieze and Grimmett~\cite{FriezeG85}. The process starts with a single node of a fully connected network knowing a rumor. Then, in each round of the process, each node knowing the rumor gossips the rumor to a node chosen uniformly at random. Denote by $S_n$ the number of rounds taken until all nodes know the rumor. Already Frieze and Grimmett (1985) give the fairly precise result that $S_n = (1 \pm o(1)) (\log_2 n + \ln n)$ with probability $1 - o(1)$. They also prove that for all $\eps, \gamma > 0$, with probability at least $1 - o(n^{-\gamma})$, the broadcast time does not exceed $(1 + \eps)(\log_2 n + \gamma \ln n)$. The first bound was sharpened by Pittel (1987), who proved that for any $h = \omega(1)$, we have $\Pr(|S_n - \log_2 n - \ln n| \ge h(n)) \to 0$.
We show that $S_n$ is very closely described by $\log_2 n$ plus $(1/n)$ times the completion time $C_n$ of the coupon collector process with $n$ coupon types: For any $\eps > 0$, $S_n$ is dominated by $\lceil\log_2 n\rceil + (1 + O(n^{-\frac12 +\eps})) C_n/n + 2.562 + o(1) + \Geom(1 - O(n^{-1+\eps}))$. On the other hand, an elementary argument shows that $S_n$ is subdominated by $\lfloor \log_2 n \rfloor + (1/n) C_n(n/2) - 1$, where $C_n(n/2)$ is the random variable describing the time needed to collect the last $n/2$ coupons in the coupon collector process. These bounds in particular give the first bound for the expected runtime of the process that is tight apart from additive constants: $\lfloor \log_2 n \rfloor + \ln n - 1.116 \le \E[S_n] \le \lceil\log_2 n\rceil + \ln n + 2.765 + o(1)$.
(joint work with Marvin Künnemann (MPI Informatics, Saarbrücken, Germany)

Andrzej Dudek

On Hamiltonicity of Random Hypergraphs

In this talk, we present both old and new developments concerning the Hamiltonicity of random hypergraphs. First, we consider random k-uniform hypergraphs of order n (each possible k-tuple appears independently with probability  p) and determine the thresholds for the existence of different types of Hamilton cycles (including loose and tight cycles). In particular, we show that p = e/n is the sharp threshold for the existence of tight Hamilton cycles. (joint work with A. Frieze).
Next, we discuss some very recent results about Hamiltonicity  of random regular hypergraphs  (joint  work with  A. Frieze, A. Rucin´ski, and M. Šileikis).

Martin Dyer

The chromatic number of a random hypergraph

We consider the problem of k-colouring a random r-uniform hypergraph with n vertices and cn edges, where k, r and c remain constant as n → ∞. Achlioptas and Naor showed that the chromatic number of a random graph in this setting (the case r = 2) has one of two easily computable values as n→∞. We give a complete generalisation of this result to colouring random uniform hypergraphs.

Asaf Ferber

Universality of random graphs and rainbow embedding

In this talk we discuss how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of $\gnp$. First, we improves a result of Johannsen, Krivelevich and Samotij, by providing a better (smaller) $p$ than their $n^{-1/3}$ for which w.h.p a graph $G\sim \gnp$ contains copies of all the spanning trees with maximum degree bounded by $\Delta=O(1)$ (in our case $p=\omega(n^{-1/2}\polylog)$). Next, using similar methods we show that for $p=\omegan^{-1/2d}\log^2n)$, a graph $G\sim \gnp$ w.h.p contains copies
of all spanning graphs $H$ with maximum degree bounded by $\Delta$ and with density $d$, where $d$ is the maximal average degree of all the subgraphs of $H$. In case that the density is smaller than half of the maximum degree, this improves a result of Dellamonica,
Kohayakawa, R\"odl and Ruci\'ncki. Finally, in the same spirit, we show that for any spanning graph $H$ with maximum degree $\Delta=O(1)$, and for suitable $p$, if we randomly color a graph $G\sim \gnp$ with $O(n)$ colors, then w.h.p there exists a rainbow copy of $H$ in $G$ (that is, a copy of $H$ with all edges colored with distinct colors).

Joint work with: Rajko Nenadov and Ueli Peter, two excellent PhD students in my group.

Stefanie Gerke

Maximum matchings in random bipartite graphs with degree constraints

We consider maximum matchings in random bipartite graphs with a fixed degree distribution. We analyse Karp-Sipser's algorithm and compare our approach to that of Bordenave, Lelarge and Salez who used analytic methods to obtain more general results. This is joint work with Paul Balister.
(joint work with with Paul Balister)

Danny Hefetz

Random directed graphs are robustly Hamiltonian

We study random directed graphs and prove that, if they are not too sparse, then asymptotically almost surely such graphs satisfy the following property: even if an adversary deletes almost half of the arcs at every vertex, the resulting digraph still admits a directed Hamilton cycle. This result extends the classical theorem of Ghouila-Houri as well as results on the Hamiltonicity of random directed graphs due to McDiarmid and Frieze.
(joint work with Angelika Steger and Benny Sudakov)

PRESENTATION

Cecilia Holmgren

Stein Couplings for the Study of Fringe Trees

The binary search tree (in computational science known as Quicksort, the most used of all sorting algorithms) and the random recursive tree are important examples of random trees. We have examined fringe trees ("small" subtrees) in these two types of random trees. The use of certain couplings based on Stein's method allow provision of simple proofs showing that in both of these trees, the number of fringe trees of size k, where k tends to infinity, converges to a Poisson distribution. Furthermore, combining these results and another version of Stein's method, we can also show that for k=o(sqrt{n}) (where n is the size of the whole tree) the number of fringe trees in both types of random trees converges to a normal distribution. We can then use these general results on fringe trees to obtain simple solutions to a broad range of problems relating to random trees; as an example, we can simply prove that the number of protected nodes in the binary search tree has a normal distribution.
(Joint work with Svante Janson, Uppsala University)

Mihyun Kang

Phase transitions in random graphs

The phase transition in random graphs refers to a phenomenon that there is a drastic change of the size and structure of the largest component, caused by altering a critical edge density. In the Erd\H{o}s and R\'enyi graph process, which begins with an empty graph on $n$ vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches $n/2$ and a giant component emerges. In this talk we will discuss key results and techniques to study the size of giant components in various random graphs.

Linyuan Lu

High Order Phase Transition in Random Hypergraphs

The phase transition of random hypergraphs was considered by Schmidt-Pruzan and Shamir in 1985. Karo\'nski and {\L}uczak in 2002 took a closer look at the connected components  near the threshold.
In this talk, we study the phase transition of the high order connected components. For a positive integer $n$ and a real $p\in [0,1]$, let $H:=H^r(n,P)$ be the random $r$-uniform hypergraph on the vertex set $[n]$, where each $r$-set is an edge with probability $p$ independently. For $1\leq s \leq r-1$ and two $s$-sets $S$ and $S'$, we say $S$ can be reached from $S'$ if there is a sequence of alternating $s$-sets and edges $S_0,F_1,S_1,F_1, \ldots, F_k, S_k$ which satisfies $S_0,S_1,\ldots, S_k$ are $s$-sets, $S_0=S$, $S_k=S'$, $F_1,F_2,\ldots, F_k$ are edges of $H$, and $S_{i-1}\cup S_i\subset F_i$ for each $1\leq i\leq k$. This is an equivalence relation over the family of all $s$-sets ${[n]\choose s}$ and results a partition: ${V\choose s}=\cup_i C_i$. Each $C_i$ is called an { $s$-th-order} connected component and a component $C_i$ is a giant $s$-th order connected component if $|C_i|=\Theta(n^s)$. We determined the threshold of the existence of the $s$-th-order giant connected components in $H^r(n,p)$ for all $s\geq 2$.
(joint work with
Xing Peng)

PRESENTATION

Malwina Luczak

SIR epidemics on random graphs with a given degree sequence

We study the susceptible-infective-recovered (SIR) epidemic on a random graph chosen uniformly subject to having given vertex degrees. In this model infective vertices infect each of their susceptible neighbours, and recover, at a constant rate.
Suppose that initially there are only a few infective vertices. We prove that there is a threshold for a parameter involving the rates and vertex degrees below which only a small number of infections occur. Above the threshold a large outbreak may occur. We prove that, conditional on a large outbreak, the evolutions of certain quantities of interest, such as the fraction of infective vertices, converge to deterministic functions of time. In contrast to earlier results for this model, our results only require basic regularity conditions and a uniformly bounded second moment of the degree of a random vertex.
(joint work with Svante Janson and Peter Windridge)

Gábor Lugosi

Connectivity properties of random geometric irrigation graphs

Consider a graph whose vertices represent n uniform random points in the unit square.
One may form a random geometric graph by connecting two point by an edge if the distance of the points is at most r. Let c be a positive integer. We form an irrigation subgraph of the random geometric graph by selecting, at random, c vertices among the neighbors of any given vertex, and keeping only the edges joining the vertex to the selected neighbors.
We present various results about connectivity properties of such graphs. Joint work with Nicolas Broutin and Luc Devroye.

Colin McDiarmid

Random graphs from a minor-closed class

Consider a class of graphs which is closed under forming minors, such as the class of forests or the class of planar graphs.  We are interested in the random graph R_n sampled uniformly from the graphs in the class on vertex set 1,..,n.  We shall focus on two recent developments.
(a)  Call a class of graphs bridge-addable if, whenever G is in the class and u and v are in different components, then G+uv is also in the class. For such a class, the random graph R_n should be at least as likely to be connected as for a random forest?
(b)  Consider the class of graphs with at most k vertex disjoint cycles.  Typically R_n consists of a forest together with k vertices (which form a blocker, hitting each cycle in the graph). There is a similar result if we replace cycles by other 2-connected excluded minors, as long as we do not allow all fans'.  But what about disjoint K_4 minors?  (This includes work of Valentas Kurauskas.)

Viresh Patel

A domination algorithm for $\{0,1\}$-instances of the travelling salesman problem

In this talk, I shall discuss an approximation algorithm for $\{0,1}$-instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, given a $\{0,1\}$-edge-weighting of the complete graph $K_n$ on $n$ vertices, our algorithm outputs a Hamilton cycle $H$ of $K_n$ with the following property: the proportion of Hamilton cycles of $K_n$ whose weight is smaller than that of $H$ is at most $n^{-1/29}$. Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial-time algorithm with domination ratio $1/2 - o(1)$ for arbitrary edge-weights. On the hardness side we can show that, if the Exponential Time Hypothesis holds, there exists a constant $C$ such that $n^{-1/29}$ cannot be replaced by $\exp(-(\log n)^C)$ in the result above.
(joint work with Daniela Kühn and Deryk Osthus)

Oleg Pikhurko

Measurable edge-colourings of graphings

Consider a graph G=(X,E) on a standard Borel space X with maximum degree bounded by d whose edge set E is a Borel subset of X^2. It is known that G admits a Borel edge-colouring with 2d-1 colours (Kechris-Solecki-Todorcevic 1999) but not always with 2d-2 colours (Marks 2013). We consider measurable edge-colourings when G is a graphing (i.e. it can be represented by finitely many measure-preserving maps) and show that d+o(d) colours suffice. This is a joint work with Endre Csoka and Gabor Lippner.

Pawel Pralat

A few random open problems, some of them for random graphs

I am going to present a few open problems I am recently thinking about. These problems are related to: 1) total acquisition in random graphs, 2) the acquaintance time of random graphs, 3) lazy cops and robbers, 4) cops and robbers on Boolean lattice.

PRESENTATION

Bruce Reed

The structure of a typical H-free Graph

We consider the structure of a typical graph not containing an induced subgraph isomorphic to H, for various H. Amongst other results we show that the vertex set of almost every $C_6$-free graph can be partitioned into a stable set and the complement of a graph of girth 5.

Daniel Reichman

The layers model with applications

Given an undirected graph $G = (V,E)$ and an integer $k$, let $Tk(G)$ denote the random vertex induced subgraph of $G$ generated by ordering $V$ according to a random permutation and including in $Tk(G)$ those vertices with at most $k-1$ of their neighbors preceding them in this order. The distribution of subgraphs sampled in this manner is called the layers model with parameter $k$. The layers model has found applications in combinatorics, property testing and local algorithms, the design of algorithms for the maximum independent set problem, and bootstrap percolation.
We will present some of these connections. We will also consider the infinite grid $Z_2$, for which we prove that $T4(Z_2)$ contains an infinite cluster with probability 1.
(joint works with Uri Feige and Jonathan Hermon)

Miklos Simonovits

Embedding trees into graphs

abstract

Josef Skokan

Improved counting relative to pseudorandom graphs

Recently, Conlon, Fox and Zhao proved a counting lemma, counting small graphs in $\varepsilon$-regular subgraphs of sparse pseudorandom graphs. This counting lemma has many important applications such as sparse pseudorandom analogues of Tur\’an’s Theorem, Ramsey’s Theorem and the graph removal lemma. One key ingredient for the proof of their counting lemma is a regularity inheritance lemma, which states that for most vertices in an$\varepsilon$-regular subgraph of a pseudorandom graph, the neighbourhoods of this vertex form an $\varepsilon’$-regular graph. We improve this regularity inheritance lemma, so that it now applies to graphs with weaker pseudorandomness conditions. This implies an improved counting lemma relative to these pseudorandom graphs.
(joint work with Peter Allen, Julia Boettcher, Maya Stein)

Greg Sorkin

The Satisfiability Threshold for k-XORSAT

We consider "unconstrained" random k-XORSAT, which is a uniformly random system of m linear non-homogeneous equations in F2 over n variables, each equation containing k \ge 3 variables, and also consider a "constrained" model where every variable appears in at least two equations. Dubois and Mandler proved that m/n=1 is a sharp threshold for satisfiability of constrained 3-XORSAT, and analyzed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT.
We show that m/n=1 remains a sharp threshold for satisfiability of constrained k-XORSAT for every k \ge 3, and we use standard results on the 2-core of a random k-uniform hypergraph to extend this result to find the threshold for unconstrained k-XORSAT. For constrained k-XORSAT we narrow the phase transition window, showing that m-n \to -\infty implies almost-sure satisfiability, while m-n \to +\infty implies almost-sure unsatisfiability.

Joel Spencer

Finding Needles in Exponential Haystacks

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 that when $ed < 2^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 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 $r_j$ in $n$-space with all coefficients in $[-1,+1]$ one wants a vector $x=(x_1,...,x_n)$ with all $x_i=+1$ or $-1$ so that all dot products $x\cdot r_j$ are at most $K\sqrt{n}$ in absolute value, $K$ an absolute constant. A random $x$ would make $x\cdot r_j$ 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=(0,...,0)$ and let it float in a kind of restricted Brownian Motion until all the coordinates hit the boundary.

Miloš Stojaković

Threshold for Maker-Breaker H-game

We will look at the Maker-Breaker $H$-game played on the edge set of the random graph $G_{n,p}$. In this game two players, Maker and Breaker, alternately claim unclaimed edges of $G_{n,p}$, until all the edges are claimed. Maker wins if he claims all the edges of a copy of a fixed graph $H$; Breaker wins otherwise.
It turns out that, with the exception of trees and triangles, the threshold for this game is given by the threshold of the corresponding Ramsey property of $G_{n,p}$ with respect to the graph $H$.
(joint work with Rajko Nenadov and Angelika Steger)

PRESENTATION

Anusch Taraz

On the tree-packing conjecture of Gyarfas and Lehel

In 1976, Gyarfas and Lehel made the somewhat stunning conjecture that any family of trees T_1,T_2,...,T_n, with 1,2,...,n vertices respectively, can be packed in an edge-disjoint manner into the complete graph on n vertices. This conjecture is still open.
In this talk I will sketch a proof for a slightly weakened version of this conjecture, where we only consider trees of bounded maximum degree and allow the complete graph to have an additional o(n) vertices.
The proof uses tree-indexed random walks controlled by the nibble method.
(joint work with J.Boettcher, J.Hladky and D.Piguet)

Danny Vilenchik

## Chasing the k-colorability threshold

In this talk I will present a substantially improved lower bound on the $k$-colorability threshold of the random graph $G(n,m)$ with $n$ vertices and $m$ edges.
The new lower bound is 1.39 less than the $2k\ln k-\ln k$ first-moment upper bound (and 0.39 less than the 2k\ln k-\ln k-1 physics conjecture).
By comparison, the best previous bounds left a gap of about 2+\ln k, unbounded in terms of the number of colors [Achlioptas, Naor: Annals of Mathematics 2005].
Furthermore, we prove that, in a precise sense, our lower bound marks the so-called condensation phase transition predicted on the basis of physics arguments.
Our proof technique is a novel approach to the second moment method, inspired by physics conjectures on the geometry of the set of $k$-colorings of the random graph.

Joint work with Amin Coja-Oghlan. Paper appeared in FOCS 2013.

PRESENTATION

## Lutz Warnke

Phase transitions in random graphs with dependencies

In the Erdös-Rényi random graph process, starting from an empty graph, in each step a new random edge is added to the evolving graph. One of its most interesting features is the percolation phase transition': as the ratio of the number of edges to vertices increases past a certain critical density, the global structure changes radically, from only small components to a single giant component plus small ones.
In this talk we consider Achlioptas processes, which have become a key example for random graph processes with dependencies between the edges.
Starting from an empty graph these proceed as follows: in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. We discuss why, for a large class of rules, the percolation phase transition is qualitatively comparable to the classical Erdös-Rényi process.
(joint work with Oliver Riordan)

PRACTICAL INFORMATION

### ●      Venue

Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,

Den Dolech 2, 5612 AZ  EINDHOVEN,  The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the (4th floor) (about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.

### ●      Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl

The organisers acknowledge the financial support/sponsorship of:

#### Last updated 09-04-14, by PK

P.O. Box 513, 5600 MB Eindhoven, The Netherlands
tel. +31 40 2478100
e-mail: info@eurandom.tue.nl