Revisions to When are the 3-colorings of vertex subsets uncorrelated?

Clarified that region affected by colouring of A must extend slightly beyond grey vertices.

Source Link

edited Apr 7, 2021 at 22:55

2.9k
1
16
22

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.

For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct assignments of colours to vertices in $A$ that are induced by the 3-colourings in $C$.

Suppose we choose two disjoint subsets of vertices, $A\subset V$ and $B\subset V$. We can ask when $C_A$ and $C_B$ are uncorrelated, in the sense that:

$$C_{A\cup B} \cong C_A \times C_B $$

That is to say, restricting our choice of 3-colourings of $G$ to those that induce one particular 3-colouring of $A$ will still leave us with all of the original possibilities for 3-colourings of $B$ that are listed in $C_B$, and vice versa.

Does this property have a standard name in the literature?
Are there any results on sufficient conditions for the 3-colourings of vertex subsets to be uncorrelated in this sense?

I suspect that determining this in general will be hard, but there might be some special cases where simple conditions have been found.

To give an example of the kind of phenomenon that interests me, in the graph below one subset of vertices has been marked in black, and another in magenta.

There are 1,007,111,586 proper vertex 3-colourings of the full graph, and these induce 12 distinct 3-colourings of the set $A$ of three black vertices.

The magenta vertices show the union of all 3-element, edge-connected subsets $B$ of $V$ such that $C_A$ and $C_B$ are uncorrelated. (The whole set of magenta vertices, $M$, does not give $C_M$ uncorrelated with $C_A$; I have not identified the maximal subset(s) of $V$ whose colourings are uncorrelated with $C_A$.)

Intuitively, it appears that any choice of a specific 3-colouring for the black vertices, $A$, affects only a limited region of $G$, given by — slightly larger than the union of the black and grey vertices;vertices — but beyond that, the possibilities for 3-colouring the remaining vertices are entirely unaffected by choices made for $A$.

So, I am curious as to whether this kind of “limited propagation of colouring choice” has been studied, and to what extent the determining conditions have been characterised.

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.

For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct assignments of colours to vertices in $A$ that are induced by the 3-colourings in $C$.

Suppose we choose two disjoint subsets of vertices, $A\subset V$ and $B\subset V$. We can ask when $C_A$ and $C_B$ are uncorrelated, in the sense that:

$$C_{A\cup B} \cong C_A \times C_B $$

That is to say, restricting our choice of 3-colourings of $G$ to those that induce one particular 3-colouring of $A$ will still leave us with all of the original possibilities for 3-colourings of $B$ that are listed in $C_B$, and vice versa.

Does this property have a standard name in the literature?
Are there any results on sufficient conditions for the 3-colourings of vertex subsets to be uncorrelated in this sense?

I suspect that determining this in general will be hard, but there might be some special cases where simple conditions have been found.

To give an example of the kind of phenomenon that interests me, in the graph below one subset of vertices has been marked in black, and another in magenta.

There are 1,007,111,586 proper vertex 3-colourings of the full graph, and these induce 12 distinct 3-colourings of the set $A$ of three black vertices.

The magenta vertices show the union of all 3-element, edge-connected subsets $B$ of $V$ such that $C_A$ and $C_B$ are uncorrelated. (The whole set of magenta vertices, $M$, does not give $C_M$ uncorrelated with $C_A$; I have not identified the maximal subset(s) of $V$ whose colourings are uncorrelated with $C_A$.)

Intuitively, it appears that any choice of a specific 3-colouring for the black vertices, $A$, affects only a limited region of $G$, given by the union of the black and grey vertices; beyond that, the possibilities for 3-colouring the remaining vertices are entirely unaffected by choices made for $A$.

So, I am curious as to whether this kind of “limited propagation of colouring choice” has been studied, and to what extent the determining conditions have been characterised.

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.

For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct assignments of colours to vertices in $A$ that are induced by the 3-colourings in $C$.

Suppose we choose two disjoint subsets of vertices, $A\subset V$ and $B\subset V$. We can ask when $C_A$ and $C_B$ are uncorrelated, in the sense that:

$$C_{A\cup B} \cong C_A \times C_B $$

That is to say, restricting our choice of 3-colourings of $G$ to those that induce one particular 3-colouring of $A$ will still leave us with all of the original possibilities for 3-colourings of $B$ that are listed in $C_B$, and vice versa.

Does this property have a standard name in the literature?
Are there any results on sufficient conditions for the 3-colourings of vertex subsets to be uncorrelated in this sense?

I suspect that determining this in general will be hard, but there might be some special cases where simple conditions have been found.

To give an example of the kind of phenomenon that interests me, in the graph below one subset of vertices has been marked in black, and another in magenta.

There are 1,007,111,586 proper vertex 3-colourings of the full graph, and these induce 12 distinct 3-colourings of the set $A$ of three black vertices.

The magenta vertices show the union of all 3-element, edge-connected subsets $B$ of $V$ such that $C_A$ and $C_B$ are uncorrelated. (The whole set of magenta vertices, $M$, does not give $C_M$ uncorrelated with $C_A$; I have not identified the maximal subset(s) of $V$ whose colourings are uncorrelated with $C_A$.)

Intuitively, it appears that any choice of a specific 3-colouring for the black vertices, $A$, affects only a limited region of $G$ — slightly larger than the union of the black and grey vertices — but beyond that, the possibilities for 3-colouring the remaining vertices are entirely unaffected by choices made for $A$.

So, I am curious as to whether this kind of “limited propagation of colouring choice” has been studied, and to what extent the determining conditions have been characterised.

