coloring problem

mono trio: three collinear points spaced out by distance 1, all with the same color (wrt some coloring)

A cool question: Fix \(t\in [5]\). - can you color \(\mathbb{R}^2\) with \(t\) colors and avoid mono trios?

Turns out: There is a \(3\) coloring based on a plane tiling with hexagons + do weird stuff to the boundaries (appropriately assign them) that avoids mono trios!

A special class of colorings: “circly” colorings: all points at a fixed distance from the origin have the same color.

Question: is there some nice color reduction thing that you can do in higher dimensions?

Anyways, let’s think about circly colorings a bit.

It turns out we get the following formulas:

If you have a circle of radius \(r\), then the following two other circles must have different colors: - \[r\mapsto \sqrt{r^{2}+2}\] - \[r\mapsto \sqrt{r^{2}-1}\] (note that your circle must have \(r\ge 1\) to apply this rule)

If you have circles of radii \(a,b\) of the same color, then we find a circle of this radius that must have a different color: - \[a,b \mapsto \sqrt{\frac{a^{2}+b^{2}}{2} - 1}\] - \[a,b \mapsto \sqrt{2b^{2}-a^{2}- 1}\]

Using these rules with the seed that \(0,1\) are different colors, it’s pretty easy to show that any circly two coloring of \(\mathbb{R}^2\) has a mono trio.

Ok, but three colors? This is tricky. You could try to make an algorithm that - repeatedly applies these rules - by doing so you generate some graph - then you need to check if that graph is \(3\)-colorable - if the graph ever ends up having chromatic number at least \(4\) then we have found out that it is impossible to avoid mono trio in a \(3\) coloring - in fact, this would kind of work generally. we just converted this into a graph problem from a geometry problem.

• caveat! you can’t just start from a single seed, e.g., the origin, and generate everything

• because many irrational things live in different universes that you would never explore within your tame square-roots of finite binary decimal universe.

• so you must branch all the universes.

• oops its too much. will probably explode your computer. unless quantum.

question: does this algorithm terminate in <5 minutes?

3 coloring

But now, maybe a question you could ask is “what graphs are 3-colorable.”

well, here’s an easier question: In an Erdos-Renyi graph with parameter \(p\) what is the probability that it is \(K_4\) free? Or really, what value of \(p\) makes this probability constant?

Expected number of \(K_4\)’s is a good indicator, especially because variance is likely quite small. And the expected number is \(\Theta(p^{6} n^{4})\). So this would be \(p=\frac{1}{n^{\frac{2}{3}}}\) to get \(\Theta(1)\) probability probably probabbly of \(K_4\) or no \(K_4\). probably didnt actually calculate variance plz forgive.

But now back to some harder questions.

question: if \(p=100/n\) then how likely is it to be \(3\)-colorable? Maybe feels good because it is locally looking like trees?

question: what is relationship between max-degree and chromatic number?

observation: the \(p=\frac{100}{n}\) dude has \(O(1)\) triangles in expectation.

question: does this help us with \(3\)-coloring-ness?

question: is there a relationship between average degree and chromatic number?

question: what if instead you were looking for trios where you didn’t enforce colinearity? or you enforced some other geometrical condition?