[go: up one dir, main page]
Scribd
Upload
35 views2 pages

MATH5425 ProblemSheet3

This document is a problem sheet for the MATH5425 Graph Theory course at UNSW Sydney for Term 1, 2025. It includes problems related to the probabilistic method in graph theory, random functions, and dominating sets in graphs, requiring calculations of expected values and probabilities. The problems aim to deepen understanding of random graphs and their properties through mathematical proofs and applications.

Uploaded by

TiltTheTilt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
35 views2 pages

MATH5425 ProblemSheet3

This document is a problem sheet for the MATH5425 Graph Theory course at UNSW Sydney for Term 1, 2025. It includes problems related to the probabilistic method in graph theory, random functions, and dominating sets in graphs, requiring calculations of expected values and probabilities. The problems aim to deepen understanding of random graphs and their properties through mathematical proofs and applications.

Uploaded by

TiltTheTilt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

SCHOOL OF MATHEMATICS AND STATISTICS

UNSW Sydney
MATH5425 Graph Theory Term 1, 2025
Problem Sheet 3, Probabilistic Method
1. Consider the uniform model of random graphs on the vertex set {1, . . . , n}.
Recall that Pr(ij is an edge) = 21 , independently for each 1 ≤ i < j ≤ n.
(a) For 1 ≤ i < j ≤ n let Xij be the indicator variable for the event that
{i, j} is an edge in a uniformly random graph. Calculate EXij .
P
(b) What is counted by 1≤i<j≤n Xij ?
(c) Let X be the number of edges in a uniformly random graph  on n ver-
1 n
tices. Using linearity of expectation, prove that EX = 2 2 .
(Compare this proof with the direct proof given in lectures: which do you
prefer?)
2. Let Ω be the set of all functions g : S → {1, . . . , k} for some finite set S
and positive integer k. Form the random function f ∈ Ω using the following
procedure: choose f (a) ∈ {1, . . . , k} uniformly at random, independently for
each a ∈ S.
(Note: choosing an element uniformly at random from a set B means “ac-
cording to the uniform probability distribution on B”, with each element of
B equally likely to be chosen.)
(a) Calculate |Ω|.
(b) Let f0 ∈ Ω be any fixed function in Ω. Prove that Pr(f = f0 ) = 1/|Ω|.
3. Let Ω be the set of all subsets of a given finite set S, and p ∈ R with
0 ≤ p ≤ 1. Define the map π : Ω → [0, 1] by π(X) = p|X| (1 − p)|S|−|X| for all
X ⊆ S.
P
(a) Show that π is a probability distribution (i.e., X⊆S π(X) = 1).
(b) Now consider a random subset Y of S constructed by the following
procedure: put a ∈ Y with probability p, independently for each element
a ∈ S.
Prove that for any subset Y0 of S we have Pr(Y = Y0 ) = π(Y0 ). (That
is, the probability distribution on Ω which results from this procedure
is exactly given by π.)
(In (b), you can imagine flipping a biased coin which has Pr(heads) = p,
independently for each a ∈ S, and place a ∈ Y if the coin comes up heads.)

(... Please turn over for Question 4)


4. A dominating set in a graph is a set of vertices U ⊆ V such that every vertex
which is not in U has a neighbour in U . Suppose that G has n vertices and
minimum degree δ ≥ 1. We will prove that G has a dominating set of at
most
n(1 + ln(δ + 1))/(δ + 1)
vertices, using the probabilistic method.

(a) For a given p ∈ [0, 1], choose a random subset X of V using the proce-
dure of Question 3(b). Let Y = YX be the random set of all vertices in
V − X that do not have a neighbour in X. Calculate E|X| and prove
that E|Y | ≤ n(1 − p)δ+1 .
(b) Hence show that G has a dominating set of size at most

np + n(1 − p)δ+1 .

(c) Use the bound 1 − p ≤ e−p (which is a very good approximation when p
is small) to (approximately) minimise the above expression, completing
the proof.

You might also like