Random Graphs

for any $p\in (0,1)$ there exists a set of vertices $A\subset V$ such that the union of $A$ and the set of all vertices not joined to any vertex of $A$ contains at most $np+n(1-p)^{\delta +1}$ vertices;

there exists a set of vertices $D\subset V$ such that every vertex of $V\setminus D$ is joined by an edge to some vertex of $D$ and $\left|D\right|\leqslant n\dfrac {1+\ln (\delta +1)}{\delta +1}$.

If $\dbinom {k}{m}p^{\binom {m}{2}}+\dbinom {k}{n}(1-p)^{\binom {n}{2}} < 1$ for some $p\in (0,1)$, then $R(m,n) > k$ (here $R(m,n)$ are the Ramsey numbers, see Sec. 4.1).

$R(4,n) \geqslant \Omega \left(\dfrac {n^2}{\ln^2 n}\right)$ (we write $g \geqslant \Omega (f)$ if $f=O(g)$).

Cherchez la femme. At a Russian-French meeting there were no representatives of other countries. The total amount of money held by the French turned out to be greater than the total amount of money held by the Russians, and the total amount of money held by the women turned out to be greater than the total amount of money held by the men. Must there have been a Frenchwoman at the meeting?

Banknotes of different denominations and from different countries are packed into two suitcases. The average value of a banknote equals 100 rubles. The total number of banknotes in the left suitcase is greater than in the right one. Must there be a banknote worth at most 200 rubles in the left suitcase? (Cf. Markov's inequality 6.3.9 (1).)

For any integers $l,q>0$ there exists a graph that contains no cycles of length less than $l$ and cannot be properly colored in $q$ colors. (See the definition of a proper coloring in Sec. 3.1.)

isolated vertices;

triangles;

$k$-cliques;

$k$-cliques that are connected components;

Hamiltonian cycles;

non-self-intersecting cycles of length $k$;

non-self-intersecting cycles of length $k$ that are connected components with exactly $k$ edges;

trees with $k$ vertices;

tree components of a given size $k$, i.e., trees with $k$ vertices that are connected components.

isolated vertices;

triangles.

$\mathbb {E}\left[X+Y\right] = \mathbb {E}\left[X\right]+\mathbb {E}\left[Y\right]$;

$\operatorname {Var}\left[X+Y\right] = \operatorname {Var}\left[X\right]+\operatorname {Var}\left[Y\right]$ if $X$ and $Y$ are independent (i.e., for any $x,y$ we have $\mathbb {P}\left(X=x,Y=y\right)=\mathbb {P}\left(X=x\right)\cdot \mathbb {P}\left(Y=y\right)$).

Markov’s inequality. $\mathbb {P}\left(\left|X\right|>a\right) \leqslant \mathbb {E}\left[\left|X\right|\right]/a$. (Cf. Problem 6.3.3 (1).)

Chebyshev’s inequality. $\mathbb {P}\left(\left|X-\mathbb {E}\left[X\right]\right|>a\right) \leqslant \operatorname {Var}\left[X\right]/a^2$.

a.a.s.there are more than $n/2$ isolated vertices;

for some $C>0$, a.a.s.every connected component has fewer than $C\ln n$ vertices (specialists say: fewer than $O(\ln n)$ vertices);

a.a.s.every connected component is a tree or a unicyclic graph;

for some $C>0$, a.a.s.there are fewer than $C$ unicyclic components.

For $p(n)=o(n^{-3/2})$, a.a.s.the edges are pairwise disjoint.

For $p=p(n)=o(n^{-3/2})$ and $pn^2\to \infty$, there exists a function $r=r(n)=o(pn^2)$ such that a.a.s.the number of vertices of degree 1 is greater than $pn^2-r$ and less than $pn^2+r$, and the degrees of all the other vertices are zero.

Find at least one function $p^*(n)$ such that

• for $p(n)/p^*(n)\to 0$, a.a.s.the graph contains no triangle,

• for $p(n)/p^*(n)\to +\infty$, a.a.s.the graph contains a triangle.

The same with the triangle replaced by a subgraph isomorphic to $K_4$.

one for $p(n)=o(1/n^2)$;

two for $p(n)=o(1/n)$;

three for $p(n)=c/n$, where $c<1$.

The greedy coloring algorithm (see Problem 3.2.3: the vertices of the graph are processed in some order, and each of them is assigned the smallest color that does not occur among its already colored neighbors), for any positive $\varepsilon$, a.a.s.(for $p(n)=1/2$) errs by a factor of at most $2+\varepsilon$.

For any $\varepsilon ,\delta >0$ there exists a sequence $G_n$ of graphs with $n$ vertices such that, for a random numbering of the vertices of the graph $G_n$ (i.e., with the probability of each numbering equal to $1/2$), the probability that the ratio of the number of colors in the greedy coloring to $\chi (G_n)$ is greater than $n^{1-\varepsilon }$ is greater than $\delta$. (In other words, on the one hand, for almost every graph the greedy coloring is good in any numbering, but, on the other hand, there are graphs for which, almost no matter how you number them, the result is still rubbish!)