User puzzly - MathOverflow

Distribution of random vectors

2012-09-30T19:25:53Z

Two positive numbers $\alpha$ and $\beta$ are given. We are going to describe a process of choosing a random vector on the unit sphere $S$ in $\mathbb R^3$ (given by $x^2+y^2+z^2=1$).

A vector $u\in S$ is chosen uniformly at random in the spherical disc with center $(0,0,1)$ and radius $\alpha$ on the sphere. After that a vector $v\in S$ is chosen uniformly at random on the spherical circle with center $u$ and radius $\beta$.

Can we describe the distribution of $v$ on the sphere (e.g., by specifying its density function or otherwise)? Clearly, $v$ lies in the spherical disc around $(0,0,1)$ of radius $\alpha+\beta$, however its distribution doesn't seem to be uniform. Can we estimate somehow the most frequent angle that $v$ subtends with $(0,0,1)$? The answer should certainly depend on $\alpha$ and $\beta$.

(By a "spherical disc" with center $c$ and radius $r$ we understand the set of points on the sphere whose distance from $c$ is at most $r$. Similarly, a "spherical circle" with center $c$ and radius $r$ is the set of points on the sphere whose distance from $c$ is exactly $r$.)

This question arouse related to the distribution of the polarization vector in a randomly grained polycrystalline material (ceramics).

Small 4-chromatic coin graphs

2012-04-02T10:10:18Z

A coin graph is a graph that can be represented by a set of disjoint, except possibly touching, unit disks in the plane (i.e. the disks are the vertices and the edges correspond to the pairs that touch each other). It's easy to show by induction that $\chi(G)\leq4$ for every coin graph $G$, as there's always a vertex of degree at most 3.

My question is: what is the smallest order (i.e. the number of vertices) of a 4-chromatic coin graph?

In this paper by Erdos http://www.renyi.hu/~p_erdos/1987-27.pdf there is a coin graph of order 19 that is 4-chromatic (see Figure 1) by I doubt it's the smallest one (it was constructed for a different purpose, having to do with the independence number). The question I asked was proposed for an IMO competition in 1979, see p. 138 question 73 in Djukic, Jankovic, Matic, Petrovic: the IMO Compendium (there is no solution there, however).

Clearly, coin graphs are also unit distance graphs, for the definition see http://en.wikipedia.org/wiki/Unit_distance_graph. The smallest 4-chromatic unit-distance graph is probably the Moser spindle http://en.wikipedia.org/wiki/Moser_spindle that has 7 vertices. There is a similar notion of matchstick graphs: those are unit distance graphs drawn in the plane with non-crossing straight-line segments, see http://en.wikipedia.org/wiki/Matchstick_graph Note that the Moser spindle is NOT a matchstick graph, although it's planar and unit-distance.

The second (related) question is: what is the smallest order of a 4-chromatic matchstick graph?

I think the answer (to the second question) is 8.

Comment by puzzly

2012-04-03T12:58:35Z

great, sounds convincing enough, except that i don't see (at least not without a bit of geometry) how |V(G)-V(C)|\geq 2 implies |V(C)|\geq 8. did u have in mind a trivial way to see that?

Comment by puzzly

2012-04-02T12:22:53Z

if i understand correctly, your second construction is a matchstick graph, but not a coin graph, right?