5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Is this homework? $\endgroup$
    – Brendan McKay
    Commented May 2, 2013 at 15:45
  • $\begingroup$ @tempestadept, what is the definition of a "unit distance graph", please? $\endgroup$
    – Włodzimierz Holsztyński
    Commented May 2, 2013 at 17:02
  • $\begingroup$ @Brendan McKay, No @Wlodzimierz Holsztynski, $V(G)\subset\mathbb{R}^2$, $E(G)=\{(v,w)|d(v,w)=1\}$. $d$ is euclidean distance. $\endgroup$
    – tempestadept
    Commented May 2, 2013 at 17:30
  • $\begingroup$ 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. $\endgroup$
    – Benoît Kloeckner
    Commented May 2, 2013 at 20:44

1 Answer 1

Reset to default
6
$\begingroup$

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).

These two facts end the proof of your problem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can we identify some class of non-unit-distance graphs that are almost surely contained in such a random graph? $\endgroup$
    – Brendan McKay
    Commented May 3, 2013 at 3:28
  • $\begingroup$ 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$. $\endgroup$
    – Benoît Kloeckner
    Commented May 3, 2013 at 7:15
  • $\begingroup$ 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 $\endgroup$
    – tempestadept
    Commented May 4, 2013 at 19:24
  • $\begingroup$ 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. $\endgroup$
    – Benoît Kloeckner
    Commented May 4, 2013 at 20:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .