Excluding bichromatic vertices - Revision history

Domotorp: /* Conjecture for using bichromatic vertices to bound CNP */ added conjecture is true for lines

2018-08-24T12:18:32Z

Conjecture for using bichromatic vertices to bound CNP: added conjecture is true for lines

← Older revision		Revision as of 05:18, 24 August 2018
Line 55:		Line 55:
	'''Conjecture.''' In any non-monochromatic coloring of the plane with finitely many colors, we can find any such configuration.		'''Conjecture.''' In any non-monochromatic coloring of the plane with finitely many colors, we can find any such configuration.

	~~It might be easier to first prove the~~ respective conjecture for lines~~. This has also been posted on~~ [https://mathoverflow.net/questions/299616/bichromatic-pencils? MathOverflow here].		The respective conjecture for lines is true: [https://mathoverflow.net/questions/299616/bichromatic-pencils? MathOverflow here].


	[[Category:Polymath16]]		[[Category:Polymath16]]

Domotorp: /* Conjecture for using bichromatic vertices to bound CNP */ improved previous

2018-07-10T21:33:36Z

Conjecture for using bichromatic vertices to bound CNP: improved previous

← Older revision		Revision as of 14:33, 10 July 2018
Line 49:		Line 49:
	== Conjecture for using bichromatic vertices to bound CNP ==		== Conjecture for using bichromatic vertices to bound CNP ==

	~~This is a proposal of a way to prove that we can start with a similar assumption in case of non-measurable colorings, as for measurable ones. More precisely, suppose~~ that we have an (embedded) unit-distance graph <math>G</math> with a special vertex <math>v_0</math> that doesn’t admit a 4-coloring if <math>v_0</math> has two colors, i.e., none of its neighbors can be red or blue. We want to argue that in this case the chromatic number of the plane is at least 5.		Suppose that we have an (embedded) unit-distance graph <math>G</math> with a special vertex <math>v_0</math> that doesn’t admit a 4-coloring if <math>v_0</math> has two colors, i.e., none of its neighbors can be red or blue. We want to argue that in this case the chromatic number of the plane is at least 5.

	Denote the neighbors of <math>v_0</math> by <math>\Gamma_0</math>. Consider the <math>\|\Gamma_0\|</math> unit circles <math>\mathcal C</math> that are centered on the points <math>\Gamma_0</math> (these all go through <math>v_0</math>). We would like to show that for any good (i.e., without a monochromatic unit-distance) 4-coloring of the plane there is an isometric copy of <math>\mathcal C</math> such that the common points of the circle is, say red, and there is another color, say blue, that is present on all the circles. If we could find such a configuration, then we could just shift <math>G</math> appropriately so that the vertices <math>\Gamma_0</math> are mapped to the centers of the circles.		Denote the neighbors of <math>v_0</math> by <math>\Gamma_0</math>. Consider the <math>\|\Gamma_0\|</math> unit circles <math>\mathcal C</math> that are centered on the points <math>\Gamma_0</math> (these all go through <math>v_0</math>). We would like to show that for any good (i.e., without a monochromatic unit-distance) 4-coloring of the plane there is an isometric copy of <math>\mathcal C</math> such that the common points of the circle is, say red, and there is another color, say blue, that is present on all the circles. If we could find such a configuration, then we could just shift <math>G</math> appropriately so that the vertices <math>\Gamma_0</math> are mapped to the centers of the circles.

	It might be easier to first prove the respective ~~statement~~ for lines. This has been ~~also posed~~ on [https://mathoverflow.net/questions/299616/bichromatic-pencils? MathOverflow here].		'''Conjecture.''' In any non-monochromatic coloring of the plane with finitely many colors, we can find any such configuration.

			It might be easier to first prove the respective conjecture for lines. This has also been posted on [https://mathoverflow.net/questions/299616/bichromatic-pencils? MathOverflow here].


	[[Category:Polymath16]]		[[Category:Polymath16]]

Domotorp: added conjecture

2018-07-10T21:29:57Z

added conjecture

← Older revision		Revision as of 14:29, 10 July 2018
Line 34:		Line 34:

	Now suppose instead that <math>c_\eta \neq c_{\overline{\eta}}</math>, then <math>c_1</math> is distinct from either <math>c_\eta</math> or <math>c_{\overline{\eta}}</math>. Without loss of generality (conjugation symmetry) assume <math>c_\eta \neq c_1</math>. By item 5, each <math>(\eta - \overline{\eta} \omega) \omega^j</math> is connected both to <math>\eta \omega^j</math>, which has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta}\omega^{j+1}</math>, which has color <math>c_{\overline{\eta}}+2j</math>. Thus all of <math>(\eta - \overline{\eta} \omega) C_6</math> is 0,2-colored. Similarly, from items 6,7, each <math>\omega^j + \eta \omega^{j+2}</math> is connected to <math>\omega^j</math>, which has color <math>c_1 + 2j</math>, and <math>\eta \omega^{j+2}</math>, which has color <math>c_\eta + 2j</math>, and hence <math>(1 + \eta \omega^2) C_6</math> is also 0,2-colored. Now observe from items 4,5 that each <math> (\eta - \overline{\eta}) \omega^j</math> is the vertex of an equilateral triangle with other two vertices <math>\eta \omega^{j-1} - \overline{\eta} \omega^j</math>, <math> \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j</math> which are 0,2-colored and hence <math>(\eta - \overline{\eta}) C_6</math> is 1,3-colored, again giving the required contradiction. <math>\Box</math>		Now suppose instead that <math>c_\eta \neq c_{\overline{\eta}}</math>, then <math>c_1</math> is distinct from either <math>c_\eta</math> or <math>c_{\overline{\eta}}</math>. Without loss of generality (conjugation symmetry) assume <math>c_\eta \neq c_1</math>. By item 5, each <math>(\eta - \overline{\eta} \omega) \omega^j</math> is connected both to <math>\eta \omega^j</math>, which has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta}\omega^{j+1}</math>, which has color <math>c_{\overline{\eta}}+2j</math>. Thus all of <math>(\eta - \overline{\eta} \omega) C_6</math> is 0,2-colored. Similarly, from items 6,7, each <math>\omega^j + \eta \omega^{j+2}</math> is connected to <math>\omega^j</math>, which has color <math>c_1 + 2j</math>, and <math>\eta \omega^{j+2}</math>, which has color <math>c_\eta + 2j</math>, and hence <math>(1 + \eta \omega^2) C_6</math> is also 0,2-colored. Now observe from items 4,5 that each <math> (\eta - \overline{\eta}) \omega^j</math> is the vertex of an equilateral triangle with other two vertices <math>\eta \omega^{j-1} - \overline{\eta} \omega^j</math>, <math> \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j</math> which are 0,2-colored and hence <math>(\eta - \overline{\eta}) C_6</math> is 1,3-colored, again giving the required contradiction. <math>\Box</math>

			For an alternative proof (using another unit-distance graph), see [https://dustingmixon.wordpress.com/2018/05/10/polymath16-fifth-thread-human-verifiable-proofs/#comment-4438 here].

	== Using bichromatic vertices to bound MCNP ==		== Using bichromatic vertices to bound MCNP ==
Line 44:		Line 46:

	'''Proof''' Suppose for contradiction that we had a measurable 4-coloring <math>c</math> of the plane. For any natural number n, consider the set <math>\Delta_{1/n} = \{ v: c(v) \neq c(v+1/n) \}</math>. These sets are measurable, and their measure in any fixed bounded region tends to zero as <math>n \to \infty</math> (since translation is strongly continuous in say the <math>L^1</math> topology). Also these sets are non-empty, for instance since <math>c(0) \neq c(1)</math> the pigeonhole principle forces <math>\Delta_{1/n}</math> to have non-zero intersection with <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>. Let v_n be an element of <math>\Delta_{1/n}</math> in <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>, and let G be a finite unit distance graph containing the origin with the origin not bichromatic, such as the one provided by Theorem 1. By two applications of Lemma 2, we see that for any real numbers <math>\theta_1,\theta_2 \in [0,2\pi)</math>, there exist non-zero vertices <math>w_1,w_2</math> of G such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math>. By the pigeonhole principle, there thus exists non-zero vertices <math>w_1,w_2 \in G</math> and a set <math>\Omega_n \in [0,2\pi)^2</math> of Lebesgue measure at least <math>1/(\|G\|-1)^2</math> (where <math>\|G\|</math> denotes the number of vertices of G) such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math> for all <math>(\theta_1,\theta_2) \in \Omega_n</math>. Since the map <math>(\theta_1,\theta_2) \mapsto e^{i\theta_1} w_1 + e^{i\theta_2} w_2</math> does not depend on <math>n</math>, is at most two-to-one, and is an immersion outside of a measure zero set, we thus conclude that the measure of <math>\Delta_{1/n}</math> in the disk <math>D( 0, 1 + 2 \mathrm{diam}(G) )</math> is bounded away from zero uniformly in n, but this contradicts the strong continuity of translation. <math>\Box</math>		'''Proof''' Suppose for contradiction that we had a measurable 4-coloring <math>c</math> of the plane. For any natural number n, consider the set <math>\Delta_{1/n} = \{ v: c(v) \neq c(v+1/n) \}</math>. These sets are measurable, and their measure in any fixed bounded region tends to zero as <math>n \to \infty</math> (since translation is strongly continuous in say the <math>L^1</math> topology). Also these sets are non-empty, for instance since <math>c(0) \neq c(1)</math> the pigeonhole principle forces <math>\Delta_{1/n}</math> to have non-zero intersection with <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>. Let v_n be an element of <math>\Delta_{1/n}</math> in <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>, and let G be a finite unit distance graph containing the origin with the origin not bichromatic, such as the one provided by Theorem 1. By two applications of Lemma 2, we see that for any real numbers <math>\theta_1,\theta_2 \in [0,2\pi)</math>, there exist non-zero vertices <math>w_1,w_2</math> of G such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math>. By the pigeonhole principle, there thus exists non-zero vertices <math>w_1,w_2 \in G</math> and a set <math>\Omega_n \in [0,2\pi)^2</math> of Lebesgue measure at least <math>1/(\|G\|-1)^2</math> (where <math>\|G\|</math> denotes the number of vertices of G) such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math> for all <math>(\theta_1,\theta_2) \in \Omega_n</math>. Since the map <math>(\theta_1,\theta_2) \mapsto e^{i\theta_1} w_1 + e^{i\theta_2} w_2</math> does not depend on <math>n</math>, is at most two-to-one, and is an immersion outside of a measure zero set, we thus conclude that the measure of <math>\Delta_{1/n}</math> in the disk <math>D( 0, 1 + 2 \mathrm{diam}(G) )</math> is bounded away from zero uniformly in n, but this contradicts the strong continuity of translation. <math>\Box</math>

			== Conjecture for using bichromatic vertices to bound CNP ==

			This is a proposal of a way to prove that we can start with a similar assumption in case of non-measurable colorings, as for measurable ones. More precisely, suppose that we have an (embedded) unit-distance graph <math>G</math> with a special vertex <math>v_0</math> that doesn’t admit a 4-coloring if <math>v_0</math> has two colors, i.e., none of its neighbors can be red or blue. We want to argue that in this case the chromatic number of the plane is at least 5.

			Denote the neighbors of <math>v_0</math> by <math>\Gamma_0</math>. Consider the <math>\|\Gamma_0\|</math> unit circles <math>\mathcal C</math> that are centered on the points <math>\Gamma_0</math> (these all go through <math>v_0</math>). We would like to show that for any good (i.e., without a monochromatic unit-distance) 4-coloring of the plane there is an isometric copy of <math>\mathcal C</math> such that the common points of the circle is, say red, and there is another color, say blue, that is present on all the circles. If we could find such a configuration, then we could just shift <math>G</math> appropriately so that the vertices <math>\Gamma_0</math> are mapped to the centers of the circles.

			It might be easier to first prove the respective statement for lines. This has been also posed on [https://mathoverflow.net/questions/299616/bichromatic-pencils? MathOverflow here].


	[[Category:Polymath16]]		[[Category:Polymath16]]

Teorth: /* Using bichromatic vertices to bound MCNP */

2018-05-15T16:42:50Z

Using bichromatic vertices to bound MCNP

← Older revision		Revision as of 09:42, 15 May 2018
Line 43:		Line 43:
	'''Corollary 3''' The measurable chromatic number of the plane is at least 5.		'''Corollary 3''' The measurable chromatic number of the plane is at least 5.

	'''Proof''' Suppose for contradiction that we had a measurable 4-coloring <math>c</math> of the plane. For any natural number n, consider the set <math>\Delta_{1/n} = \{ v: c(v) \neq c(v+1/n) \}</math>. These sets are measurable, and their measure in any fixed bounded region tends to zero as <math>n \to \infty</math> (since translation is strongly continuous in say the <math>L^1</math> topology). Also these sets are non-empty, for instance since <math>c(0) \neq c(1)</math> the pigeonhole principle forces <math>\Delta_{1/n}</math> to have non-zero intersection with <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>. Let v_n be an element of <math>\Delta_{1/n}</math> in <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>, and let G be a finite unit distance graph containing the origin with the origin not bichromatic, such as the one provided by Theorem 1. By two applications of Lemma 2, we see that for any real numbers <math>\theta_1,\theta_2 \in [0,2\pi)</math>, there exist non-zero vertices <math>w_1,w_2</math> of G such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math>. By the pigeonhole principle, there thus exists non-zero vertices <math>w_1,w_2 \in G</math> and a set <math>\Omega_n \in [0,2\pi)^2</math> of Lebesgue measure at least <math>1/(\|G\|-1)^2</math> (where <math>\|G\|</math> denotes the number of vertices of G) such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math> for all <math>(\theta_1,\theta_2) \in \Omega_n</math>. Since the map <math>(\theta_1,\theta_2 \mapsto e^{i\theta_1} w_1 + e^{i\theta_2} w_2</math> is at two-to-one and is an immersion outside of a measure zero set, we thus conclude that the measure of <math>\Delta_{1/n}</math> in the disk <math>D( 0, 1 + 2 \mathrm{diam}(G) )</math> is bounded away from zero uniformly in n, but this contradicts the strong continuity of translation. <math>\Box</math>		'''Proof''' Suppose for contradiction that we had a measurable 4-coloring <math>c</math> of the plane. For any natural number n, consider the set <math>\Delta_{1/n} = \{ v: c(v) \neq c(v+1/n) \}</math>. These sets are measurable, and their measure in any fixed bounded region tends to zero as <math>n \to \infty</math> (since translation is strongly continuous in say the <math>L^1</math> topology). Also these sets are non-empty, for instance since <math>c(0) \neq c(1)</math> the pigeonhole principle forces <math>\Delta_{1/n}</math> to have non-zero intersection with <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>. Let v_n be an element of <math>\Delta_{1/n}</math> in <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>, and let G be a finite unit distance graph containing the origin with the origin not bichromatic, such as the one provided by Theorem 1. By two applications of Lemma 2, we see that for any real numbers <math>\theta_1,\theta_2 \in [0,2\pi)</math>, there exist non-zero vertices <math>w_1,w_2</math> of G such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math>. By the pigeonhole principle, there thus exists non-zero vertices <math>w_1,w_2 \in G</math> and a set <math>\Omega_n \in [0,2\pi)^2</math> of Lebesgue measure at least <math>1/(\|G\|-1)^2</math> (where <math>\|G\|</math> denotes the number of vertices of G) such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math> for all <math>(\theta_1,\theta_2) \in \Omega_n</math>. Since the map <math>(\theta_1,\theta_2) \mapsto e^{i\theta_1} w_1 + e^{i\theta_2} w_2</math> does not depend on <math>n</math>, is at most two-to-one, and is an immersion outside of a measure zero set, we thus conclude that the measure of <math>\Delta_{1/n}</math> in the disk <math>D( 0, 1 + 2 \mathrm{diam}(G) )</math> is bounded away from zero uniformly in n, but this contradicts the strong continuity of translation. <math>\Box</math>

	[[Category:Polymath16]]		[[Category:Polymath16]]

Teorth at 16:09, 15 May 2018

2018-05-15T16:09:55Z

← Older revision		Revision as of 09:09, 15 May 2018
Line 35:		Line 35:
	Now suppose instead that <math>c_\eta \neq c_{\overline{\eta}}</math>, then <math>c_1</math> is distinct from either <math>c_\eta</math> or <math>c_{\overline{\eta}}</math>. Without loss of generality (conjugation symmetry) assume <math>c_\eta \neq c_1</math>. By item 5, each <math>(\eta - \overline{\eta} \omega) \omega^j</math> is connected both to <math>\eta \omega^j</math>, which has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta}\omega^{j+1}</math>, which has color <math>c_{\overline{\eta}}+2j</math>. Thus all of <math>(\eta - \overline{\eta} \omega) C_6</math> is 0,2-colored. Similarly, from items 6,7, each <math>\omega^j + \eta \omega^{j+2}</math> is connected to <math>\omega^j</math>, which has color <math>c_1 + 2j</math>, and <math>\eta \omega^{j+2}</math>, which has color <math>c_\eta + 2j</math>, and hence <math>(1 + \eta \omega^2) C_6</math> is also 0,2-colored. Now observe from items 4,5 that each <math> (\eta - \overline{\eta}) \omega^j</math> is the vertex of an equilateral triangle with other two vertices <math>\eta \omega^{j-1} - \overline{\eta} \omega^j</math>, <math> \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j</math> which are 0,2-colored and hence <math>(\eta - \overline{\eta}) C_6</math> is 1,3-colored, again giving the required contradiction. <math>\Box</math>		Now suppose instead that <math>c_\eta \neq c_{\overline{\eta}}</math>, then <math>c_1</math> is distinct from either <math>c_\eta</math> or <math>c_{\overline{\eta}}</math>. Without loss of generality (conjugation symmetry) assume <math>c_\eta \neq c_1</math>. By item 5, each <math>(\eta - \overline{\eta} \omega) \omega^j</math> is connected both to <math>\eta \omega^j</math>, which has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta}\omega^{j+1}</math>, which has color <math>c_{\overline{\eta}}+2j</math>. Thus all of <math>(\eta - \overline{\eta} \omega) C_6</math> is 0,2-colored. Similarly, from items 6,7, each <math>\omega^j + \eta \omega^{j+2}</math> is connected to <math>\omega^j</math>, which has color <math>c_1 + 2j</math>, and <math>\eta \omega^{j+2}</math>, which has color <math>c_\eta + 2j</math>, and hence <math>(1 + \eta \omega^2) C_6</math> is also 0,2-colored. Now observe from items 4,5 that each <math> (\eta - \overline{\eta}) \omega^j</math> is the vertex of an equilateral triangle with other two vertices <math>\eta \omega^{j-1} - \overline{\eta} \omega^j</math>, <math> \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j</math> which are 0,2-colored and hence <math>(\eta - \overline{\eta}) C_6</math> is 1,3-colored, again giving the required contradiction. <math>\Box</math>

			== Using bichromatic vertices to bound MCNP ==

			'''Lemma 2''' Let G be a unit distance graph containing the origin such that the origin is not bichromatic. For any 4-coloring <math>c</math> of the plane, and any non-zero complex number <math>z</math>, let <math>\Delta_z</math> denote the set of all complex numbers <math>v</math> such that <math>c(v) \neq c(v+z)</math>. Then for any <math>\theta \in {\bf R}</math> and <math>v \in \Delta_z</math>, there exists a non-zero vertex <math>w</math> of G such that <math>v + e^{i\theta} w \in \Delta_z</math>.

			'''Proof''' Suppose not, thus there exists <math>\theta \in {\bf R}, v \in \Delta_z</math> such that <math>v + e^{i\theta} w \not \in \Delta_z</math> for all non-zero vertices w of G. Then we can 4-color G by giving non-zero vertices w the color of <math>c(v + e^{i\theta} w) = c(v + e^{i\theta} w + z)</math> and giving the origin the two colors <math>c(v) \neq c(v+z)</math>. But this contradicts the hypothesis that the origin is not bichromatic. <math>\Box</math>

			'''Corollary 3''' The measurable chromatic number of the plane is at least 5.

			'''Proof''' Suppose for contradiction that we had a measurable 4-coloring <math>c</math> of the plane. For any natural number n, consider the set <math>\Delta_{1/n} = \{ v: c(v) \neq c(v+1/n) \}</math>. These sets are measurable, and their measure in any fixed bounded region tends to zero as <math>n \to \infty</math> (since translation is strongly continuous in say the <math>L^1</math> topology). Also these sets are non-empty, for instance since <math>c(0) \neq c(1)</math> the pigeonhole principle forces <math>\Delta_{1/n}</math> to have non-zero intersection with <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>. Let v_n be an element of <math>\Delta_{1/n}</math> in <math>\{0, 1/n, 2/n, \dots, (n-1)/n \}</math>, and let G be a finite unit distance graph containing the origin with the origin not bichromatic, such as the one provided by Theorem 1. By two applications of Lemma 2, we see that for any real numbers <math>\theta_1,\theta_2 \in [0,2\pi)</math>, there exist non-zero vertices <math>w_1,w_2</math> of G such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math>. By the pigeonhole principle, there thus exists non-zero vertices <math>w_1,w_2 \in G</math> and a set <math>\Omega_n \in [0,2\pi)^2</math> of Lebesgue measure at least <math>1/(\|G\|-1)^2</math> (where <math>\|G\|</math> denotes the number of vertices of G) such that <math>v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n}</math> for all <math>(\theta_1,\theta_2) \in \Omega_n</math>. Since the map <math>(\theta_1,\theta_2 \mapsto e^{i\theta_1} w_1 + e^{i\theta_2} w_2</math> is at two-to-one and is an immersion outside of a measure zero set, we thus conclude that the measure of <math>\Delta_{1/n}</math> in the disk <math>D( 0, 1 + 2 \mathrm{diam}(G) )</math> is bounded away from zero uniformly in n, but this contradicts the strong continuity of translation. <math>\Box</math>

	[[Category:Polymath16]]		[[Category:Polymath16]]

Pgibbs: missing bracket

2018-05-11T18:42:35Z

missing bracket

← Older revision		Revision as of 11:42, 11 May 2018
Line 16:		Line 16:
	:<math> \overline{\eta - \overline{\eta}} = (\eta - \overline{\eta}) \omega^3 </math>		:<math> \overline{\eta - \overline{\eta}} = (\eta - \overline{\eta}) \omega^3 </math>
	:<math> \overline{\eta - \omega \overline{\eta}} = (\eta - \omega \overline{\eta}) \omega^2 </math>		:<math> \overline{\eta - \omega \overline{\eta}} = (\eta - \omega \overline{\eta}) \omega^2 </math>
	we also see that <math>(\eta - \overline{\eta}) C_6</math>, <math>(\eta - \overline{\eta}\omega C_6</math> are conjugation invariant, while <math>\eta C_6</math> is conjugate to <math> \overline{\eta} C_6</math> and <math>(1+\eta \omega^2 ) C_6</math> is conjugate to <math>(1 + \overline{\eta \omega^2 }) C_6</math>.		we also see that <math>(\eta - \overline{\eta}) C_6</math>, <math>(\eta - \overline{\eta}\omega) C_6</math> are conjugation invariant, while <math>\eta C_6</math> is conjugate to <math> \overline{\eta} C_6</math> and <math>(1+\eta \omega^2 ) C_6</math> is conjugate to <math>(1 + \overline{\eta \omega^2 }) C_6</math>.

	We observe the following unit edges:		We observe the following unit edges:

Teorth at 21:51, 10 May 2018

2018-05-10T21:51:27Z

← Older revision		Revision as of 14:51, 10 May 2018
Line 7:		Line 7:
	Let <math>\omega := \exp( i \pi/3)</math> be the sixth root of vector, then we have the identities		Let <math>\omega := \exp( i \pi/3)</math> be the sixth root of vector, then we have the identities
	:<math> \omega^6 = 1; \quad \omega^3 = -1; \quad \omega^2 = \omega - 1. \quad (1)</math>		:<math> \omega^6 = 1; \quad \omega^3 = -1; \quad \omega^2 = \omega - 1. \quad (1)</math>
	Let <math>\eta := \exp( \frac{i}{2} \arccos(\frac{5}{6}),</math> then <math>\eta</math> is a unit vector that obeys the identity		Let <math>\eta := \exp( \frac{i}{2} \arccos(\frac{5}{6})),</math> then <math>\eta</math> is a unit vector that obeys the identity
	:<math> \eta (\omega + \omega^2) - \overline{\eta} (\omega + \omega^2)+ 1 = 0 \quad (2).</math>		:<math> \eta (\omega + \omega^2) - \overline{\eta} (\omega + \omega^2)+ 1 = 0 \quad (2).</math>
	Let		Let

Teorth at 19:56, 10 May 2018

2018-05-10T19:56:04Z

← Older revision		Revision as of 12:56, 10 May 2018
Line 1:		Line 1:
	'''Theorem 1''' A 4-coloring of the unit plane cannot contain a bichromatic vertex (a vertex that can be colored in either of two colors while keeping the color of all other vertices fixed).		'''Theorem 1''' A 4-coloring of the unit plane cannot contain a bichromatic vertex (a vertex that can be colored in either of two colors while keeping the color of all other vertices fixed).

			Equivalently, in a 4-coloring of the plane, the color of each vertex is determined uniquely by the colors of all the other vertices. This also gives an alternate proof of Falconer's result that the measurable chromatic number of the plane is at least five.

	'''Proof''' Without loss of generality we may assume that the colors are <math>{\bf Z}/4{\bf Z}</math> and that the origin is bichromatic with colors 0,2.		'''Proof''' Without loss of generality we may assume that the colors are <math>{\bf Z}/4{\bf Z}</math> and that the origin is bichromatic with colors 0,2.

Teorth at 19:54, 10 May 2018

2018-05-10T19:54:59Z

← Older revision		Revision as of 12:54, 10 May 2018
Line 31:		Line 31:
	Suppose first that <math>c_\eta = c_{\overline{\eta}}</math>. By item 4, each <math>(\eta - \overline{\eta})\omega^j</math> is connected both to <math> \eta \omega^j</math> that has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta} \omega^j</math> that has color <math>c_{\overline{\eta}} + 2j + 2</math>. Thus <math>(\eta - \overline{\eta})\omega^j</math> has to be colored 0 or 2, giving the 2-coloring of <math>(\eta - \overline{\eta}) C_6</math>.		Suppose first that <math>c_\eta = c_{\overline{\eta}}</math>. By item 4, each <math>(\eta - \overline{\eta})\omega^j</math> is connected both to <math> \eta \omega^j</math> that has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta} \omega^j</math> that has color <math>c_{\overline{\eta}} + 2j + 2</math>. Thus <math>(\eta - \overline{\eta})\omega^j</math> has to be colored 0 or 2, giving the 2-coloring of <math>(\eta - \overline{\eta}) C_6</math>.

	Now suppose instead that <math>c_\eta \neq c_{\overline{\eta}}</math>, then <math>c_1</math> is distinct from either <math>c_\eta</math> or <math>c_{\overline{\eta}}</math>. Without loss of generality (conjugation symmetry) assume <math>c_\eta \neq c_1</math>. By item 5, each <math>(\eta - \overline{\eta} \omega) \omega^j</math> is connected both to <math>\eta \omega^j<math>, which has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta}\omega^{j+1}</math>, which has color <math>c_{\overline{\eta}}+2j</math>. Thus all of <math>(\eta - \overline{\eta} \omega) C_6</math> is 0,2-colored. Similarly, from items 6,7, each <math>\omega^j + \eta \omega^{j+2}</math> is connected to <math>\omega^j</math>, which has color <math>c_1 + 2j</math>, and <math>\eta \omega^{j+2}</math>, which has color <math>c_\eta + 2j</math>, and hence <math>(1 + \eta \omega^2) C_6</math> is also 0,2-colored. Now observe from items 4,5 that each <math> (\eta - \overline{\eta}) \omega^j</math> is the vertex of an equilateral triangle with other two vertices <math>\eta \omega^{j-1} - \overline{\eta} \omega^j</math>, <math> \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j<\math> which are 0,2-colored and hence <math>(\eta - \overline{\eta}) C_6</math> is 1,3-colored, again giving the required contradiction. <math>\Box</math>		Now suppose instead that <math>c_\eta \neq c_{\overline{\eta}}</math>, then <math>c_1</math> is distinct from either <math>c_\eta</math> or <math>c_{\overline{\eta}}</math>. Without loss of generality (conjugation symmetry) assume <math>c_\eta \neq c_1</math>. By item 5, each <math>(\eta - \overline{\eta} \omega) \omega^j</math> is connected both to <math>\eta \omega^j</math>, which has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta}\omega^{j+1}</math>, which has color <math>c_{\overline{\eta}}+2j</math>. Thus all of <math>(\eta - \overline{\eta} \omega) C_6</math> is 0,2-colored. Similarly, from items 6,7, each <math>\omega^j + \eta \omega^{j+2}</math> is connected to <math>\omega^j</math>, which has color <math>c_1 + 2j</math>, and <math>\eta \omega^{j+2}</math>, which has color <math>c_\eta + 2j</math>, and hence <math>(1 + \eta \omega^2) C_6</math> is also 0,2-colored. Now observe from items 4,5 that each <math> (\eta - \overline{\eta}) \omega^j</math> is the vertex of an equilateral triangle with other two vertices <math>\eta \omega^{j-1} - \overline{\eta} \omega^j</math>, <math> \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j</math> which are 0,2-colored and hence <math>(\eta - \overline{\eta}) C_6</math> is 1,3-colored, again giving the required contradiction. <math>\Box</math>


	[[Category:Polymath16]]		[[Category:Polymath16]]

