# Random graphs nonisomorphic to unit distance graphs

I've encountered an interesting problem but can solve it only partially:

Prove that random graph $G\sim G\left(n,\frac cn\right)$, $c=const$, almost surely is isomorphic to some unit distance graph on a plane if $c$ is sufficiently small and almost surely won't be ismorphic to any unit distance graph on a plane if $c$ is sufficiently large.

I can prove only the first part (for $c<1$, connected components of $G$ will almost surely contain no more than 1 cycle, and it's easy to show that such $G$ can be represented as a unit distance graph).

Some precisions: the model for random graphs is the one of Erdös and Renyi ($G$ has $n$ vertices and each edge is present with probability $c/n$), and almost surely'' means that the probability of the event goes to $1$ when $n\to\infty$.

A unit distance graph is a graph that can be represented by point in the plane, with two points joined by an edge if and only if their are at unit distance one from the other.

• Is this homework? – Brendan McKay May 2 '13 at 15:45
• @tempestadept, what is the definition of a "unit distance graph", please? – Włodzimierz Holsztyński May 2 '13 at 17:02
• @Brendan McKay, No @Wlodzimierz Holsztynski, $V(G)\subset\mathbb{R}^2$, $E(G)=\{(v,w)|d(v,w)=1\}$. $d$ is euclidean distance. – tempestadept May 2 '13 at 17:30
• It seems a bit harsh to me to close. I took the liberty to add precisions (which I hope do not depart from what the OP had in mind) that are better in the question than in comments; I think that there is question here, even if it is not very difficult once one has the right ingredients. – Benoît Kloeckner May 2 '13 at 20:44

The almost sure asymptotic chromatic number of $G$ goes to $\infty$ with $c$, see for example the precise result by Achlioptas and Naor in Annals of Math. 2005.
The chromatic number of a unit-distance graph (and in fact of the whole plane) is bounded above by $7$, see e.g. the math coloring book by Soifer (this is simple: one colors an hexagonal tiling of carefully chosen side length).
• I have thought a little bit about that, but I am not familiar enough with random graphs to answer. If I had the courage to make precise computations, I would bet on the family of wheels (one vertex connected to all vertices of a cycle) with more than 7 vertices, or more generally the family of graphs with one vertex connected to all the other, and the other inducing a graph with either a connected component of size $>6$ or a connected component with a vertex of degree 3. This makes a large family of non-unit-distance graphs, so it is somewhat likely that one of these graphs appears in $G$. – Benoît Kloeckner May 3 '13 at 7:15
• Well, $K_4$ and $K_{2,3}$ are classic examples of non-unit distance graphs, but with edge probability of $\frac cn$ $G$ almost surely won't contain any of these subgraphs. As for wheels in general, I'm not sure about how to estimate their probability – tempestadept May 4 '13 at 19:24
• I think you cannot exclude any given graph, because your random graphs are too sparse to exclude anything but forests. What you can try is to find an infinite family $\mathcal{F}$ of non-unit-distance finite graphs, and prove that as $n\to\infty$, your random graph will contain one of the members of $\mathcal{F}$ with high probability. This is probably a good exercise to someone wanting to get familiar with random groups. – Benoît Kloeckner May 4 '13 at 20:57