# Random Discrete Structures and Beyond

**Dates**

###### 22nd May 2017 to 16th June 2017

**Duration**

###### 4 weeks

**Venue**

###### UPC

**Organizers:**

- Josep Díaz Cort (UPC)
- Gábor Lugosi (UPF)
- Juanjo Rué Perna (UPC)
- Oriol Serra (UPC)

**List of BGSMath Research Groups involved with the proposal:**

- Dep. of Computer Science, UPC: ALBCOM (Josep Díaz)
- Dep. of Mathematics, UPC: Combgraph (Oriol Serra)
- Dep. of Mathematics, UPC: Matemática Discreta (Juanjo Rué)
- Dep. of Economics, UPF: STARS (Gábor Lugosi)

With the support of the Spanish Ministry of Economy and Competitiveness, through the ”María de Maeztu” Programme for Units of Excellence in R&D” (MDM‐2014‐0445).

##### Registration

##### Presentation

The BGSMath Monthly Program Random Discrete Structures and Beyond aims to bring together top leader researchers in combinatorics, probability theory and computer science in the area of random discrete structures, as well as early stage researchers on this active area. The monthly program will be articulated around 4 axes: long research stays of distinguished researchers on the area of random combinatorial structures, a scientific workshop (by invitation), a weekly seminar on random discrete structures and finally a wide spectrum of specialized graduate courses delivered by some of the guest researchers. The last point is a natural sequel of the BGSMath course Random Structures and the Probabilistic Method delivered in the Fall 2013.

##### Objectives, opportunities of the program and expected synergies.

The main objective of the program is to reinforce the existing community in the area within the BGSMath through the organisation of a program in the scope of the call which will certainly have an international impact. To that purpose we have conrmed the participation of leading top researchers in a wide variety of disciplines related to random discrete structures, with a strong record of collaboration with the members of the BGSMath involved in the project. The interplay between theory and applications is one of the objectives of the program, which has also shaped the prole of the invited researchers. As a BGSMath program, most particular attention will be put on the participation of early stage researchers (graduate students and postdoctoral researchers) and to the establishment of new collaborations. The program will also contribute to the permanent training of the members of the research groups involved in the proposal to maintain and improve their scientic prole and international visibility which may attract talent, particularly in the framework of the BGSMath. The monthly program aims to produce a synergy between the researchers in random graphs and those versed in the analysis of large scale networks. More precisely, the expected synergies of this monthly program are multiple, and in dierent levels: Provide courses delivered by top leading experts on the eld will denitely contribute to the training objectives of the doctoral, postdoctoral and faculty members of the BGSMath. We believe that the wide variety of courses we propose will make the activity completely visible also for international early-stage researchers, which will be potential future members of BGSMath (specially as postdoctoral fellows). Provide the right environment to continue research collaboration with some of the guest visitors, as well as to start new research projects. We expect to start new investigations with the visiting researchers that will produce a positive development of the activity of this branch in the Barcelona area.

##### Planing

The scientific program will be articulated around three axes: **graduate courses** covering a wide spectrum of topics in the context of random discrete structures, a **research workshop **and a **weekly seminar** (except for the week of the workshop).

**Graduate Courses:**

Long-term visiting researchers will deliver a graduate course course each (around 5 hours each course). Problem sessions will complement the lectures. the courses offered are the following:

**Discrete Fourier analysis: combinatorics and percolation (Tobias Muller, Week 1)**Discrete analogues of Fourier analysis have been critical to many important results in random graph theory and percolation.

Abstract

In the course we will start with (almost) no prerequisites and after treating the basics we will cover selected results including

the Kahn-Kalai-Linial theorem, Friedgut’s junta theorem and Bourgain’s theorem, and we’ll discuss some applications of

these to random graphs and percolation theory.

**Embedding large structures in random graphs (David Conlon, Week 2)**

**Abstract**In this course, we will explore some of the techniques used to embed large sparse graphs in random graphs. Along the way, we hope to touch on the rotation-extension technique, the sparse regularity method, the blow-up lemma and much more.

**Random trees: from Darwin to Janson (Luc Devroye, Week 4)**

The ubiquity of trees in computer science, probability theory, network science, graph theory, and biology should make it obligatory to understand their theoretical underpinnings. Trees appear in many forms, so the first step is to develop a proper model.**Abstract**

Consider a binary tree with n nodes, and assume that each such tree is equally likely. This tree was studied in the 1830s by Eugène Catalan.

By “study”, they meant to just count them: the number of such trees is called the Catalan number.

