most recent 30 from http://mathoverflow.net 2013-05-24T13:17:59Z http://mathoverflow.net/feeds/user/26959 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/129407/random-graphs-nonisomorphic-to-unit-distance-graphs tempestadept 2013-05-02T11:30:11Z 2013-05-02T20:47:22Z

<p>I've encountered an interesting problem but can solve it only partially:</p> <blockquote> <p>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.</p> </blockquote> <p>I can prove only the first part (for $c&lt;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).</p> <p><strong>Some precisions:</strong> 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$.</p> <p>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.</p>

http://mathoverflow.net/questions/108692/property-of-cube-hypergraph-qn-n tempestadept 2012-10-03T06:04:51Z 2012-10-03T13:43:11Z

<p>The set of vertices of $Q(d,n)$ is <code>$\{0,1,\ldots,n-1\}^d$</code> and every edge is formed by all vertices having $d-1$ coordinates fixed and the last one getting all possible values (so it has $dn^{d-1}$ edges).</p> <p>I'm trying to prove that $Q(n,n)$ has the following property: if $S$ is some subset of its edges and $U$ is their union, then $|S|\leq\frac{|U|\log|U|}{n\log n}$. I'm sure that's true, extreme cases (when the inequality becomes an equality) being those when $U$ is a hypercube of lesser dimension and $S$ consists of all edges in $U$, but I don't know how to approach the proof. Could you give any hints?</p>

http://mathoverflow.net/questions/129407/random-graphs-nonisomorphic-to-unit-distance-graphs/129457#129457 tempestadept 2013-05-04T19:24:20Z 2013-05-04T19:24:20Z

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

http://mathoverflow.net/questions/129407/random-graphs-nonisomorphic-to-unit-distance-graphs tempestadept 2013-05-02T17:30:27Z 2013-05-02T17:30:27Z

@Brendan McKay, No @Wlodzimierz Holsztynski, $V(G)\subset\mathbb{R}^2$, $E(G)=\{(v,w)|d(v,w)=1\}$. $d$ is euclidean distance.