Crossings in Randomly Embedded Graphs

A graph is pair $G=(V,E)$, where $E\subset\{\{v,w\}|v,w\in V\}$. Elements in $V$ are called vertices and elements in $E$ are called edges. An edge $\{v,w\}$ is sometimes written as $v\sim_{G}w$ or $v\sim w$ if the underlying graph $G$ is clear. The number or vertices $|V|$, will be denoted by $n$, while the number of edges, $|E|$, will be denoted be $m$.

For a vertex $v$, we say that $w$ is a neighbour of $v$, if $\{v,w\}\in E$. The number of neighbours of $v$ is called the degree of $v$, denoted by $deg(v)$. The largest degree among all vertices in a graph will be denoted by $\Delta$.

A subgraph of $G$, is a graph, $H=(W,F)$, such that $W\subset V$ and $F\subset G$. We say that $G=(V,E)$ and $G^{\prime}=(V^{\prime},E^{\prime})$ are isomorphic if there exist a bijection $\varphi:V\to V^{\prime}$ such that $\{u,v\}\in E$ if and only if $\{\varphi(u),\varphi(v)\}\in E^{\prime}$, for all $u,v\in V$.

An $r$-matching in a graph $G$ is a set of $r$ edges in $G$, no two of which have a vertex in common. We denote by $M_{r}(G)$ the set $r$-matchings of $G$ and by $m_{r}(G)$ their cardinality. Note the $m_{1}=m$ corresponds to the number of edges of the graph $G$.

Let $X$ be a positive random variable with mean $\mu$ finite. We say that the random variable $X^{s}$ has the size bias distribution with respect to $X$ if for all $f$ such that $\mathbb{E}[Xf(X)]<\infty$, we have

In the case of $X=\sum_{i=1}^{n}X_{i}$, with $X_{i}$’s positive random variables with finite mean $\mu_{i}$, there is a recipe to construct $X^{s}$ (Proposition 3.21 from [6]) from the individual size bias distributions of the summands $X_{i}$:

1. 1.

   For each $i=1,\ldots,n$, let $X_{i}^{s}$ having the size bias distribution with respect to $X_{i}$, independent of the vector $(X_{j})_{j\neq i}$ and $(X_{j}^{s})_{j\neq i}$. Given $X_{i}^{s}=x$, define the vector $(X_{j}^{(i)})_{j\neq i}$ to have the distribution of $(X_{j})_{j\leq i}$ conditional to $X_{i}=x$.

2. 2.

   Choose a random index $I$ with $\mathbb{P}(I=i)=\mu_{i}/\mu$, where $\mu=\sum\mu_{i}$, independent of all else.

3. 3.

   Define $X^{s}=\sum_{j\neq I}X_{j}^{(I)}+X_{I}^{s}$.

It is important to notice that the random variables are not necessarily independent or have the same distribution. Also, $X$ can be an infinite sum (See Proposition 2.2 from [2]).

If $X$ is a Bernoulli random variable, we have that $X^{s}=1$. Indeed, if $\mathbb{P}(X=1)=p$, $\mathbb{E}(X)=p=\mu$ and then

Therefore, we have the following corollary (Corollary 3.24 from [6]) by specializing the above recipe.

The following result (Theorem 5.3 from [2]) gives us bounds for the Kolmogorov distance, in the case that a bounded size bias coupling exists. This distance is given by

where $F_{X}$ and $F_{Y}$ are the distribution functions of the random variables $X$ and $Y$.

Let $\pi$ be a fixed permutation and let $I=(e,f)$ be a random index chosen with probability $\mathbb{P}(I=i)=1/m_{2}(G)$ , which corresponds to a 2-matching (in this way $e,f$ are edges), and which is independent of $\pi$. For said fixed $\pi$, we have a fit $G_{\pi}$. We construct $\pi^{s}$ as follows

• •

  If $\pi$ is such that $G_{\pi}$ has a crossing at $I$, we define $\pi^{s}=\pi$.

• •

  Otherwise, we perform the following process to obtain a permutation with a cross on $I$. Suppose $e=\{u_{1},u_{2}\}$ and $f=\{v_{1},v_{2}\}$, then under $\pi$ these edges are $\pi(e)=\{\pi(u_{1}),\pi(u_{2})\}$ and $\pi(f)=\{\pi(v_{1}),\pi(v_{2})\}$. Since they do not cross, without loss of generality we can assume that $\pi(u_{1})<\pi(v_{1})<\pi(v_{2})<\pi(u_{2})$ satisfies. Now, we choose a random vertex uniformly among the vertices of the edges of $I$. In case the vertex is $u_{1}$ or $v_{1}$, we leave these fixed and swap the positions between $\pi(v_{2})$ and $\pi(u_{2})$ and define $\pi^{s}$ as the resulting permutation. In case of choosing $u_{2}$ or $v_{2}$, we do the same process leaving these vertices fixed and exchanging $\pi(v_{1})$ and $\pi(u_{1})$. In this way we obtain a permutation $\pi^{s}$ such that it has a crossing at $I$

Note that $\pi^{s}$ is a uniform random permutation conditional on the event that $\pi(u_{i})$’s and $\pi(v_{i})$’s are in alternating in the cyclic order. This in turn means that $G_{\pi^{s}}$, is a uniform random embedding conditioned on the event that the event $I$ has a crossing.

In summary, we obtain that

satisfies $\{Y_{\pi^{s}(j)}\}_{j\neq I}$ has the distribution of $\{Y_{\pi(j)}\}_{j\neq I}$ conditional on $Y_{\pi(I)}=1$. Then, by Corollary 1, we get that $X^{s}=X(G_{\pi^{s}})$, has the size bias distribution of $X$.

Define $X^{s}=X(G_{\pi}^{s})$ as the size bias transform of $X(G_{\pi})$. By construction, $|X^{s}-X|\leq 2\Delta(m-1)$. Indeed, because in the worst case each of the edges incident to each vertex creates a new crossing.

In order to use Theorem 2 we need a bound for the variance of a conditional expectation, which depends of $X$ and its size bias transform $X^{s}$. A bound for that variance is given in the next lemma, which is one of the main results in this paper.

Using the previous results, we are in position to apply Theorem 2. Therefore, we can obtain a bound for the Kolmogorov distance of the (normalized) number of crossings and a standard Gaussian random variable.

Let $G$ be a pairing or matching graph on $2n$ vertices, that is, a disjoint union of $n$ copies of $K_{2}$, as in Example 1. In particular, $m=n$, $m_{2}(G)=\binom{n}{2}$ and $m_{4}(G)=\binom{n}{4}$ and the variance is given by

which is bigger that $n^{3}/45$ for $n>3$. On the other hand, since $\Delta=1$, we see that, for $n>3$,