It is possible to define many infinite sets of trees and define a random tree as a uniform random tree of a given size taken from this set. British mathematician Arthur Cayley (1821-1895) counted the number of labeled trees on $n$ nodes, so these trees provide another example. Meir and Moon (1970) called all these models “simply generated trees”, and were the first modern day researchers to analyze many properties of typical trees.

The early expected performance analysis of these uniform trees was based upon combinatorial tools such as generating functions, and worked out in great detail by Knuth in 1973 in his groundbreaking volumes.

In the second half of the nineteenth century, Bienaymé (1845), and separately, Galton and Watson (1874) invented a rather different model of random tree. Sir Francis Galton (1822-1911) was an English Victorian statistician, progressive, polymath, sociologist, psychologist, anthropologist, eugenicist, tropical explorer, geographer, inventor, meteorologist, proto-geneticist, and psychometrician, and Charles Darwin’s half-brother. Charles Robert Darwin (1809-1882) was an English naturalist, geologist and biologist, and is of course best known for his contributions to the science of evolution. So, Galton’s tree, created to explain population dynamics and evolution, starts with a single individual. This individual has a random number of children according to a certain distribution. Each child reproduces independently according to that same law. This random tree either becomes extinct or lives forever. The Galton-Watson trees are the simplest example of a branching process. Thousands of statisticians and probabilists have studied their properties.

It is amazing, then, that we had to wait until 1975 until someone noticed that both models are actually identical: the uniform combinatorial tree is identical in distribution to a certain random Galton-Watson tree conditional on that same size. Thus, Galton-Watson trees, conditional on their size, loom large as an important class of random trees. The purpose of these notes is to provide a general introduction to these objects. We begin with the identification of those trees that are bound to become extinct, a result already known to Bienaymé (1845). The equivalence of simply generated trees and Galton-Watson trees will be shown next. There are several ways of viewing the conditional Galton-Watson trees. The simplest one is based on random walks. This simple view has deep consequences and leads to the property that a randomly selected node in these trees is very likely the root of an unconditional critical Galton-Watson tree and the extensive surveys and new analyses by Janson). It also leads to the second view, namely the description of the limiting tree, as $n \to \infty$, sometimes called Kesten’s tree. This infinite tree has a spine, a path from the root down. Each node on the spine reproduces according to a size-biased distribution, but all other nodes are roots of independent unconditional critical (and hence, finite) Galton-Watson trees. We end our tour with a third view, which describes the limit of several traversals (or contours) of the tree, after scaling, to a Brownian excursion, a ground-breaking result due to Aldous.**Random graphs from constrained graph classes (Colin McDiarmid, Week 4)**

**Abstract**

Consider a given class of graphs, for example the class of planar graphs. What are typical properties of the random graph Rn sampled uniformly from the graphs in the class with vertex set {1, …, n}? Is there usually a giant component? How likely is it for Rn to be connected? Are there many leaves? How big is the 2-core?Such questions have attracted much interest over recent years. Here we discuss some general combinatorial and probabilistic methods to investigate them, while making limited assumptions about the class of graphs involved. We focus mostly on minor-closed classes of graphs. We shall usually assume also at least that the class is bridge-addable (that is, if G is in the class and u and v are vertices in different components, then the graph G’ obtained by adding the edge uv must be in the class).

**Workshop ‘Random Discrete Structures and Beyond’:**

The Week 3 of the program will be focussed on a 3-day research workshop. The workshop will have an open problem session. The following are the speakers of the workshop:

– Milan Bradonjic (Bell Labs)

– Amin Coja-Oghlan (Frankfurt)

– Stefanie Gerke (Royal Holloway)

– Colin Mcdiarmid (Oxford)

– Dieter Mitsche (Nice)

– Tobias Müller (Utrech)

– Guillem Perarnau (Birmingham)

– Xavier Pérez (Nebraska)

– Benny Sudakov (ETH Zurich)

– Tibor Szabó (FU Berlin)

– Lutz Warnke (GeorgiaTech-Cambridge)

– Maya Stein (U. Chile)

– Yufei Zhao (Oxford)

**Weekly seminar:**

Complementarily to the courses and the workshop, we expect that short-term visitors will deliver research seminars in the context of the joint LIMDA seminar at UPC Barcelona (usually running on Thursdays at 12:00)

##### Schedule

All lectures will be at FME (UPC- Campus Diagonal Sud, Edifici U. C. Pau Gargallo 14, 08028 Barcelona)

Map of the building:

http://fme.upc.edu/ca/la-facultat/edifici/plafo-fme-a4.pdf

