Talk:Unit distance graph

For the Hamming (3,3) graph, the vertical coordinates are roots of polynomial 3 x^6 - 9 x^4 + 6 x^2 - 1 = 0. Use the 6th, 5th, and negative 4th roots, for approximate values {1.4619, 0.777862, -0.507713}. EdPeggJr (talk) 22:11, 26 October 2016 (UTC)

GA Review

This review is transcluded from Talk:Unit distance graph/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Ovinus (talk · contribs) 01:09, 24 November 2022 (UTC)

Will do over the next week or so. Ovinus (talk) 01:09, 24 November 2022 (UTC)

GA review (see here for what the criteria are, and here for what they are not)

1. It is reasonably well written.

   a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists):

2. It is factually accurate and verifiable.

   a (reference section): b (citations to reliable sources): c (OR): d (copyvio and plagiarism):

3. It is broad in its coverage.

   a (major aspects): b (focused):

4. It follows the neutral point of view policy.

   Fair representation without bias:

5. It is stable.

   No edit wars, etc.:

6. It is illustrated by images and other media, where possible and appropriate.

   a (images are tagged and non-free content have non-free use rationales): b (appropriate use with suitable captions):

7. Overall:

   Pass/Fail:

Comments

• "unit distance graph with two vertices that must be that distance apart" This is somewhat subtle, so maybe add something like, "regardless of how it is realized/drawn" Ovinus (talk) 01:09, 24 November 2022 (UTC)

  In the lead? I tend to think of that as the place for stating in rough and intuitive terms results whose details are spelled out later. Here, "later" is the first sentence of the "Algebraic numbers and rigidity" section. —David Eppstein (talk) 06:37, 25 November 2022 (UTC)

  Fair

• State somewhere that any supergraph of a non-unit-distance graph is also not a unit distance graph. Obvious, but if sourceable, I think reasonable because the reader can extrapolate their own examples of non-unit-distance graphs. Ovinus (talk) 23:32, 24 November 2022 (UTC)

  This was already more or less implicit in the "Forbidden subgraphs" section but I rewrote that section in an attempt to make the same idea more explicit. —David Eppstein (talk) 07:06, 25 November 2022 (UTC)

• "however, the same is not true for other common graph products" – such as? Ovinus (talk) 23:32, 24 November 2022 (UTC)

  Such as the strong product of graphs. Added. I need to expand that article; there has been a lot of interest in strong products in graph structure theory recently. —David Eppstein (talk) 07:09, 25 November 2022 (UTC)

• Is the wheel graph minus a radial edge minimal? Also, I'll make a picture Ovinus (talk) 23:32, 24 November 2022 (UTC)

  Yes, it's easy to see that removing any more edges from it gives it enough flexibility to avoid the non-adjacent unit-distance pair. Our source for it being not strictly unit distance doesn't seem to say so explicitly. —David Eppstein (talk) 07:15, 25 November 2022 (UTC)

  That is clear, but what I meant was, do all six-vertex graphs (and/or all non-isomorphic seven-vertex graphs) not have this property? Ovinus (talk) 08:24, 25 November 2022 (UTC)

  Oh. No. The source gives a different six-vertex example, a triangular prism minus one of the triangle edges. —David Eppstein (talk) 08:26, 25 November 2022 (UTC)

  Interesting. And five vertices is always possible? Ovinus (talk) 22:10, 25 November 2022 (UTC)

  Well, except if it contains K4 or K2,3 as a subgraph. Five vertices is too few to produce examples that are non-strict unit distance graphs but not strict unit distance graphs. —David Eppstein (talk) 22:30, 25 November 2022 (UTC)

  Ah. Maybe add that six vertices is the fewest such so that a graph is a subgraph of a unit distance graph but not strictly one? Ovinus (talk) 04:03, 26 November 2022 (UTC)

