Transcript random planar graph

On the degree distribution of random planar graphs
Angelika Steger
(joint work with Konstantinos Panagiotou, SODA‘11)
Motivation
Random Graphs
from
Classes with Constraints
Classical Random Graph Theory
Paul Erdős, Alfred Rényi
On the evolution of random graphs
Publ. Math. Inst. Int. Hungar. Acad. Sci., 1960
Given: a set of n vertices.
Decide for each potential edge
randomly and independently
whether edge is present.
Key property:
edge probability p
→ random graph Gn,p
Independence of edges.
The Setup
• Examples (classes with constraints):
– Trees, Outerplanar Graphs, Planar Graphs, etc.
– Generally: excluding a minor (or a fixed subgraph)
• Random Graph:
– This talk: according to the uniform distribution
• Typical questions for such a random graph:
–
–
–
–
Number of edges?
Degree Sequence? [Number of vertices of degree loglog(n)?]
The obvious problem: no
Subgraph count?
independence! 
Evolution?
Test Case: Random Planar Graphs
Colin McDiarmid, AS, Dominic Welsh
Random planar graphs
Journal of Combinatorial Theory, Series B, 2005
Pn
:= set of all planar graphs on n (labelled) vertices
Pn := graph drawn randomly from Pn
( → random planar graph)
 c, C:
0 < c < Prob[Pn connected ] < C < 1
Connectedness – Proof Idea
Direct approach: Counting ...
Prob[Pn connected ] =
# connected planar graphs on n vertices
# planar graphs on n vertices
We: rough, adhoc methods
Giménez, Noy, 2009:
|Pn| ≈ p · n−7/2 · γn · n!
where
|Cn| ≈ c · n−7/2 · γn · n!
where
p = 4.26094.. · 10−6
γ ≈ 27.2269..
c ≈ 4.10436.. · 10−6
Techniques
• ”Classical” approach:
– enumeration: count graphs with specific
properties…
– analytic combinatorics …
– Lots of papers ... [in particular: Drmota, Giménez, Noy ...]
• This talk:
– sample a graph
• Boltzmann Sampling
• analyze the construction during the execution of the
algorithm
– find and exploit independence in the probability
space
Outline
• 1) The Power of Independence
• 2) Boltzmann Sampling
• 3) Block Structure
• 4) Degree Sequence
Recall
Azuma-Hoeffding :
If for
then
there are
s.t.
A General Decomposition
Block Decomposition (of a connected graph)
The Key Idea
• Condition on the block structure! Specify
– How many blocks of size
– How they „touch“ each other
there are, and
• Observation: can generate a
graph with given block
structure by choosing the
blocks independently!
• So we obtain a product
probability space.
Outline
• 1) The Power of Independence
• 2) Boltzmann Sampling
• 3) Block Structure
• 4) Degree Sequence
Generation of Random Objects
Duchon, Flajolet, Louchard, Schaeffer
Boltzmann Samplers for the Random
Generation of Combinatorial Structures
Combinatorics, Probability and Computing, 2004
Boltzmann Sampler
G(x)
|G|:== # of
An algorithm ΓG (x) that generates an element
generating
verticesGofGG is called
Boltzmann Sampler iff
function for
class G
Observations:
• If we condition on |ΓG (x)| = n,
then ΓG (x) is a uniform sampler.
• Expected size of the output depends on the parameter x:
A Sampler for Connected Graphs
A Branching Process:
ΓC (x):
for λC and μC
appropriately
(details later)
...
d ⟶ Po(λ )
C
for i = 1,..., d:
Bi ⟶ ΓB (μC)
(d1, d2 , …)
(B1, B2, … )
ΓC (x)
C
for u ∈ Bi (except the root)
replace u with ΓC (x)
identify root of Bi with v
Why Is This Useful ?
(d1, d2 , …)
(B1, B2, … )
ΓC (x)
C
• The di‘s and the Bi‘s are drawn independently!
• Under reasonable assumptions:
x=ρ
Idea: properties of the sequences (d1, d2 , … , di , …) and (B1, B2 , … , Bi , …) that
hold with „extremely high“ probability also hold for a random object
Why Is This Useful (cont.) ?
(d1, d2 , …)
(B1, B2, … )
ΓC (ρ)
C
• Suppose that the sampler ΓC (ρ) used the values
(d1, d2 , …, dn) and (B1, B2, …, Bm) to generate C
• By inspecting the sampler:
- n is the total number of vertices in C
- m satisfies
and (by Chernoff)
(d1, d2 , …)
(B1, B2, … )
ΓC (ρ)
C
E: ΓC (ρ) generates a graph on n vertices
A:
B: B1,..., Bm satisfy property P
BΓ: blocks of ΓC (x) satisfy property P
Note: blocks are independent ... can apply e.g. Chernoff bounds
Summary
(d1, d2 , …)
(B1, B2, … )
ΓC (ρ)
In order to bound
it suffices to bound
where
A:
B: B1,..., Bm satisfy property P
C
Outline
• 1) The Power of Independence
• 2) Boltzmann Sampling
• 3) Block Structure
• 4) Degree Sequence
Nice Graph Classes
• Let
be the set of biconnected graphs in
• is nice if
– Every
–
and
looks like
are „small“:
and
• Examples: planar, outerplanar, minor-free, ...
[Norin, Seymour, Thomas, Wollan ‘06]
Block Structure
Panagiotou, St. (SODA’09)
Let C be a random graph from a ‘nice‘ class.
Let
be the singularity of B(x). Then the following is true a.a.s.
– If
, then
C has blocks of at most logarithmic size.
– If
, then
• The largest block in C contains
• The second largest block contains
• There are „many“ blocks that contain
vertices.
vertices.
vertices.
Simple vs. Complex
Simple
Complex
„Plenty“ of
independence
A „lot“ is hidden in
the large block
e.g. outerplanar graphs,
series-parallel graphs
e.g. planar graphs
Outline
• 1) The Power of Independence
• 2) Boltzmann Sampling
• 3) Block Structure
• 4) Degree Sequence
Sampler Connected Graphs
(λ1, λ2 , … , λi , …)
(B1, B2 , … , Bi , …)
ΓC (x)
C
List of parameters distributed indep. according to Po(λC).
List of vertex rooted biconnected graphs distr. indep. according to ΓB(μC).
Subcritical case


