Reductions

From CSclasswiki
Jump to: navigation, search

Reductions

New page created 21Mar11.

Corner Reduction: New Reduction (12Mar11)

A future marker for me to explain, but this I think is neat:

Corner Reduction. Let b be be a corner brick, that is, a brick with three exposed (exterior) faces sharing a vertex. If b is the tip of a 2x2x2 subcomplex (without any conditions on exposed faces among this subcomplex, so there can be arbitrary surrounding bricks as long as b itself remains exposed on three faces sharing corner), then b is reducible. I do not consider this obvious, so I need to detail a proof, but the proof is quite solid. I just don't have time to write it out at the moment. Although I am confident that this reducibility is sound, I have no sense of its consequences (if any!?).

Inventory of Reductions (21Mar11)

Some of this repeats the notes from 9Mar11 and the corner reduction description above. We have identified three reductions. I now realize that the 1st & 3rd imply the 2nd, so we only need two reductions. Here I will just describe the reductions, leaving justification to later.

  1. Deg-2 Reduction: Delete any brick b of degree ≤ 2.
  2. Duplicate Layer Reduction: Let R be a connected region of bricks in one layer (actually, within any xyz-coordinate plane—I'll use "layer" in this extended sense). R should be maximally connected, in that we want to include every brick connected to R in that layer. So R is like an island. If the following two conditions hold, R can be deleted:
    1. R should be exposed on one side, that is, no bricks are attached to one side of R.
    2. To the other side of R, all the bricks are duplicated in the adjacent layer.
  3. Corner Reduction: Let b be be a corner brick, that is, a brick with three exposed (exterior) faces sharing a vertex. If b is the tip of a 2x2x2 subcomplex, then b can be deleted.

As mentioned, I am convinced that the Duplicate Layer Reduction is already implied by the other two. So this means there are just two reductions, each of which deletes exactly one brick b:

  1. Deg-2 Reduction
  2. Corner Reduction

A proof of this lemma is needed:

Lemma: Any Duplicate Layer Reduction can be achieved by a combination of Deg-2 and Corner Reductions.

Proof: [needed]

Hmmm. Maybe this is false without "filling-in." Not as clear as I thought...

If this is R, with a duplicate layer below, then all bricks are degree 3, and no corner can be reduced.

And if the above were an odd cycle, it could not be filled in. So... I guess this lemma is false and we need to retain all three reductions.

Reduction Theorem (21Mar11)

The justification for reductions is the following theorem:

Theorem: Let C be a complex that is reducible to the empty complex by repeated application of the reductions (detailed above). Then C is 3-colorable.

(22Mar11): Rawia and I met and went over the proof. Here it is. (Not entirely finished.)

Proof: The proof is by induction. For the base case, a single brick is 1-colorable and so 3-colorable.

For the general case, we know that C is reducible by hypothesis. Let C1 be the complex that results from the first step of the presumed reduction. Now the proof breaks into three cases, depending on which of the three reductions was applied in that first step.


(23Mar11) But, because I can sense that my first attempt to explain this was not successful, let me try to frame it better before plunging into the details. One way to look at it is as follows. If C can be reduced to one brick by our reductions, then it can be built up from one brick by reversing each reduction. It is easiest to think of just the Deg-2 Reduction, the simplest. This means we build up C from the one brick by gluing on bricks one at a time. Now color the first brick color 1. When the second brick is added, we can choose color 2. Keep adding bricks one by one, at each stage growing the previous 3-coloring. Because each added brick can only share at most two faces in this reverse construction process, we always can color the newly added brick. So we construct C from the ground up, always having at each stage a 3-coloring.

The same is true for the more complicated reductions; it is just that the logic of why the 3-coloring can be extended at each construction stage becomes more involved. This construction viewpoint is exactly the same as induction, unwound so-to-speak. The induction viewpoint is: We start with C, and we perform just one reduction to C1. Now by induction we assume we could have 3-colored C1. This is the same as saying that if we started from one brick and reversed the induction, we could reach C1, and it would be 3-colored, because it is 3-colored at every stage. Now we just need to show that reversing the very last construction step, which is the very first reduction, can extend the 3-coloring of C1 to a 3-coloring of C.

OK, that is enough preamble. Now here are the details.


Case 1: Degree ≤ 2 Reduction. C1 has one fewer brick than does C, say by removing brick b of degree ≤ 2. So the induction hypothesis applies and shows that C1 is 3-colorable. Now we place b back on C1, reforming the original C. Because b has degree ≤ 2, it is adjacent to at most two colors in C1. Choose the 3rd color. This 3-colors C, and the induction hypothesis is reestablished.

Case 2: Duplicate Layer Reduction. Let R be the layer deleted to form C1. Again, C1 has fewer bricks than C, and so can be 3-colored by the induction hypothesis. Now put R back. By the definition of a layer reduction, each brick b in R is adjacent to a brick "below" it in the adjacent layer, which has now been colored. If that brick below is colored c, color b color c+1, with, as usual, wrap around. This is a valid 3-coloring of R and compatible with the 3-coloring of C1. Thus we have 3-colored C, and the induction hypothesis is reestablished.

Case 3: Corner Reduction. Let b be the corner brick removed from the 2x2x2 cluster to form C1. I showed Rawia that it cannot happen that its three adjacent bricks are given three different colors in the 3-coloring of C1. So, even though b has degree 3, it is safe to put it back, because it can only be adjacent to two, not three, colors. (I realize this is not a proof! It will take some effort to write this out fully. But Rawia agreed it was sound.)

(23Mar11) What is tricky with this 3rd case is that the proof that the corner reduction can be reversed, and the 3-coloring of C1 extended to a 3-coloring of C, is a proof by contradiction. If the removed brick b is adjacent to only two different colors in the 3-coloring of C1 given by induction, we are safe to color b with the 3rd color. The only time we could be forced to using a 4th color is if b is adjacent to three distinct colors provided by the 3-coloring of C1. So I assume we are in this problematic case, and then show that in fact it cannot occur if C1 is truly 3-colored, by showing that there must be a color clash in C1 in the problematic case. But we know there cannot be because C1 is validly 3-colored by induction. Or if you prefer the reverse viewpoint, we have constructed C1 from one brick, extending a 3-coloring at each stage, and we are poised to put back the corner brick b. The proof shows that, the problematic case cannot occur, so we can add back b and extend the 3-coloring of C1 to a 3-coloring of C.

Corner Reduction proof. The squares represent the front 2x2, and the back 2x2 behind it. Assume the removed corner brick is adjacent to three different colors. Then an illegal color clash (3 adjacent to 3, bottom right) is forced following the logic a,b,c,d. Therefore the assumption that colors 1,2,3 are adjacent to the top front corner brick leads to a contradiction.

(Trivial) Irreducible Object (24Mar11)

The only object I know which is irreducible by the above three reductions is the trivial case we discussed before Spring Break: Start with a 3x3x3 complex of 27 cubes, and remove the innermost cube, leaving a one-cube cavity there. Every brick has degree 3. Every layer is different from the one beneath it (which has the hole). And there are no 2x2x2 subcomplexes from which to pluck a corner brick (again because of the hole).

The reason I say this is trivial is that, as Micaela observed long ago, if we simply fill in the hole, then it is reducible. However, I have yet to see how to incorporate this "filling-in" in a completely general way, how to integrate filling-in with reductions, and what the consequences might be. Future work...

String Complexes are 3-colorable! (30Mar11)

A rough draft of the proof we worked on today:

Thickness-k Complexes (JOR Notes from 31Mar11)

I don't have time to write this carefully, but here is a rough high-level summary. First a definition. A thickness-k complex is one in which every brick has z-height exactly 1, and the total z-height of the complex is k. So these complexes can be partitioned cleanly into "layers."

  • We have a (new) proof that every thickness-2 complex is 3-colorable.
  • Some believe essentially the same proof extends to thickness-3 complexes. (I remain unconvinced until this is written out.)
  • There are potential problems with the notion of "filling-in" (see email for suggested alternative names) for thickness-k complexes for larger k, perhaps k ≥ 5.
  • We convinced ourselves that if any combination of filling-in and reductions eventually reduces a complex to the empty complex, then it is 3-colorable.


Thickness-2 Complexes (4Apr11)

A rough draft of just the Thickness-2 proof:

(6Apr11): Whoops! The group showed today my attempted simple proof is in fact wrong! :-/ Of course we have another proof of the result. It seems we need to get a precise characterization of the structure of an irreducible thickness-2 complex, and then apply the proof method in that draft. I'll be thinking about that...

Hmm. Maybe this isn't a good path. What would we do with this complex? (It is a variation on the example that shows the above proof is flawed.) It seems irreducible by our three rules, but it cannot be filled either....

(10Apr11): My example broke last Thursday---You showed me it could be partially filled and then reduced. Below I have replaced the example. Now I think this can neither be filled nor reduced....? It consists of two odd cycles, and can be 3-colored.

An irreducible thickness-2 complex.

Thickness-3 Complexes (5Apr11)

My attempts at a fill-and-reduce proof for thickness-3 complexes seems to be stuck on this example, with two odd holes running through the complex in perpendicular directions:

Is this complex irreducible? (Hand-drawn figure uses orthographic projection rather than perspective projection.)

(6Apr11): Yes, we determined that it is irreducible according to our three reductions. Hmmm...

Reduction Figures (6Apr11)

All figures below are JPEG files, width 600 pixels (heights variable). I did not have time to crop them optimally. Click on each thumbnail to reach full-size version.

New Deg-3 Corner L-Reduction (19Apr11)

I found a new reduction! It is a deg-3 corner brick in a special configuration. It is the 2x2x2 configuration, except that two of the back bricks are missing. So rather than 8 bricks in the 2x2x2, there are 6 bricks, forming a 2-layer "L" shape. So I am calling it a "Deg-3 Corner L-Reduction." The proof is not that simple, but it relies on the {1,2} and {3,1} and {3,2} connected components. Unlike the 2x2x2 reduction, this one needs that the complex illustrated is extreme, in the sense that all six bricks must be exposed to the corner as illustrated. (This weakens its applicability.) But at least, for example, it applies to thickness-2 complexes.

Thickness-2 Irreducible Complex Revisited (12Apr11)

I don't know how to justify this, but I've inserted some bricks in that problematical example above, in such a way that every cycle's parity is maintained (I think). After the insert, several fills are now possible. And after those fills, the Duplicate-Layer reduction applies:

The irreducible thickness-2 complex C above (left figure), with inserts that permit it to be reduced. Middle figure is C*, right figure after filling.


(13Apr11). My attempt to prove that a version of this "pumping" (by insertion of a new level) is always justified, has failed. I was trying to prove that, if the pumped complex C* is 3-colorable, then so must be the original complex C.






Back to top of MTH301_Math_Research_S11
Back to bottom of MTH301_Math_Research_S11#Reductions