• "for a constant c" – did Erdos find an explicit c? Ovinus (talk) 23:32, 24 November 2022 (UTC)

  No, and neither does the other early reference on this problem, Spencer, Szemerédi, and Trotter, "Unit distances in the Euclidean plane".

  If you hit the problem with a big hammer you can see fairly easily that grid points with a carefully chosen spacing have this many unit distances. It's easier to use integer grid points and then choose some distance $d$ that occurs frequently. In particular, if $d$ is a product of $k$ distinct primes congruent to 1 modulo 4 then a circle of radius $d$ centered at the origin in the integer grid will pass through a number of grid points proportional to $2^{k}$, by the sum of two squares theorem. Now choose $d$ proportional to but somewhat smaller than ${\sqrt {n}}$ so that you can pack linearly many of these dense circles into a ${\sqrt {n}}\times {\sqrt {n}}$ grid (one centered at each grid point). Using the prime number theorem (or rather the form of it for primes congruent to 1 mod 4) shows that, when you multiply together the $k$ smallest primes, you get a number whose logarithm is proportional to $k\log k$, and you want it to be around ${\tfrac {1}{2}}\log n$, so $k$ is proportional to $\log n/\log \log n$. The only remaining step is to observe that, for this choice of $k$, $2^{k}\approx n^{c/\log \log n}$ for some $c$.

  But if you want to know what $c$ is then you have to do all this much more carefully to work out the best tradeoff for $d$ versus ${\sqrt {n}}$, figure out how far off from its optimal value $d$ will be coming from the fact that it comes from a quickly growing sequence [1] that might not be as close to ${\sqrt {n}}$ as you'd like, calculate how many unit distances you get for the partial circles whose center is too close to the edge of the grid, figure out how the constant of proportionality in the prime number theorem affects $c$, check whether maybe using prime powers instead of just primes helps, etc. Erdős says none of this but I think he would have expected his audience to know all this. I think also that neither he nor S S & T took the effort to work it out in detail because they saw it as just a calculation and not a nontrivial new result worthy of their effort. —David Eppstein (talk) 07:56, 25 November 2022 (UTC)

  Fascinating. I would have thought an improvement from the trivial linear bound would be much trickier, but I guess it makes sense since some numbers form many more Pythagorean triples. What happens if you choose a different lattice, or perhaps superimposed multiple square lattices? Ovinus (talk) 22:10, 25 November 2022 (UTC)

  Something similar will work for the equilateral triangle lattice but then I guess you need to use Eisenstein primes instead of Gaussian primes. I have no idea whether that makes a difference to the exponent. Overlaying lattices doesn't seem likely to be a good idea; then you would only get the sum of the numbers of distances in the separate lattices rather than getting any kind of better-than-linear synergy. —David Eppstein (talk) 22:33, 25 November 2022 (UTC)

• "For small values of n – up to? Ovinus (talk) 23:32, 24 November 2022 (UTC)

  Added. —David Eppstein (talk) 08:13, 25 November 2022 (UTC)