** Week 1: Tobias Müller (Utrecht)**: Discrete Fourier analysis: combinatorics and percolation

All lectures will be done at FME-Room 002

Tuesday 23rd: Lecture 1, 10:00-12:00.

Wednesday 24th: Lecture 2, 10:00-12:00

Thursday 25th: Problem session 1, 10:00-12:00

Friday 26th: Lecture 3 +Problem session 2, 10:00-12:30

** Week 2: David Conlon (Oxford):** Embedding large structures in random graphs

All lectures will be done at FME-Room 103

Monday 29th : Lecture 1, 10:30-12:00

Tuesday 30th: Seminar 10:00-12:00 (see Seminars Sessions)

Wednesday 31st: Lecture 2, 10:30-12:00

Thursday 1st : Problems 1, 10:30-12:30.

Friday 2nd: Lecture 3, 10:30-12:30.

**Week 3: Seminar + BGSMath Workshop: ‘Random Discrete Structures and Beyond’**

Tuesday 6th: 10:30-12:30 Room 103 (see Seminars Sessions)

Wednesday 7th-Friday 10th: BGSMath Workshop ‘Random Discrete Structures and Beyond’. See the webpage of the workshop for the schedule

** Week 4: Luc Devroye (McGill):** Random trees: from Darwin to Janson, and

**: Random graphs from constrained graph classes**

__Colin McDiarmid (Oxford)__Monday 12th (Room S03): 10:00-13:00, 1,5 hours+1,5 hours (McDiarmid 10:00-11:30, Devroye 11:30-13:00)

Tuesday 13th (Room S03): 10:30-12:30 (McDiarmid)

Wednesday 14th (Room S05): 10:30-12:30 (Devroye)

Thursday 15th (Room S05): 10:30-12:00 Seminar 10:00-13:00 (see Seminars Sessions)

Friday 16th (Room S05): 10:00-13:00, 1,5 hours+1,5 hours (McDiarmid 10:00-11:30, Devroye 11:30-13:00)

##### Seminars Sessions

**Week 4:** Wednesday 14th

**Time:** 10:30-12:00 (Room S05)

**Speaker:** Benny Sudakov (ETH Zurich)

**Title and Abstract:** Rainbow cycles and trees in properly edge-colored complete graphs

A rainbow subgraph of a properly edge-colored complete graph is a subgraph all of whose edges have different colors. One reason to study such subgraphs arises from the canonical version of Ramsey’s theorem, proved by Erdos and Rado. Another motivation comes from problems in design theory. In this talk we discuss several old conjectures about finding spanning rainbow cycles and trees in properly edge-colored complete graphs and present some recent progress on these problems.

Joint work with A. Pokrovskiy and in part with N. Alon

**Time:** 12:00-13:00 (Room S05)

**Speaker:** Dieter van Melkebeek, (University of Wisconsin-Madison)

**Title and Abstract:** Kernelization lower bounds from AP(3)-free sets

Many hard computational problems contain a parameter k other than the input size n that has a large impact on the computational complexity but in practice only takes on small values. A good example is the vertex cover problem, where one seeks a subset of at most k vertices of a given n-vertex graph that hit every edge of the graph. The trivial algorithm runs in time O(n^k), but there exist algorithms that take time O(f(k)+n^c) where c is a constant and f is an arbitrary function – a running time that is typically much better than the trivial algorithm.

One way to achieve such running times is through kernelization: Reduce in time polynomial in n to an equivalent instance of size bounded by some function g of the parameter k only, and then run a brute-force algorithm on the reduced instance. In order to obtain good parameterized algorithms, the functions f and g should not behave too badly, which motivates the quest for kernels of small size g(k).

For the vertex cover problem, the best known kernelizations yield graphs with O(k^2) edges. If P=NP there trivially exist kernelizations with O(1) edges. Under a hypothesis that is considered not much stronger than P<>NP, we’ll show that kernelizations with O(k^{2-epsilon}) edges do not exist for any positive constant epsilon. The proof hinges on the existence of AP(3)-free sets of high density, i.e., large subsets of {1,2,…,N} that do not contain arithmetic progressions of length 3.

Similar results hold for other NP-complete problems. For example, under the same hypothesis we can show that for any constant d>=3, d-CNF formulas cannot be sparsified in polynomial time below the trivial bound of O(n^k) bits while preserving satisfiability.

