Algebraic formulation of Hadwiger-Nelson problem: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
Created page with "''This is a part of Polymath16 - for the main page, see Hadwiger-Nelson problem.''" |
No edit summary |
||
| Line 1: | Line 1: | ||
''This is a part of Polymath16 - for the main page, see [[Hadwiger-Nelson problem]].'' | ''This is a part of Polymath16 - for the main page, see [[Hadwiger-Nelson problem]].'' | ||
Given a [https://en.wikipedia.org/wiki/Unit_distance_graph unit distance graph] <math>G</math>, the edges of the graph are formed by a set of vectors <math>V</math> of unit length. Often a single vector is used many times in the same graph for different edges. The vectors generate an infinite group <math>\mathcal{G}</math> under addition. The [https://en.wikipedia.org/wiki/Cayley_graph Cayley graph] <math>\Gamma(\mathcal{G},S)</math> is a unit distance graph that will contain <math>G</math> as a subgraph. A colouring of the Cayley graph reduces to a colouring of <math>G</math>, and is an efficient way to set an upper bound on its [https://en.wikipedia.org/wiki/Graph_coloring chromatic number]. | |||
Revision as of 03:29, 7 May 2018
This is a part of Polymath16 - for the main page, see Hadwiger-Nelson problem.
Given a unit distance graph [math]\displaystyle{ G }[/math], the edges of the graph are formed by a set of vectors [math]\displaystyle{ V }[/math] of unit length. Often a single vector is used many times in the same graph for different edges. The vectors generate an infinite group [math]\displaystyle{ \mathcal{G} }[/math] under addition. The Cayley graph [math]\displaystyle{ \Gamma(\mathcal{G},S) }[/math] is a unit distance graph that will contain [math]\displaystyle{ G }[/math] as a subgraph. A colouring of the Cayley graph reduces to a colouring of [math]\displaystyle{ G }[/math], and is an efficient way to set an upper bound on its chromatic number.
