MTH301 Math Research S11
Contents
- 1 Who We Are
- 2 Solid-coloring of objects built from 3D bricks
- 2.1 Some Background Material [Jan 2011]
- 2.2 Papers that may be relevant/useful [8Feb11]
- 2.3 Some Figures of Zonohedra and Parallelepiped Bricks [8Feb11]
- 2.4 JOR Notes after 9Feb11 Meeting
- 2.5 JOR Notes after 16Feb11 Meeting
- 2.6 JOR Notes after Thurs 17 Feb 11 Meeting
- 2.7 JOR Notes after Wed 23 Feb 11 Meeting
- 2.8 VIPY Notes after Thur 24 Feb 11 Meeting
- 2.9 JOR Notes after Wed 2 Mar 11 Meeting
- 2.10 JOR Notes after Wed 9 Mar 11 Meeting
- 2.11 MRM Notes after Thur 10 Mar 11 Meeting
- 2.12 Reductions
- 2.13 Final Paper
Who We Are
In alphabetical order:
- Lily Du <ldu@smith.edu>
- Jessica Lord <jlord@smith.edu>
- Micaela Mendlow <mmendlow@gmail.com>
- Emily Merrill <emerrill@smith.edu>
- Joseph O'Rourke <orourke@cs.smith.edu> (My schedule is a link on my homepage.)
- Viktoria Pardey <vpardey@smith.edu>
- Rawia Salih <rsalih@smith.edu>
- Stefanie Wang <stwang@smith.edu>
Solid-coloring of objects built from 3D bricks
Some Background Material [Jan 2011]
- Initial PowerPoint Presentation, Jan 2011
- "A Note on Solid Coloring of Pure Simplicial Complexes": JOR paper on coloring simplices (PDF)
- Suzanne Gallagher Honors Thesis, 2003: Suzanne Thesis (PDF)
Papers that may be relevant/useful [8Feb11]
I haven't looked at either of these (just-released) papers, both by Landon Rabern. Recording them here for future reference:
- "An Improvement On Brooks' Theorem": http://arxiv.org/abs/1102.1021
- "Coloring Δ-Critical Graphs With Small High Vertex Cliques": http://arxiv.org/abs/1102.1023
Some Figures of Zonohedra and Parallelepiped Bricks [8Feb11]
- This gives a hint why zonohedra are called that: it is because of the zones:
- We were hoping that objects built from parallelepiped bricks always had a corner, but---alas!---this is not true, via this complicated counterexample: This is from a 2004 paper, "On Corners of Objects Built from Parallelepiped Bricks," which can be accessed from my list of papers here.
JOR Notes after 9Feb11 Meeting
Where to Focus Next
We decided to first work on these special cases of the rectangular box version:
- All boxes are cubes, 1x1x1 (Jessica's idea). I believe there is a relatively simple checkerboard proof that 2 colors suffice. Proof now added below.
- All boxes are either 1x1x1 cubes, or 2x1x1 (call these long boxes). My sense is that this is already difficult. So, following Polya's dictum, we need to simplify:
- The object is at most 1 unit thick in the z-direction. (Let's call that z-thickness.) Then it is the same as the planar case, known to be 3-colorable.
- The object is at most 2 units thick in the z-direction. I hope we can prove this! Should be 3-colorable.
- The object is at most 3 units thick in the z-direction. Maybe now getting more difficult. But if we can prove 3-colorability here, we move on to thicker objects. At some thickness, we'll be bumping into difficult cases.
Proof that Objects Built from Cubes are 2-colorable
Incidentally, objects built from cubes are sometimes called polycubes in the literature. Here's a rough proof.
First imagine that space is tesselated (partitioned) into cubical cells, infinite in all directions. Then the cells can be 2-colored as follows. Take the cells whose base face touches the z=0 plane. Color these like a checkerboard. Now look at the next layer up, those cells whose base face touches the z=1 plane. Color these like a checkerboard also, but the opposite of the layer below. So if the cell whose lower-left corner is at (0,0,0) is colored 1=white, color the cell just above it, whose lower-left corner is (0,0,1), 2=black. Continue in this manner, coloring each layer like a checkerboard, alternating the pattern vertically. This colors all of infinite space with 2 colors.
Now, any polycube object is a subset of this infinite space, and the object's cubes can inherit the colors of the cells. QED.
Results that are Known for Boxes
Here is a compendium of results that I know, focused on boxes. Terminology: To say an object is k-colorable means that k colors suffice, are enough, but it does not say that k colors are necessary, that there is an examples that really needs k colors.
First, results in 2D:
- Objects built from squares in 2D are 2-colorable (see proof above, restricted to one layer).
- Objects built from rectangles (of different sizes) in 2D are 3-colorable, and 3 colors are needed when there is a hole surrounded by an odd cycle. (This is a special case of the result of Wagon for parallelograms.) The proof is by induction: There exists a corner rectangle, remove it, apply induction, put it back.
- Objects built from rectangles (of different sizes) in 2D are 2-colorable if there are no holes (this is called genus zero).
Now results in 3D:
- Objects built from cubes in 3D are 2-colorable (proof above).
- Objects built from rectangular boxes (which we call bricks) in 3D with no holes are 2-colorable. This is a result from Suzanne's thesis. I did not discuss that yet. A beautiful and surprising result. Surprising that moving to 3D leaves matters still 2-colorable.
- Objects built from rectangular bricks in 3D are 4-colorable. I sketched the proof by induction: There exists a corner brick etc.
- Objects built from rectangular bricks in 3D sometimes need 3 colors, if there is a hole with an odd cycle. This is just the same as in 2D.
- Objects built from rectangular bricks in 3D with just one hole (i.e., genus 1) are 3-colorable. This is another result from Suzanne's thesis that I didn't discuss. The proof is difficult and tangled (and not explained well in her thesis).
Suzanne and I conjectured in 2003 that all objects built from rectangular bricks are 3-colorable. We could not construct an example that needs 4 colors.
AMS Meeting @ Holy Cross, Worchester MA
April 9-10. AMS link
Abstract submitted Saturday 12Feb11! Our talk will be on Saturday April 9th.
Four Colors needed for Convex Quadrilaterals (14Feb11)
You might wonder, when are four colors ever needed, even in the plane? One answer is that any configuration whose dual graph includes a copy of K_{4}, the complete graph on 4 nodes, needs four colors. But K_{4} cannot occur with boxes, in 2D or 3D. So what other configurations force four colors?
The following nice example shows that even convex quadrilateral regions (convex = no dents, no concavities) might need four colors. This is taken from Sibley & Wagon:
The dual graph has lots of odd cycles, in fact of length 3. I guess there is no concise characterization of what types of graphs need four colors; otherwise the proof of the 4-color theorem would not be so difficult!
Several Odd Cycles forming a Frame (14Feb11)
Well, this didn't quite come out like I had intended. The top and bottom "faces" are even cycles; I intended odd cycles on all six faces, but only manged to achieve them on {front, left, right, back}. Not sure if that is even possible to get six interacting odd cycles. In any case, I think this example is not difficult to 3-color:
Notice this example has z-thickness 4.
Link to Mathematica file: coming soon... Here is the Mathematica file: Cycle9Frame.nb: right-click and Save Link As. Open the file, Select-All, Shift-Return to evaluate the notebook.
JOR Notes after 16Feb11 Meeting
What a great meeting! :-) Even though we are stuck, (a) we made progress, and (b) we are stuck on something substantive. Here is what I think happened today:
- We restricted attention to objects with z-thickness ≤ 2, and using only two shapes of bricks, let's call them unit and long bricks.
- We argued that vertical long bricks (let's call those tall bricks—long bricks oriented vertically) form a separate component of such objects, a separate component in the dual graph. This is because a tall brick can only connect to another tall brick to remain within z-thickness ≤ 2.
- This component is essentially planar, in fact, a planar configuration made of squares (the base of the tall bricks). So we know this component is 2-colorable (we said 3-colorable at the meeting, but I just realized it is 2-colorable; of course it doesn't matter).
- Because the tall bricks form a separate component, they cannot interact with the other bricks. So, we can just ignore this component from now on.
- This leaves is with the following situation: all bricks are unit or long, and if long, they are long horizontally (let's call those wide bricks), within one layer.
- Each layer is itself planar, and so 3-colorable.
- So the challenge is: Prove that a two-layer object built from unit and wide bricks is 3-colorable.
So the problem has been reduced. We explored the following "algorithm" (which we don't know how to complete) for coloring these objects:
- Color layer 1 with 3 colors.
- In layer 2, for every brick b_{2} that sits on a brick b_{1} in layer 1, if b_{1} is colored c, then color b_{2} c+1 (with implied wrap-around: 3+1 = 1).
- Somehow show that the remaining bricks in layer 2, which are suspended above emptiness beneath them, can be colored with just three colors.
We ended without a clear method for resolving this last problem. But we all(?) remain convinced that four colors cannot be forced. In other words, it seems that one does not have to be careful in coloring layer 1—any 3-coloring of layer 1 can be completed in layer 2 with just 3 colors. We tried to think of situations that would force the need for a 4th color, and it seems impossible to force. But we definitely do not (yet) understand this.
Lily's Algorithm
Lily caught me on the way to a meeting to suggest an algorithm, this time an algorithm that colors every brick in a two-layer object built from unit and wide bricks (to continue the notation defined above). I think this is it (Lily, you may correct me if I've mangled it).
3-color layer 1. In layer 2, start with any brick b. Color b with the smallest color number not used by any of its neighbors, either below or in the same layer. Repeat. That's it! The novelty here is to always choose the minimum color number available for use. Once you start coloring bricks in layer 2, some of the constraints come from layer 2, some (at most one) from layer 1.
Now this needs a proof that it never needs to use color 4. I haven't had time to think about it, but it is promising. It is a definite algorithm (whereas the one I suggested did not have a plan to color all the bricks, more a hope and a prayer). So we should either be able to prove it always works, or find a counterexample.
JOR Notes after Thurs 17 Feb 11 Meeting
At this point I am just going to repeat the final list of what we agreed to work on next:
- The "hallucintating/imaginary bricks" proof for z-thickness ≤ 2 needs to be written out carefully to see if it holds up. I'll do that. (Finished 20Feb11. See below.)
- I think this proof can be simplified if we only allow whole-edge-to-whole edge contact between the two layers. The only reason the imaginary bricks may not meet the real bricks in layer 1 whole-face-to-whole-face is if there is one or more bricks in layer 2 that meet a brick in layer 1 violating whole-edge-to-whole edge contact. I am attracted to this restriction, because it is a bit aesthetically displeasing to have to extend the model. I'll think about this.
- I think this doesn't work. The same issue arises if we have two boxes sharing just one corner. So, I guess have to go back to the full ugliness of that argument.
- Having now written out the proof, I no longer think it is so ugly. :-)
- The next logical step is to work on z-thickness ≤ 3, restricting to unit bricks and 2x1x1 bricks. As Emily noticed, already we can get new odd cycles in vertical planes, so this will likely need new ideas. Maybe all the complexity is concentrated in three-layer objects?
- We have a somewhat vague conjecture that the number of times a 3rd color needs to be used (for rectangles in the plane) is the minimum number of vertices that dominate some odd-cycle graph that we couldn't quite pinpoint. In terms of cycles drawn in the plane, there are two ideas:
- Vicki suggested that we can retract or collapse any number of odd cycles that are nested and share one point, which eliminates the problem that Micaela noticed that in fact there are many ways to weave through these odd cycles, proliferating odd cycles and confusing the issue. Retraction will hopefully control this unwieldy aspect.
- If we draw the odd cycles as intersecting circles in the plane, we want to find the minimum number of points that touch every circle. This seems to be the right number, but we didn't manage to phrase it entirely in terms of a graph dominating number.
- Stephanie raised an apparently novel question: Is there an object built from trapezoids (two opposite parallel edges) that needs 4 colors in the plane, or do 3 colors always suffice? (Again, we only permit gluing whole edge to whole edge.) We couldn't alter the convex quadrilaterals example that needs 4 colors to trapezoids.
- If we cannot make progress here, it would be natural to restrict further to isosceles trapezoids, those with equal base angles. (I looked it up, and this is the right name for this shape: Wikipedia link.)
Rawia ordered 100 Math Blocks that can attach to one another on all six faces, which should be fun to explore. She also found a web site where one can construct objects out of Legos.
Thickness-2 Proof (17Feb11)
- Draft of Thickness-2 proof: TwoLayers.pdf (20Feb11 draft). This is pretty much finished now. Seems to hold up.
- Here is the .tex: TwoLayers.tex.
Trapezoids (18Feb11)
Like convex quadrilaterals, trapezoids can form odd cycles of length 3 and larger. This example has several interacting odd cycles (three 3-cycles, one 5-cycle), but still only needs 3 colors. Hmm...
(19Feb10). Briefly I thought this needed 4 colors, but I was wrong:
Again it seems the freedom to push the 3rd color around the odd cycles is what allows avoidance of 4 colors.
New Special Case: z-height = 1 (20Feb11)
Rather than sticking to the idea of only mixing 1x1x1 and 2x1x1 boxes, I now think the following is perhaps the better special case to consider: for every box, one dimension, the z-dimension or height, is always 1, but the other two can be anything. The reason this seems simpler to me now is that there is a clear sense of layers. This didn't matter for thickness-2 box complexes, but it matters quite a bit for thickness-3 complexes: then every box is on layer 1, layer 2, or layer 3; there are no anomalous boxes crossing layers. And thickness-3 still seems difficult, so there is no reason to make it more complicated with layer crossings. In fact, we could still concentrate on just 1x1x1 and 2x1x1 boxes, but only permit the latter to lie horizontally, within one layer.
Having identified this special case, I don't have a new idea on how to attack it. But it seems like the next place to concentrate for boxes. (We now have other problems on which to concentrate as well: trapezoids and domination.)
(22Feb11) I should add (prompted by Jessica here), that I don't see how to extend the thickness-2 proof to thickness-3. It seems that requires, in some sense, projecting the constraints from both layer 3 and layer 2 down to layer 1, coloring there, and percolating upwards. But it seems we lose planarity. I don't see my way clearly in this thicket, but it seems to get more complicated.
References on Odd Cycles (23Feb11)
There is literature on odd cycles and coloring. I have not looked at these yet, and it is quite unclear if it will be worth the effort. But it is at least interesting that the odd-cycle "structure" affects coloring.
- "Structure and Coloring of Graphs with Only Small Odd Cycles," Susan Wang paper
- "Colourings of graphs with two consecutive odd cycle lengths ," link.
JOR Notes after Wed 23 Feb 11 Meeting
We formulated a Hypothesis which we believe is a clean theorem, but we are missing a proof at one point.
- Hypothesis: If a complex (in 2D, but maybe a proof can work also in 3D?) has no odd cycles, then it is 2-colorable. We all firmly believe this, but by the end of the meeting we did not have a clear proof.
- If removal of a set of bricks B from a complex C leaves C \ B (that's C set-minus B) without any odd cycles, and if no two bricks in B are adjacent, then C can be 3-colored using the 3rd color only |B| times (where |B| is the cardinality of B).
- Thus, the number of times the 3rd color needs to be used in a 3-coloring is the same as the minimum number of non-adjacent bricks whose removal breaks all odd cycles.
This is exciting because (a) the Hypothesis above is surely true and we should be able to prove it, (b) the reasoning no longer seems to rely on 2D, and so we seem to be on the verge of establishing a result for 3D (or even arbitrary dimensions).
We studied two nested odd loops, touching throughout their lengths, and at least I found the situation confusing, as the two bricks using the 3rd color needed to be diagonally adjacent. (Added 27Feb11: Micaela remembers a counterexample to this "diagonally-adjacent" claim.) We started to look at ... stringy(?) complexes that just consist of cycles that touch minimally (unlike the two nested cycles that touched everywhere), and this seems like an approachable special case. This is one I drew on the board:
Here is an example of Rawia's that includes lots of nested and interacting spirals on which to test our hypotheses. It has 9 holes. It starts to become non-obvious to me what is the minimal set B that breaks all odd cycles, and therefore what is the fewest of the 3rd color needed. (Notice this is not quite "stringy," because it has four squares forming a 2x2 square, but perhaps this is not relevant to the cycle structure?)
Here is a link to a printable version of Rawia's example in case you want to experiment: RawiaSpirals.pdf
Rawia's math cubes arrived and will be in FH243 for exploration.
VIPY Notes after Thur 24 Feb 11 Meeting
We wanted to prove the Hypothesis: If a complex has no odd cycles, then it is 2-colorable. It seemed as if we were all trying to do so by induction on the number of blocks. There were some disagreement about how to do that but I outline what I think our main ideas were.
- We agreed (we did not prove but all firmly believe) on the fact that if you have a complex that has no odd cycles, removing a block cannot create an odd cycle. (JOR comment: Excellent point which I never considered!)
- We agreed also on the fact that if you have a complex that has no odd cycles, there will be a place where you can add a block without creating an odd cycle. That obviously does not work in an arbitrary position.
- Jess' idea: Taking a complex with n rects, then add one in a position that is not creating an odd cycle. We can assume it is a corner stone, as we just need to reduce our complex by 1 to use the ind. hyp. and we could either find a corner stone or block that was not included meaning only touches one other. Now, there was another argument why the adjacent blocks (all touching each other at corners) have to have the same colour. (I leave it for Jess to add; I am sorry I can't recall the argument quite right)
(JOR comment) On this last idea, as I mentioned in email, I suggest we strengthen the hypothesis to include exactly what is needed to complete this argument:
- Hypothesis2: If a complex has no odd cycles, then it is 2-colorable in such a way that diagonally adjacent blocks (touching one another at a corner) have the same color.
April 9th Talk Scheduled
For Saturday, 5:00PM. See Special Session Program.
Distance Coloring Algorithm
(1Mar11) Starting from the square marked 0, shortest distance (edges in dual graph). This first example has no odd cycles:
(2Mar11) This second example consists of two intersecting odd cycles in 3D:
JOR Notes after Wed 2 Mar 11 Meeting
Great progress today!!
- Theorem. A box complex (in any dimension!) with no odd cycles is 2-colorable.
- Choose any box X as the start node. Run the shortest-path (paint-spreading) algorithm to label every box with its shortest distance from X.
- Claim: The label d for any box b differs by at most 1 from the labels for every box adjacent to b, i.e., all the adjacent distance labels are d, d+1, or d-1.
- Suppose two adjacent boxes get the same label d. Then the paths from those boxes back to X yield a path of length 2d+1, an odd cycle.
- Therefore, because we assumed there are no odd cycles, no two adjacent boxes get the same label. So their labels must differ by exactly 1, d+1 or d-1.
- Therefore adjacent boxes always have different parity labels.
- Now color every odd box color 1, and every even box color 2. This is a 2-coloring.
- Corollary. If removal of a set of boxes B from a complex breaks all odd cycles, and if no two bricks in B are adjacent, then the complex is 3-colorable.
- This follows almost immediately from the 2-colorable theorem.
- This again works in arbitrary dimensions. :-)
- Challenge. When the shortest-path algorithm is applied to an arbitrary complex, the result (in general) is a number of conflicts where two adjacent boxes are both labeled d. We want to prove that we can resolve all such conflicts (by coloring one or the other box color 3) without selecting adjacent boxes for the 3rd color.
- Define the conflict graph to have an arc (from the dual) between any two boxes that are adjacent and are assigned the same distance label from the algorithm. Example shown below.
- We need to establish that the conflict graph has no odd cycles; because if it did, the desired conflict resolution would be impossible.
- Some felt confident that this must hold, that the conflict graph has no odd cycles. It seems theoretically possible that it might occur, but we do not yet understand this aspect.
It seems the new focus should be: Understanding the structure of the conflict graph that results from applying the shortest-path algorithm from an arbitrary start box X.
This example is entirely unproblematical, but we don't yet understand how weird and complicated the conflict graph might be. Especially in 3D (this is where perhaps the dimension makes a difference).
Conflict Graph w. Odd Cycle
I believe that the conflict graph can have an odd cycle C. Here is crude sketch of a construction. Start with the odd cycle C somewhere in space. We need every brick of the cycle to be the same distance d from the start brick X. Place X far away. Now create string-like paths to two adjacent bricks of C. Include two long bricks in each path, and then adjust their lengths k_{1} and k_{2} so that the two paths have identical lengths. This can always be done if X is far enough away and we can use arbitrarily long bricks. Then do this again for two other bricks, adjusting k_{3} and k_{4}. Etc.
Of course it is easy to 3-color this example. But I think this shows that the proof idea we had yesterday cannot be completed as we hoped. Because we would want to change the color of every other brick in the odd cycle to color 3, and this would necessarily result in two adjacent bricks with color 3.
Emily's Example (3Mar11)
Here is Emily's Mathematica Notebook (right-click and SaveAs), and here is one image from it:
From her notebook comments:
- The orange is d=0, and then purple/blues are odds and pinks/reds are evens. Each block in the (odd) 7-cycle at the bottom is touching a block with d=11, so therefore each block in that cycle has d=12.
Spectacular, Emily!
One obvious comment, of which I am sure you are all quite aware: Just because we have found a counterexample to the hopeful hypothesis that the conflict graph from any start brick X has no odd cycle, does not spell the end of this approach. Because we only need that ∃ one X whose conflict graph has no odd cycle. And it seems a tall order to construct an example where the conflict graph for every start X has an odd cycle. But then again, it also seems difficult to prove that such a beast cannot exist.
Ruminations on: Where Next? (5Mar11)
It seems to me were are in a difficult spot now.
- We know that if we can block all odd cycles with non-adjacent bricks, we are finished. But Emily's exploration of Rawia's example has convinced me that grasping all odd cycles is difficult.
- As in my comment above, we just need some X for which the conflict graph has no odd cycle. It seems difficult to imagine an example where every X leads to an odd cycle. But I don't see a way to proceed here.
- One idea is to stick with just one X, and if it does lead to an odd cycle in its conflict graph, repair the problem with local changes. For example, if we apply the coloring-repair procedure and end up with two 3's next to one another, one can simply be moved off the odd cycle (I know I should draw a figure for this, but it might not be worth it...). It is like a transposition in a permutation: the sequence of colors 3, 1, 2 in a path becomes 1, 3, 2, moving the problematical 3 to a safe spot. I cannot see how this could work in every situation, partly because I cannot wrap my head around "every situation." If we pursue this line, we need a better understanding of the conflict graph.
Those are three lines following our previous path. I have one other, rather different approach, that involves reducing a complex to a simpler complex. For example:
- Define a complex to be clotted if every node in the dual has degree ≥ 3. I call these clotted complexes because they are densely connected.
- Suppose we could prove this Hypothesis: Every clotted complex is 3-colorable. (I have no idea how to prove this, but ...)
- Then we would be finished. Let C be any complex with a node of degree ≤ 2. Remove that node, color the remaining complex by induction, put it back, using the 3rd color that does not clash with its at-most two neighbors.
- So we only have to consider clotted complexes.
This is what I mean by a reduction. Here is another reduction, less interesting and useful, but, for what it is worth:
- Let C be a complex that has two identical, adjacent layers of bricks, with no longer bricks jumping across these layers (have to think of a cleaner way to say this). Then, C is 3-colorable if and only if the "collapsed" version of C that merges the two layers to one, call it C_{1}, is 3-colorable. This is because, if you can 3-color C_{1}, you can re-insert the collapsed layer, color it with colors c+1 as we did with the 2-layers proof, and adjust the colors above accordingly.
- So now we only have to settle the case of clotted complexes with no two identical, adjacent layers.
There are likely other reductions. Unfortunately, I have little intuition on what this class of complexes looks like. Definitely not like the complexes we've been drawing!
Genus/Holes (6Mar11)
Another direction occurred to me: Rather than push harder, we could step back and see if we have already proved that some subclass of complexes are already established as 3-colorable by our work so far. In particular, we may be able to prove that any complex with genus ≤ 2 is 3-colorable, which would be a new result (Suzanne and I proved this for genus = 1).
The genus of a complex is, intuitively, the number of holes. Another intuitive notion, from topology, is that it is the number of handles on a sphere, like the handle of a coffee cup. To go beyond intuition, one must use Euler's polyhedral formula to compute the genus from the number of vertices, edges, and faces.
If you look at Emily's example above, it has quite a few holes. It is not easy to count, but I would guess it has genus 5 or more. If we could prove that, in order to get stuck in our coloring algorithm—stuck by an odd cycle in the conflict graph—the genus has to be at least 2, then we have a new result.
Here is one approach. We know that any genus-0 complex is 2-colorable, a result from Suzanne's thesis. (Also our work gives an alternate proof of this, I think.) A genus-0 object is called a topological ball or just a ball. I think this is implied by our work:
Lemma: No odd cycle can be "filled-in" with bricks so that it lies on the boundary of a ball.
The reason is that, if it could, then it would be 2-colorable, but we know an odd cycle needs 3 colors. Now, because an odd cycle cannot be filled-in (in this sense), every odd cycle surrounds a hole. Now what I would like to conclude is that, in any Emily-like example, there must be at least two holes: One for the odd cycle in the conflict graph (at the bottom of Emily's example), and at least one for the paths leading to that odd cycle. The challenge here is to prove that the various odd cycles in such an example cannot all derive from the same hole. I don't think they can all derive from a common hole, but that would need a proof.
Genus/Holes Revisited (12Apr11)
A very late addition to the above idea. I now think that if we have an odd cycle in the conflict graph, the complex must be genus ≥ 9 (!). Which would mean we've established 3-colorability for genus ≤ 8. This is very tentative, but a significant advance on what's known...
(14Apr11). I thought about this a bit more, and I remain convinced that the above is true:
- Starting from any brick x, use the paint-spreading algorithm to mark all cells with their distance from x.
- Form the conflict graph where any two adjacent bricks with the same distance d from x are in conflict.
- If the conflict graph is empty, then we can just use the parity of the distances to 2-color the complex.
- If the conflict graph has no odd cycles, then we can 2-color each component of conflicts using party and the 3rd color to resolve clashes.
- If the conflict graph has an odd cycle, it must be of length ≥ 9.
- This implies (through some version of the reasoning we've been discussing) that the complex must have genus ≥ 9.
- Therefore, any complex with genus ≤ 8 is 3-colorable.
The "Couch" 9-cycle (14Apr11)
I was thinking about proving that the shortest odd cycle has nine bricks (Micaela's question), and although I did not see a knock-out proof, I did find a somewhat different looking 9-cycle. Note that it really is still a hole in some sense, and it still cannot be filled in. But it is a bit unsettling, because it doesn't look like a hole. If we want the surface of our complex to be a 2-manifold, then this is illegal. But we've never excluded such objects.
Blocking Odd Cycles
Our Result re Even Cycles is known
It turns out that our discovery re even cycles is a known theorem in graph theory. A graph is bipartite, which is equivalent to being 2-colorable, if and only if it contains no odd cycle:
- Diestel Graph Theory Prop. 1.6.1, p.17-18.
JOR Notes after Wed 9 Mar 11 Meeting
After surveying the possible directions ahead, we concentrated on reductions. The general idea is to assume irreducible complexes can be 3-colored (or, perhaps, do not even exist!), and to find reductions that, under that hypothesis, guarantee 3-coloring when the reduction is reversed. There are two clear reductions:
- Any brick of degree ≤ 2 can be reduced. This is because, after reduction, and 3-coloring the remainder by induction, the reduced brick can be reattached using the unused 3rd color.
- This one is more complicated. We worked it out in the meeting. Let me try calling it duplicate 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 reduced:
- R should be exposed on one side, that is, no bricks are attached to one side of R.
- To the other side of R, all the bricks are duplicated in the adjacent layer.
The reason this second reduction works is that, after removal of R, 3-color the remainder by induction, put back R, choosing to color every brick color c+1 if the brick under it is colored c. We determined that, alas, this reduction does not work when R is not exposed, i.e., when it is in the middle of a complex. But when R is exposed, the constraints come only from one side, and the 3-coloring works.
Micaela's Conjecture. Micaela came up with a strong hypothesis. Let C be a complex. First, fill in every hole that can be filled in, by adding bricks. (It might not be easy to define precisely this "filling-in," but let's ignore that for now.) Call this new complex C_{f}. Micaela's conjecture is that our two reductions suffice to reduce C_{f} to the empty complex (which would imply 3-coloring).
I see two tasks in front of us:
- Try to find a counterexample to Micaela's Conjecture. If we cannot, that is good news. If we can, that will add further insight. Either way we advance. (12Apr11): We have found a counterexample to the strict form of this conjecture. See the Reductions page, for thickness-2 and thickness-3 counterexamples. This is not the last word, but just wanted to record this.
- Try to identify a "stringy" class of complexes for which the two reductions are guaranteed to reduce to the empty complex. This is Stephanie's idea. This would give us a result for this class of complexes, for 3-coloring would be immediate. We did not come up with geometric conditions to nail down this "stringy" class of complexes. Emily's example above is in the class, however we define it.
- Here is a try, harking back to an idea I had several weeks ago. Define a complex to be stringy if no where in the complex does a 2x2 pattern of four bricks glued together occur (in any coordinate plane). I believe(?) Emily's example satisfies this condition. This condition is surely too restrictive, as Emily pointed out today, but it may be a place to start.
- So there are two challenges here: (1) Prove that every stringy complex under this definition can be reduced to emptiness by our two reductions. (2) Think of another, broader definition for "stringy" that encompasses a wider class but is still reducible to emptiness (assuming the first definition of stringy leads to reducible complexes.)
One cool thing I just realized as I am writing this is that our reductions are defining a notion of shellability of complexes, an interesting topic in topology that I have worked on before, and of continuing interest today. This connection enriches this approach for me.
Concerning proving that a string complex (maybe that's a better term) can always be reduced, my preliminary explorations (Rawia's cubes really come in handy here!) have been unsuccessful in constructing a irreducible string complex. Trying to keep every node of degree ≥ 3 while avoiding 2x2 patterns seems difficult if not impossible. So this is hopeful.
Notes for a proof that every string complex is reducible
Assume to the contrary that there is a string complex C that is irreducible. Then every box must have degree ≥ 3, and there can be no 2x2 pattern of boxes in any coordinate plane.
Look at the top of the complex. Let b be a top brick, that is, a topmost brick: none is higher in the z direction.
The first observation is that b must be adjacent to ≥ 2 distinct top bricks. This is because a degree-3 box b must have two other boxes glued to it at that z-level, because there are only two possible patterns, which I'll call X and T. (X is not the greatest name, but...)
Now, because the collection of bricks at the top z-height is finite, each of the top bricks must lie in a top-level cycle. Because suppose otherwise. Then a brick is dangling in a top-level tree (trees have no cycles). Go to a leaf of that tree. It needs two neighboring boxes. But then it is not a leaf; leaves have degree 1.
Now I want to identify an extreme and minimal cycle γ in the top layer. Extreme in the sense that γ touches the bounding box of the top bricks. Minimal in the sense that there is no cycle nested inside γ.
The argument is unfinished, but I would like to claim that γ forces a 2x2 pattern of boxes, which is a contradiction that would establish the claim. It seems to force a 2x2 pattern in a vertical plane: two boxes of γ, and two underneath. But there are cases and cases, and I feel I have built quite a teetering proof structure...
MRM Notes after Thur 10 Mar 11 Meeting
We mainly discussed the structure of our presentation and which topics we'd like to include. Here's the rough outline:
- Definitions:
- (JOR): Although this is logically first, to start with definitions is deadly. Skip this, and integrate it later.
- 2D and 3D rectangular bricks
- Structures built from bricks (a.k.a. "complexes")
- Even/odd cycles (maybe mention dual graphs?)
- Background:
- 4-color theorem
- (JOR): Yes! Start with this. Well known, but perhaps not precisely known. There are 4-colored maps of the US. That could be the slide here: Wikipedia 4-color map of U.S.
- (JOR): I would follow this immediately with the Sibley-Wagon 3-coloring of parallelograms, just by a picture (in my PowerPoint, far above), to show the key point that: geometry matters. Initial PowerPoint Presentation, Jan 2011
- (JOR): So that might constitute the first two slides: The U.S. map 4-colored, and the Wagon Penrose tiling 3-colored. And then you talk around those two....?
- Theorem: whole-edge to whole-edge complexes of 2D bricks are 3-colorable
- Extension of this proof to suggest that 3D complexes are 4-colorable.
- (JOR): Maybe this is the only proof that should be presented? The proof that complexes in 3D are 4-colorable. Find a topmost, rightmost corner brick. Remove it, color the remainder by induction, then put back. It only has three neighbors, so we can choose a 4-th color. This is our generic proof structure, so we should present it somewhere, and here seems the best?
- (JOR): I would emphasize (somewhere!) that because we get a 2-colorablity result for arbitrary dimensions, there is every reason to believe that a 3-colorability result would hold independent of dimension.
- No examples that require 4 colors, so we hypothesize that 3 colors suffice.
- 4-color theorem
- Our work:
- Theorem: structures (in any dimension) that contain no odd cycles are 2-colorable (mention that we wrote our own proof before learning that this was already a theorem in graph theory).
- How do we break all odd cycles? (Background: set domination)
- Key point: Theorem: find a set B of bricks that breaks all odd cycles such that no two bricks in B are adjacent, remove B, 2-color remaining complex, replace B and color it using the third color. Possible to find B with minimum cardinality.
- How do we find the smallest B? Or any B?
- Emily's example (talked about this today): in 2D, count up all holes, and then find the bricks that are touching the most holes. Can represent this using a tree; minimization problem becomes straightforward. (Stefanie will post a picture of this over the break).
- Three dimensions: counting holes is NP-complete (am I remembering this correctly, Joe?). In fact, finding B at all is difficult.
- (JOR:) I believe the result is that finding a minimal transversal is NP-complete, where a transversal is a set B but without our restriction of nonadjacency. I don't think that just finding some transversal could be difficult, but finding the best is. Adding in our nonadjaceny condition takes us out of all the literature on this topic. That seems peculiar to our brick complexes.
- Incidentally, it is called a "transversal" because a line that hits a collection of objects (points) is called a transversal of those objects. Our B is hardly a line, but it is a thing that hits a collection of objects, in our case, odd cycles.
- (JOR:) I believe the result is that finding a minimal transversal is NP-complete, where a transversal is a set B but without our restriction of nonadjacency. I don't think that just finding some transversal could be difficult, but finding the best is. Adding in our nonadjaceny condition takes us out of all the literature on this topic. That seems peculiar to our brick complexes.
- Theorem: Paint-spreading algorithm and the conflict graph.
- (JOR): I think this might be phrased as follows. The paint-spreading algorithm labels every brick with a number, a distance from the paint origin. A coloring algorithm follows: Change every odd distance label to color 1, every even distance label to color 2. This is a 2-coloring except for the conflicts where it fails: conflicts between adjacent bricks that get assigned the same distance from the paint-spreading origin. Now the plan is to "resolve" or "repair" the conflicts by using the 3rd color. This seems to work in almost all circumstances, but ....
- Emily's example: what if the conflict graph is an odd cycle?
- Hypothesis: we can always find some starting brick in the complex so that none of the conflict graphs will contain an odd cycle. Requires further investigation.
- Additional work (depending on how much time we have left for the presentation):
- Method of reductions: (1) fill in any holes, if possible, (2) remove all bricks of degree ≤ 2, (3) collapse layers. Repeat until no further reduction is possible. Conjecture: complex either reduces to zero, or is 3-colorable.
- (JOR 14Mar): Incidentally, I have tried to find a counterexample this conjecture, unsuccessfully. The notion of "filling-in" is not so clear, but when it is clear, it makes a difference.
- (JOR 12Mar): I agree, this should be "future work," although I hope we will have settled aspects of it before the talk!
- Method of reductions: (1) fill in any holes, if possible, (2) remove all bricks of degree ≤ 2, (3) collapse layers. Repeat until no further reduction is possible. Conjecture: complex either reduces to zero, or is 3-colorable.
I'm going to work on setting up a general arc for the slides in beamer, and then I'll email a draft of the presentation (or post it on the wiki) so others can make it look prettier. Let me know if anyone thinks there's anything we should talk about that isn't mentioned here.
Reductions
Link to new page on Reductions. (Created 21Mar11)
Final Paper
Link to new page on Final Paper. (Created 20Apr11)