Clarified what is known about full set of magenta vertices.

Source Link

edited Apr 7, 2021 at 22:35

Greg Egan

2.9k
1
16
22

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.

For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct assignments of colours to vertices in $A$ that are induced by the 3-colourings in $C$.

Suppose we choose two disjoint subsets of vertices, $A\subset V$ and $B\subset V$. We can ask when $C_A$ and $C_B$ are uncorrelated, in the sense that:

$$C_{A\cup B} \cong C_A \times C_B $$

That is to say, restricting our choice of 3-colourings of $G$ to those that induce one particular 3-colouring of $A$ will still leave us with all of the original possibilities for 3-colourings of $B$ that are listed in $C_B$, and vice versa.

Does this property have a standard name in the literature?
Are there any results on sufficient conditions for the 3-colourings of vertex subsets to be uncorrelated in this sense?

I suspect that determining this in general will be hard, but there might be some special cases where simple conditions have been found.

To give an example of the kind of phenomenon that interests me, in the graph below one subset of vertices has been marked in black, and another in magenta.

There are 1,007,111,586 proper vertex 3-colourings of the full graph, and these induce 12 distinct 3-colourings of the set $A$ of three black vertices.

The magenta vertices show the union of all 3-element, edge-connected subsets $B$ of $V$ such that $C_A$ and $C_B$ are uncorrelated. (The whole set of magenta vertices, $M$, might well possess a much stronger property than this, such as any subset $M_0 \subset M$ havingdoes not give $C_{M_0}$$C_M$ uncorrelated with $C_A$, but; I have not verified thatidentified the maximal subset(s) of $V$ whose colourings are uncorrelated with $C_A$.)

Intuitively, it appears that any choice of a specific 3-colouring for the black vertices, $A$, affects only a limited region of $G$, given by the union of the black and grey vertices; beyond that, the possibilities for 3-colouring the remaining vertices are entirely unaffected by choices made for $A$.

So, I am curious as to whether this kind of “limited propagation of colouring choice” has been studied, and to what extent the determining conditions have been characterised.

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.

For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct assignments of colours to vertices in $A$ that are induced by the 3-colourings in $C$.

Suppose we choose two disjoint subsets of vertices, $A\subset V$ and $B\subset V$. We can ask when $C_A$ and $C_B$ are uncorrelated, in the sense that:

$$C_{A\cup B} \cong C_A \times C_B $$

That is to say, restricting our choice of 3-colourings of $G$ to those that induce one particular 3-colouring of $A$ will still leave us with all of the original possibilities for 3-colourings of $B$ that are listed in $C_B$, and vice versa.

Does this property have a standard name in the literature?
Are there any results on sufficient conditions for the 3-colourings of vertex subsets to be uncorrelated in this sense?

I suspect that determining this in general will be hard, but there might be some special cases where simple conditions have been found.

To give an example of the kind of phenomenon that interests me, in the graph below one subset of vertices has been marked in black, and another in magenta.

There are 1,007,111,586 proper vertex 3-colourings of the full graph, and these induce 12 distinct 3-colourings of the set $A$ of three black vertices.

The magenta vertices show the union of all 3-element, edge-connected subsets $B$ of $V$ such that $C_A$ and $C_B$ are uncorrelated. (The whole set of magenta vertices, $M$, might well possess a much stronger property than this, such as any subset $M_0 \subset M$ having $C_{M_0}$ uncorrelated with $C_A$, but I have not verified that.)

Intuitively, it appears that any choice of a specific 3-colouring for the black vertices, $A$, affects only a limited region of $G$, given by the union of the black and grey vertices; beyond that, the possibilities for 3-colouring the remaining vertices are entirely unaffected by choices made for $A$.

So, I am curious as to whether this kind of “limited propagation of colouring choice” has been studied, and to what extent the determining conditions have been characterised.

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.

For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct assignments of colours to vertices in $A$ that are induced by the 3-colourings in $C$.

Suppose we choose two disjoint subsets of vertices, $A\subset V$ and $B\subset V$. We can ask when $C_A$ and $C_B$ are uncorrelated, in the sense that:

$$C_{A\cup B} \cong C_A \times C_B $$

That is to say, restricting our choice of 3-colourings of $G$ to those that induce one particular 3-colouring of $A$ will still leave us with all of the original possibilities for 3-colourings of $B$ that are listed in $C_B$, and vice versa.

Does this property have a standard name in the literature?
Are there any results on sufficient conditions for the 3-colourings of vertex subsets to be uncorrelated in this sense?

I suspect that determining this in general will be hard, but there might be some special cases where simple conditions have been found.

To give an example of the kind of phenomenon that interests me, in the graph below one subset of vertices has been marked in black, and another in magenta.

There are 1,007,111,586 proper vertex 3-colourings of the full graph, and these induce 12 distinct 3-colourings of the set $A$ of three black vertices.

The magenta vertices show the union of all 3-element, edge-connected subsets $B$ of $V$ such that $C_A$ and $C_B$ are uncorrelated. (The whole set of magenta vertices, $M$, does not give $C_M$ uncorrelated with $C_A$; I have not identified the maximal subset(s) of $V$ whose colourings are uncorrelated with $C_A$.)

Intuitively, it appears that any choice of a specific 3-colouring for the black vertices, $A$, affects only a limited region of $G$, given by the union of the black and grey vertices; beyond that, the possibilities for 3-colouring the remaining vertices are entirely unaffected by choices made for $A$.

So, I am curious as to whether this kind of “limited propagation of colouring choice” has been studied, and to what extent the determining conditions have been characterised.