Scribd
Upload
28 views4 pages

C8.4 Problems2

This document contains a set of practice problems in probabilistic combinatorics. Section A contains problems about graph balance and strictly balanced graphs. Section B covers random graph thresholds and coloring problems. Section C contains optional advanced problems applying probabilistic techniques like the first and second moment methods and the local lemma to questions about satisfiability, graph coloring, and distributions.

Uploaded by

Mihnea-Gabriel Doica
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
28 views4 pages

C8.4 Problems2

This document contains a set of practice problems in probabilistic combinatorics. Section A contains problems about graph balance and strictly balanced graphs. Section B covers random graph thresholds and coloring problems. Section C contains optional advanced problems applying probabilistic techniques like the first and second moment methods and the local lemma to questions about satisfiability, graph coloring, and distributions.

Uploaded by

Mihnea-Gabriel Doica
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/ 4

C8.

4 Probabilistic Combinatorics
Sheet 2 — HT23
Second moment method; Local Lemma

Section A
1. Show that all (finite) graphs of the following types are strictly balanced: complete
graphs, cycles, trees, complete bipartite graphs, connected regular graphs.
Give (with proof) an example of a graph that is balanced but not strictly balanced.

Mathematical Institute, University of Oxford Page 1 of 4


Oliver Riordan: [email protected]
C8.4 Probabilistic Combinatorics: Sheet 2 — HT23

Section B
2. Let T be a tree with k vertices. What is the threshold for G(n, p) to contain a copy of
T?
Show that, for each fixed k, there is a function p(n) such that the probability that
G(n, p(n)) has a component of size exactly k tends to 1 as n → ∞.

3. What is the threshold for G(n, p) to contain a cycle of length k, for fixed k?
Find a threshold function for the property of containing a cycle. [Careful! It doesn’t
quite follow immediately from the first part.]
√
4. Show that it is possible to colour the edges of Kn with k = ⌈3 n⌉ colours so that no
triangle has all its edges the same colour.

5. Let H = (V, E) be a hypergraph. Suppose the vertices are k-coloured uniformly at


random; each v ∈ V receives each colour with probability 1/k, and the colours of
different vertices are independent. For e ∈ E, let Ae be the event that the hyperedge e
is monochromatic.
Show that if |e ∩ f | ⩽ 1, then Ae and Af are independent.
Is it true that Ae is independent of the collection {Af : |e ∩ f | ⩽ 1} of events?

6. A k-SAT (more properly k-CNF) formula is an expression such as (for k = 3)

(x1 or x4 or x6 ) and (x1 or x2 or x5 )


and (x2 or x3 or x4 ) and (x4 or x5 or x6 ),

where the variables xi take values true or false, xi means not xi , and k distinct
variables or their negations are ORd together in each clause. A formula is satisfiable if
there is an assignment of values to the variables making the expression true.
(a) Use the first-moment method to show that each k-SAT formula with fewer than 2k
clauses is satisfiable.
(b) Use the Symmetric Local Lemma to show that each k-SAT formula in which no
variable appears in more than 2k−2 /k clauses is satisfiable.

7. Let G = (V, E) be a graph with maximum degree ∆, and let V1 , V2 , . . . , Vs be a collection


of disjoint subsets of V , each of size k ⩾ 2e∆. Show that G has an independent set
which contains a vertex from each set Vi . [There is a hint at the bottom of the last
page.]

Mathematical Institute, University of Oxford Page 2 of 4


Oliver Riordan: [email protected]
C8.4 Probabilistic Combinatorics: Sheet 2 — HT23

8. Let G = (V, E) be a graph, and suppose that for each v ∈ V there is a list S(v) of at
least 2er colours, where r is a positive integer. Suppose also that for each v ∈ V and
each c ∈ S(v), there are at most r neighbours u of v such that c ∈ S(u).
Prove that there is a proper colouring of G under which each vertex v receives a colour
from its list S(v).

9. Let W (k) be the smallest integer n such that any two-colouring of the set {1, 2, . . . , n}
contains a monochromatic arithmetic progression of length k.
(a) Use the first-moment method to show that W (k) ⩾ 2k/2 .
2k

(b) Use the Local Lemma to show that W (k) ⩾ 2ek
1 + o(1) .

Mathematical Institute, University of Oxford Page 3 of 4


Oliver Riordan: [email protected]
C8.4 Probabilistic Combinatorics: Sheet 2 — HT23

Section C
These questions are optional, but MFoCS students are recommended to at-
tempt them. Outline solutions will be provided later; you can also approach
class tutors (if they have time) or the lecturer to discuss them.

10. Let X1 , X2 , . . . be a sequence of random variables each taking non-negative integer


values, and let k ⩾ 0 be fixed. Suppose that for each r ⩾ 0 we have limn→∞ Er [Xn ] =
λr < ∞, and that λr+k /r! → 0 as r → ∞. show that
∞
1 X λr+k
P(Xn = k) → (−1)r .
k! r=0 r!

[ Hint: Use a result from last time. Be careful exchanging sums and limits! You may
wish to just/first do the case k = 0. ]
In applications we often have a limiting distribution X in mind; this result shows that
under certain assumptions, if the moments of Xn tend to those of X, then P(Xn = k) →
P(X = k).

11. Let c > 0 be constant. Suppose that p = p(n) satisfies n4 p6 → c as n → ∞, and let Xn
denote the number of copies of K4 in G(n, p). Show that P(Xn > 0) → 1 − e−c/24 as
n → ∞.
[ Hint: use the result of the previous question. ]
What can you say about the distribution of the number of copies of K4 ? Can you
generalize this to (certain) other graphs?

Hint for Question 7: pick one vertex Xi from each Vi . You could consider a ‘bad’ event Euv
for each edge uv with u and v in different sets Vi .

Mathematical Institute, University of Oxford Page 4 of 4


Oliver Riordan: [email protected]

You might also like