After nearly five years, it’s time to roll over the discussion. Aubrey’s most recent comment in the previous thread seems interesting. I’m reproducing it here for convenience:
In the course of discussing Asger’s graph (see above) and the one I found shortly afterwards, a new conjecture has arisen:
For all d >= 2 and 3 <= n <= d+2, there exists a (d+n-1)-chromatic unit-distance graph in R^d that does not contain any n-simplex.
Since there cannot be a simplex in R^d of size greater than d+1, this covers all meaningful cases.
The conjecture is interesting because there are only finitely many (d,n} for which it is not already known to be true. That’s because several years ago, Andrei Raigorodskii proved an exponential lower bound that is analogous to his famous one, but in which the vertices lie on a sphere. The key utility of his result from the perspective of this conjecture is that the sphere can have any radius > 1/2, so in particular it can have a radius < 1/Sqrt[3], on which any UDG must clearly be triangle-free.
But starting from d = 2 (i.e. the plane), it is worth enumerating what is known. In the plane, the conjecture is proven for both relevant values of n (namely 3 and 4), because we have 5-chromatic UDGs and we also have 4-chromatic triangle-free UDGs. In R^3, the recent papers by Asger and myself deal with the cases n=3 and n=4, leaving only n=5, i.e. the non-discovery of a 7-chromatic UDG of any kind.
In higher dimensions, however, there seems to have been no exploration of UDGs restricted by simplex size. All we have is the unrestricted cases (those with n = d+2). The situation there seems to be that, other than the d=3 case just mentioned, only three dimensions (d = 5, 6 and 8) are lacking, because the highest chromatic numbers known in those dimensions are 9, 12 and 16 as against the desired 11, 13 and 17. Above d=8 we already have graphs with chromatic number at least 2d+1 through d = 18, which is well into the territory where Andrei’s famous exponential lower bound does the job.
As of now, preliminary discussions have involved only Asger, myself, Andrei, his former PhD student Oleg Rubanov (who found a large graph satisfying {d,n} = {3,3} during his doctoral studies, and Vsevolod Voronov, who (among other VERY cool results) found two 5-chromatic UDGs on S^2, which have radii less than 1 and thus deliver 7-chromatic UDGs in R^4 by spindling of bi-pyramids. Dan Ismailescu and Geoffrey Exoo, who found a lot of the best known cases in small dimensions, are also joining in. We have decided to bring the discussion here so as to involve others. Let’s do this!
consisting of
and 
,
,
, and
.
denote the set of matrices 
such that
denotes conjugate transpose, 
denotes entrywise squared modulus, 
denotes the 
identity matrix, and 
denotes the 
of size 
.
Short, Fat Matrices 