Teorth at 19:54, 10 May 2018

2018-05-10T19:54:20Z

← Older revision		Revision as of 12:54, 10 May 2018
Line 19:		Line 19:
	# Within <math>C_6</math>, there is a unit edge from any <math>\omega^j \in C_6</math> to the origin, to <math>\omega^{j+1} \in C_6</math>, and <math>\omega^{j-1} \in C_6</math>.		# Within <math>C_6</math>, there is a unit edge from any <math>\omega^j \in C_6</math> to the origin, to <math>\omega^{j+1} \in C_6</math>, and <math>\omega^{j-1} \in C_6</math>.
	# Within <math> \eta C_6</math>, there is a unit edge from any <math>\eta \omega^j \in C_6</math> to the origin, to <math>\eta \omega^{j+1} \in \eta C_6</math>, and <math>\eta \omega^{j-1} \in \eta C_6</math>. Similarly with <math>\eta</math> replaced by <math>\overline{\eta}</math>.		# Within <math> \eta C_6</math>, there is a unit edge from any <math>\eta \omega^j \in C_6</math> to the origin, to <math>\eta \omega^{j+1} \in \eta C_6</math>, and <math>\eta \omega^{j-1} \in \eta C_6</math>. Similarly with <math>\eta</math> replaced by <math>\overline{\eta}</math>.
	# Using (2) (which can be rewritten for instance as <math>(\eta - \overline{\eta}) (\omega^2 - 1) = -\omega</math>), we see that within <math>(\eta - \overline{\eta}) C_6</math>, there is a unit edge from any <math>(\eta - \overline{\eta}) \omega^j</math> to <math>(\eta - \overline{\eta}) \omega^{j+2}</math> and <math>(\eta - \overline{\eta}) \omega^{j-2}</math>.		# Using (2) (which can be rewritten for instance as <math>(\eta - \overline{\eta}) (\omega^2 - 1) = -\omega</math>), we see that within <math>(\eta - \overline{\eta}) C_6</math>, there is a unit edge from any <math>(\eta - \overline{\eta}) \omega^j</math> to <math>(\eta - \overline{\eta}) \omega^{j+2}</math> and <math>(\eta - \overline{\eta}) \omega^{j-2}</math>. In particular, <math>(\eta - \overline{\eta}) C_6</math> contains a triangle and thus cannot be 2-colored.
	# Each <math> (\eta - \overline{\eta}) \omega^j \in (\eta - \overline{\eta}) C_6</math> has a unit edge to <math>(\eta - \overline{\eta} \omega) \omega^j \in (\eta - \overline{\eta} \omega) C_6</math>, to <math>(\eta - \overline{\eta} \omega) \omega^{j-1} \in (\eta - \overline{\eta} \omega) C_6</math>, to <math>\eta \omega^j \in \eta C_6</math>, to <math>-\overline{\eta} \omega^j \in \overline{\eta} C_6</math>, to <math>\eta \omega^j - \overline{\eta} (\omega^j + \omega^{j+1}) = (1 + \eta \omega^2) \omega^{j+2} \in (1+\eta \omega^2) C_6</math>, and to <math>\eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j = (1+\overline{\eta \omega^2}) \omega^{j+1} \in (1 + \overline{\eta \omega^2}) C_6</math>. (Here (2) is used to obtain the latter two identities.)		# Each <math> (\eta - \overline{\eta}) \omega^j \in (\eta - \overline{\eta}) C_6</math> has a unit edge to <math>(\eta - \overline{\eta} \omega) \omega^j \in (\eta - \overline{\eta} \omega) C_6</math>, to <math>(\eta - \overline{\eta} \omega) \omega^{j-1} \in (\eta - \overline{\eta} \omega) C_6</math>, to <math>\eta \omega^j \in \eta C_6</math>, to <math>-\overline{\eta} \omega^j \in \overline{\eta} C_6</math>, to <math>\eta \omega^j - \overline{\eta} (\omega^j + \omega^{j+1}) = (1 + \eta \omega^2) \omega^{j+2} \in (1+\eta \omega^2) C_6</math>, and to <math>\eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j = (1+\overline{\eta \omega^2}) \omega^{j+1} \in (1 + \overline{\eta \omega^2}) C_6</math>. (Here (2) is used to obtain the latter two identities.)
	# Each <math> (\eta - \overline{\eta} \omega) \omega^j \in (\eta - \overline{\eta} \omega) C_6</math> has a unit edge to <math> \eta \omega^j \in \eta C_6</math>, to <math>-\overline{\eta} \omega^{j+1} \in \overline{\eta} C_6</math>, to <math> \eta \omega^j - \overline{\eta} (\omega^j + \omega^{j+1}) = (1 + \eta \omega^2) \omega^{j+2} \in (1+\eta \omega^2) C_6</math>, and to <math> \eta (\omega^{j+1} + \omega^j) - \overline{\eta} \omega^{j+1} = (1+\overline{\eta \omega^2}) \omega^{j+2} \in (1 + \overline{\eta \omega^2}) C_6</math>. (Again, the latter two identities come from (2).)		# Each <math> (\eta - \overline{\eta} \omega) \omega^j \in (\eta - \overline{\eta} \omega) C_6</math> has a unit edge to <math> \eta \omega^j \in \eta C_6</math>, to <math>-\overline{\eta} \omega^{j+1} \in \overline{\eta} C_6</math>, to <math> \eta \omega^j - \overline{\eta} (\omega^j + \omega^{j+1}) = (1 + \eta \omega^2) \omega^{j+2} \in (1+\eta \omega^2) C_6</math>, and to <math> \eta (\omega^{j+1} + \omega^j) - \overline{\eta} \omega^{j+1} = (1+\overline{\eta \omega^2}) \omega^{j+2} \in (1 + \overline{\eta \omega^2}) C_6</math>. (Again, the latter two identities come from (2).)
	# Each <math> \omega^j \in C_6</math> has a unit edge to <math> \omega^j + \eta \omega^{j+2} \in (1 + \eta \omega^2) C_6</math> and to <math> \omega^j + \overline{\eta} \omega^{j-2} \in (1 + \overline{\eta \omega^2}) C_6.</math>		# Each <math> \omega^j \in C_6</math> has a unit edge to <math> \omega^j + \eta \omega^{j+2} \in (1 + \eta \omega^2) C_6</math> and to <math> \omega^j + \overline{\eta} \omega^{j-2} \in (1 + \overline{\eta \omega^2}) C_6.</math>
	# Each <math> \eta \omega^j \in C_6</math> has a unit edge to <math>\omega^{j-2} + \eta \omega^j \in (1 + \eta \omega^2) C_6</math>; similarly, each <math>\overline{\eta} \omega^j \in C_6</math> has a unit edge to <math>\omega^{j+2} + \overline{\eta} \omega^j \in (1 + \overline{\eta \omega^2}) C_6</math>.		# Each <math> \eta \omega^j \in C_6</math> has a unit edge to <math>\omega^{j-2} + \eta \omega^j \in (1 + \eta \omega^2) C_6</math>; similarly, each <math>\overline{\eta} \omega^j \in C_6</math> has a unit edge to <math>\omega^{j+2} + \overline{\eta} \omega^j \in (1 + \overline{\eta \omega^2}) C_6</math>.

			We will show that <math>(\eta - \overline{\eta}) C_6</math> will be forced to be 2-colorable, contradicting item 3 above.

			From item 1 and the fact that the origin is colored 0,2 we see that <math>C_6</math> is colored 1,3, and in fact the coloring map <math>c</math> is given by <math>c(\omega^j) = c_1 + 2j</math> for some <math>c_1 = 1,3</math>. Similarly from item 2 we have <math>c(\eta \omega^j) = c_\eta + 2j</math>, <math>c(\overline{\eta} \omega^j) = c_{\overline{\eta}} + 2j</math> for some <math>c_\eta,c_{\overline{\eta}} = 1,3</math>.

			Suppose first that <math>c_\eta = c_{\overline{\eta}}</math>. By item 4, each <math>(\eta - \overline{\eta})\omega^j</math> is connected both to <math> \eta \omega^j</math> that has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta} \omega^j</math> that has color <math>c_{\overline{\eta}} + 2j + 2</math>. Thus <math>(\eta - \overline{\eta})\omega^j</math> has to be colored 0 or 2, giving the 2-coloring of <math>(\eta - \overline{\eta}) C_6</math>.

			Now suppose instead that <math>c_\eta \neq c_{\overline{\eta}}</math>, then <math>c_1</math> is distinct from either <math>c_\eta</math> or <math>c_{\overline{\eta}}</math>. Without loss of generality (conjugation symmetry) assume <math>c_\eta \neq c_1</math>. By item 5, each <math>(\eta - \overline{\eta} \omega) \omega^j</math> is connected both to <math>\eta \omega^j<math>, which has color <math>c_\eta + 2j</math>, and to <math>-\overline{\eta}\omega^{j+1}</math>, which has color <math>c_{\overline{\eta}}+2j</math>. Thus all of <math>(\eta - \overline{\eta} \omega) C_6</math> is 0,2-colored. Similarly, from items 6,7, each <math>\omega^j + \eta \omega^{j+2}</math> is connected to <math>\omega^j</math>, which has color <math>c_1 + 2j</math>, and <math>\eta \omega^{j+2}</math>, which has color <math>c_\eta + 2j</math>, and hence <math>(1 + \eta \omega^2) C_6</math> is also 0,2-colored. Now observe from items 4,5 that each <math> (\eta - \overline{\eta}) \omega^j</math> is the vertex of an equilateral triangle with other two vertices <math>\eta \omega^{j-1} - \overline{\eta} \omega^j</math>, <math> \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j<\math> which are 0,2-colored and hence <math>(\eta - \overline{\eta}) C_6</math> is 1,3-colored, again giving the required contradiction. <math>\Box</math>


	[[Category:Polymath16]]		[[Category:Polymath16]]