• Is the set of forbidden subgraphs (for either type of hereditary family) known to be finite? Ovinus (talk) 23:32, 24 November 2022 (UTC)

  Globus & Parshall (2020) don't discuss the question, and I don't have access to the other source, Chilakamarri & Mahoney (1995), to determine whether they do. (That's why it's listed as "as cited by Globus & Parshall (2020)": to indicate that it's a source copied from another source rather than used directly.) —David Eppstein (talk) 08:17, 25 November 2022 (UTC)

• "every forbidden graph is a biconnected graph" Presumably you mean "minimal forbidden subgraph" or smth like that Ovinus (talk) 23:32, 24 November 2022 (UTC)

  I'm defining forbidden subgraphs to be the minimal ones, earlier. —David Eppstein (talk) 08:17, 25 November 2022 (UTC)

  Fair

• Would it be OR to call "subgraphs of unit distance graphs" simply "nonstrict", for clarity? Ovinus (talk) 23:32, 24 November 2022 (UTC)

  I think it's more WP:NEO than WP:OR that could be an issue, although that's more about titles of articles. I don't think the term is in use but it seems harmless and clear enough. Done. —David Eppstein (talk) 08:25, 25 November 2022 (UTC)

• "it is possible to find a unit distance graph" is the proof constructive? If so, I think "construct" is nicer Ovinus (talk) 23:32, 24 November 2022 (UTC)

  Ok, done. —David Eppstein (talk) 00:59, 26 November 2022 (UTC)

• "Any graph may be embedded as a set of points in a sufficiently high dimension" – this seems a bit strange, since presumably three dimensions is sufficient Ovinus (talk) 23:32, 24 November 2022 (UTC)

  Should have been "as a unit distance graph". Three dimensions is not sufficient; $K_{5}$ cannot be embedded as a unit distance graph in 3d. —David Eppstein (talk) 01:00, 26 November 2022 (UTC)

  Yep, makes sense

• "so that the edges are exactly the unit distance pairs" – necessary clarification? Ovinus (talk) 23:32, 24 November 2022 (UTC)

  This is just the strict vs non-strict distinction again. Rewrote to attempt to clarify this. —David Eppstein (talk) 01:02, 26 November 2022 (UTC)

• Does the Matousek method work in higher dimensions? Ovinus (talk) 23:32, 24 November 2022 (UTC)

  That time bound is very specific to 2d, and to the fact that 2d unit distance graphs cannot be dense. I would imagine that there is some kind of subquadratic algorithm in 3d, coming from the subquadratic bound on the number of edges in 3d. In four or more dimensions you can get dense graphs so there is no hope of anything faster than $O(n^{2})$, and $O(n^{2})$ time is trivial. —David Eppstein (talk) 01:06, 26 November 2022 (UTC)

  Gotcha. Since you just talked about higher-dimensional examples of the problem, I'd mention that the algorithm is specific to 2D. Ovinus (talk) 04:03, 26 November 2022 (UTC)

• "to test whether a given graph is a subgraph of a unit distance graph, or is a strict unit distance graph" – Ambiguity: do you mean that it's NP-hard for both the strict and nonstrict versions of the problem, or that it's NP-hard for the single problem of finding whether it's a strict and/or nonstrict unit distance graph? Ovinus (talk) 23:32, 24 November 2022 (UTC)

  Both versions of the problem are hard. —David Eppstein (talk) 01:08, 26 November 2022 (UTC)

• Are (possible uncountably) infinite trees necessarily unit distance graphs? (e.g. [2] seems to prove it only for finite graphs) Ovinus (talk) 23:32, 24 November 2022 (UTC)

  Not always. For instance, a tree with one internal vertex and a larger number of leaves than the cardinality of the continuum is not a unit distance graph. The sentence saying trees are unit distance graphs should have qualified it as applying only to finite trees. Like a lot of material on graph theory, this article sometimes makes an implicit assumption that the graphs it is talking about are finite, but I have tried to make more of these (including the point about trees) explicit, especially because a couple of the points it makes are about infinite graphs. —David Eppstein (talk) 01:12, 26 November 2022 (UTC)

  Somehow didn't think of that; I imagine countable trees always work. In any case, yeah, I feel like this is a topic where being careful about finite vs. infinite is helpful. Ovinus (talk) 04:03, 26 November 2022 (UTC)

A pleasing read overall. Will probably do spotchecks this weekend. Ovinus (talk) 23:32, 24 November 2022 (UTC)

• Oh, also: do any sources mention the trivial case of the problem in $\mathbb {R} ^{1}$? Ovinus (talk) 19:23, 26 November 2022 (UTC)

  Not that I've found. There's some discussion of one-dimensional distance graphs in Soifer's book (section 46.3) as an example where the axioms of set theory make a big difference in the chromatic number, but these are not unit distance graphs. —David Eppstein (talk) 20:20, 27 November 2022 (UTC)

Spotchecks

(Relative to Special:Diff/1123850171)

• [1]: good
• [6]: can't access
• [7]: good
• [11]: good
• [13]: can't access
• [17]: good. Also, I'd specify that the constant of proportionality may be set to 1.94—that's really cool.
• [22]: Good (and an awesome paper)
• [24]: can't access
• [25]: Good; could we cite the paper itself, too?
• [27]: good
• [29]: good
• [31]: can't access
• [33]: Good. (The paper abstract has a typo, replacing the * in log* with a 4.)
• [35]: CiteSeerX link is broken for some reason, but from the abstract the citation seems kosher.

So just two (non-errors) to address. Ovinus (talk) 19:19, 26 November 2022 (UTC)

Ok, done. —David Eppstein (talk) 20:30, 27 November 2022 (UTC)

Lovely. There are a couple bits above (most importantly the Matousek algorithm being 2D only). I'll do a quick second pass of the article by Tuesday. Ovinus (talk) 21:05, 27 November 2022 (UTC)

Happy with the article. Passing; nice work. Ovinus (talk) 19:52, 30 November 2022 (UTC)