The probabilistic method with a network graph

Question

This is a question from a course about probabilistic methods in combinatorics.

Let a network be represented by a graph G (each user is represented by a vertex and every communication route between two users is a set of edges connecting their two vertices).

There are n disjoint couples of users who wish to communicate. Every couple $P_i$ has a list $F_i$ of $m$ possible routes in which they can communicate. Routes are said to be cut if they contain a mutual edge.

Assume that for every i,j and for every route in $F_i$ there are at most $k$ routes in $F_j$ that cut $F_i$, and $8nk \leq m$.

Prove that every couple of users $P_i$ (every two vertices) can be connected by routes from their lists $F_i$ s.t. no two routes are cut.

Idea: Choose a route for each couple of vertices. Got stuck with figuring out how the events are dependent in order to use Lovász local lemma.

Any help would be appreciated.

Answer 1

The simplest way to obtain a dependency graph for the local lemma is as follows: if

1. your random object is obtained by choosing a bunch of independent random variables, and

2. each event is determined by a subset of those random variables,

then each event is independent of all those events that use a disjoint subset of random variables. (In other words, two events are adjacent in the dependency graph if they share a random variable.) In special cases, you might be able to have fewer dependencies, but you will never need more.

Here, we have:

• Random variables $X_1, X_2, \dots, X_n$ with each $X_i$ uniformly sampled from $F_i$: it's a uniformly random route connecting couple $P_i$.
• An event $A_{ij}$ for every pair $i,j$: this is the event that route $X_i$ cuts route $X_j$.

The event $A_{ij}$ is determined by the random variables $\{X_i, X_j\}$, and therefore the dependency graph should be as follows: $A_{ij}$ depends on $A_{i1}, A_{i2}, \dots, A_{in}$ (all events that care about $X_i$) and on $A_{1j}, A_{2j}, \dots, A_{nj}$ (all events that care about $X_j$).

That's $2n-2$ events, not counting $A_{ij}$ itself, which plugs directly into the symmetric local lemma to give you a condition slightly weaker than $8nk \le m$.