Every vertex is born with a certain degree
It then receives a certain number of new
neighbors – indep. of its birth degree
pk-l = P
d l = P[
[ receive k-l more neighbors later ]
born with degree l]
Intuitively:

inner vertex of biconnected component

Poisson many copies of a root of a biconnected component
Critical Case


Every vertex is born with a certain degree
It then receives a certain number of new
neighbors – indep. of its birth degree
Intuitively:
large
component
„remainder“
2-connected ⟶ connected
Panagiotou, St. (SODA’11)
For ‘nice‘ graph classes we have: if
then
where k0‘(n) and c(.) depend on k0(n) resp b(.)
3-connected ⟶ 2-connected
Panagiotou, St. (SODA’11)
For ‘nice‘ graph classes we have: if
then
where k0‘(n) and b(.) depend on k0(n) resp t(.)
Summary
Bernasconi, Panagiotou, St (‘08):
- degree sequence of random dissections
Bernasconi, Panagiotou, St (‘09):
- degree sequence of series-parallel graphs
Johannsen, Panagiotou (’10):
- degree sequence of 3-connected planar graphs
Panagiotou, St. (’11):
- degree sequence of planar graphs
Note: similar results were obtain (using different methods) by Drmota, Giménez, Noy ...
Work in Progress
Maximum degree of a random planar graph:
Reed, McDiarmid (`08):
θ(log n)
Boltzmann sampler approach:
∃ a vertex of degree ≧ (1- ε) c log n
analytic combinatorics approach:
∄ a vertex of degree ≦ (1+ ε) c log n