Let $\varepsilon > 0$ be fixed. Then the random graph $G(n,m=(1+\varepsilon))$ is a.a.s not planar.

Question

The exact question is in the title. I understand that I somehow need to find a graph with $K_{3,3}$ or $K_5$ as a minor, but I don't really know how. I got that having $K_5$ as a minor is equivalent to having $5$ disjoint sets $A_1,\dots, A_5$, all connected within the graph (that is, the induced subgraphs $G[A_i]$ are connected), with an edge from $A_i$ to $A_j$ for every $i\neq j$. Also a similar characterization for $K_{3,3}$. I tried manipulating the possible sizes of such sets to gain a high probability for having such a structure and it didn't quite work. Any suggestions?

Answer 1

To find large sets $A_1, \dots, A_5$ such that $G[A_1], \dots, G[A_5]$ are connected, it's enough to find a long path in $G$. It's a well-known result that when the random graph is supercritical, it a.a.s. has a path of linear length. Take such a path (of some length $cn$, where $c$ will depend on $\epsilon$ in some way we don't really care about) and let $A_1$ be its first $\frac15 cn$ vertices, $A_2$ be the next $\frac15 cn$, and so on.

To find edges between $A_i$ and $A_j$, a common technique to use is "sprinkling". Instead of doing the above process for the random graph with $(1 + \epsilon)\frac n2$ edges, take the random graph with $(1 + \frac{\epsilon}{2}) \frac n2$ random edges, and leave the last $\frac{\epsilon}{4}n$ edges in reserve. We can still find $A_1, \dots, A_5$ of linear size, though now the constant will be somewhat smaller.

Next, we see what happens when we add the reserve edges. For each pair $\{i,j\}$, each of the edges we held in reserve will be placed between $A_i$ and $A_j$ with a constant probability (again, a constant depending on $\epsilon$). Therefore the probability that we add $\frac{\epsilon}{4}n$ edges and don't get a single one joining $A_i$ and $A_j$ is exponentially small.

In fact, since the probability of failure is so small in the second stage, we can do a bit less work in the first stage, getting slightly smaller $A_1, \dots, A_5$ without using as powerful a result. Just combine the following ingredients:

1. The supercritical random graph a.a.s. has a giant component.

2. Any connected graph with $k$ vertices and maximum degree $\Delta$ can be split into two connected subgraphs with at least $\frac{k-1}{\Delta}$ vertices each. (Just find the 1-vertex or 2-vertex center of its spanning tree.)

3. The random graph with a linear number of edges a.a.s. has maximum degree $O(\log n)$.

This idea will give you $A_1, \dots, A_5$ of size $\Omega(\frac{n}{\log n})$, which is still large enough for the sprinkling to work.

---

Relatedly, when the random graph is subcritical, then it is a.a.s. planar; in fact, when the random graph is subcritical, every component a.a.s. has at most one cycle, and it's easy to draw such a component in the plane. This holds somewhat more strongly when $\frac n2 - m \gg n^{2/3}$.