About | Research | Events | People | Reports | Alumni | Contact | Home
|
January 6-10, 2014 Workshop on
Probability and Graphs
SUMMARY This workshop will be the kickoff for the Stochastic
Activity Month on
Combinatorics and
Probability.
ORGANISERS
LIST OF INVITED PARTICIPANTS
MONDAY JANUARY 6
TUESDAY JANUARY 7
WEDNESDAY JANUARY 8
THURSDAY JANUARY 9
FRIDAY JANUARY 10
***************************************************************************************************************************************** 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 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. 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. 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. 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$. 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).
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 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. 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. 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. 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.
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. Gábor Lugosi Connectivity properties of random geometric irrigation graphs Consider a graph whose vertices represent n uniform
random points in the unit square. 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. 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. 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. 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. Miklos Simonovits Embedding trees into graphs 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. 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.
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. (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. 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. Danny Vilenchik Chasing the k-colorability thresholdIn 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. Lutz WarnkePhase 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. PRACTICAL INFORMATION ● VenueEurandom, 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
Metaforum building
(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).
● ContactMrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl SPONSORSThe organisers acknowledge the financial support/sponsorship of:
Last updated
09-04-14,
|
.jpg)