In fact, the results can be cast more generally as (conditional) lower bounds on the communication cost in the following two-player communication protocol to decide certain languages L: Alice holds the entire input x but is polynomially bounded; Bob is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small cost, where the cost measure is the number of bits of communication from Alice to Bob. As another application, under the same hypothesis we show the optimality of the size of the known probabilistically checkable proofs (PCPs) for the satisfiability problem on d-CNF formulas.

__Previous seminars in the Monthly Program:__

**Date: **Tuesday May 30, 2017**
Time: **10h-10h45

**Room 103,**

Where:

Where:

**Facultat de Matematiques i Estadistica**, Campus Sud UPC

**Wouter Cames van Batenburg, Radboud University Nijmegen**

Speaker:

Speaker:

**Title: **Packing graphs of bounded codegree

**Abstract: **Two graphs G1 and G2 of order n are said to pack if there exist injective mappings of their vertex sets into 1,…,n such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobas and Eldridge and, independently, Catlin, asserts that, if (Delta(G1)+1) (Delta(G2)+1) > n, then G1 and G2 pack. We consider the validity of this assertion under the additional assumption that G1 or G2 has bounded codegree. In particular, we prove for all t>=2 that if G1 does not contain a copy of the complete bipartite graph K_{2,t} and Delta(G1) > 17 t Delta(G2), then (Delta(G1)+1) (Delta(G2)+1) > n implies that G1 and G2 pack.

**Date: T**uesday May 30, 2017

**Time: **11h-11h50**
Where: **Room 103,

**Facultat de Matematiques i Estadistica**Campus Sud UPC

**Speaker: **Gilles Zemor, Univ. Bordeaux

**Title:** Unconditionally private communication through error correction

**Abstract: **In the model that has become known as “Perfectly Secure Message Transmission”(PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve will not get any information about the message while Bob will be able to recover it completely.

In this talk, we focus on protocols that work in two transmission rounds for n= 2t+1. We break from previous work by following a conceptually simpler blueprint for achieving a PSMT protocol. We reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n^3 log n) to O(n^2 log n). Our protocol also answers a question raised by Kurosawa and Suzuki and hitherto left open: their protocol reaches optimal transmission rate for a secret of size O(n^2 log n) bits, and the authors raised the problem of lowering this threshold. The present solution does this for a secret of O(n log n) bits. Additionally, we show how our protocol can be adapted to a Network Coding context.

**Date:** Tuesday June 6, 2017

**Time:** 10h30-11h15

**Where:** Room 103,** Facultat de Matematiques i Estadistica**, Campus Sud UPC

**Speaker:** Robert Hancock, Univ. of Birmingham

**Title:** Independent sets in hypergraphs and Ramsey properties of graphs and the integers

**Abstract:** Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris and Samotij, and independently Saxton and Thomason developed very general container theorems for independent sets in hypergraphs; both of which have seen numerous applications to a wide range of problems. We use the container method to prove results that correspond to problems concerning tuples of disjoint independent sets in hypergraphs.

We generalise the random Ramsey theorem of Rödl and Rucinski by providing a resilience analogue. This result also implies the random version of Turán’s theorem due to Conlon and Gowers, and Schacht. We prove a general subcase of the asymmetric random Ramsey conjecture of Kohayakawa and Kreuter. Both of these results in fact hold for uniform hypergraphs. We also strengthen the random Rado theorem of Friedgut, Rödl and Schacht by proving a resilience version of the result.

**Date:** Tuesday June 6, 2017

**Time:** 11h30-12h30

**Where:** Room 103, **Facultat de Matematiques i Estadistica**, Campus Sud UPC

**Speaker:** David Wood, Monash University

**Title:** Improper relaxations of Hadwiger’s Conjecture

**Abstract:** Hadwiger’s Conjecture asserts that every K_t-minor-free graph has a proper (t-1)-colouring. This talk is about improper relaxations of Hadwiger’s Conjecture. We prove that every K_t-minor-free graph is (2t-2)-colourable with monochromatic components of order at most ⌈(t-2)/2⌉. This result has no more colours and much smaller monochromatic components than all previous results in this direction. We then prove that every K_t-minor-free graph is (t-1)-colourable with monochromatic degree at most t-2. This is the best known degree bound for such a result. Both these theorems are based on a simple decomposition result of independent interest.

Improper colourings are interesting for other graph classes. For example, Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured with bounded monochromatic degree. We generalise this theorem for graphs excluding a complete bipartite graph, leading to new improper colouring results for graphs with linear crossing number, graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs with given thickness (with relevance to the earth-moon problem).

This is joint work with Jan van den Heuvel (arXiv:1704.06536) and Patrice Ossona de Mendez and Sang-il Oum (arXiv:1611.09060).