Discrete Structures: Two-way Bounding Margaret Fleck, University of Illinois

Two-way bounding is the technique of bounding a quantity from both the upper and lower sides. In engineering applications, the quantity is frequently not known exactly, so we're determining the range in which the right answer might live. In pure math, it is a standard way to prove that two quantities are equal. So standard, in fact, that I've heard a story involving an excessively difficult qualifying exam in which students wrote out the two halves of a bounding proof mechanically before thinking about the problem in enough detail to realize how much trouble they were in.

This method seems relatively easy to instructors. However, a frequent mistake at the beginner level is to do only one half of the proof. In traditional presentations of discrete math and CS theory, this tends to happen when proving identities for set operations or when proving what language a grammar or automaton recognizes. Students make related mistakes interpreting big-O notation for algorithm running times. In that case, the bounding is typically only from the upper end because a lower bound tends to be either obvious or (e.g. P = NP) not available.

Several problems underlying inability to use this method:

• Not appreciating why it can be helpful to break up a proof this way.
• A belief that upper and lower bounds must be tight or, at least, not too far from the exact answer.
• Uncertainty about whether it's legitimate for a proof step to lose information, i.e. there is only a one-way implication at that point in the proof.
• Lack of fluency with proving an inequality, including both numerical inequalities and abstract ones such as subset inclusion.

The root cause is undoubtedly the strong emphasis on equalities in later high school and early college math courses, especially since proofs were removed (perhaps for good reason) from most calculus sequences.

Teaching one-way bounding

Exercises on one-way bounding are scattered throughout the textbook and lecture sequence. Early in the term, we discuss the fact that implications (if/then statements) may be true in only one direction. It's helpful to include numerical examples involving a significant truth gap, e.g. "If \(|x| < 3\), then \(x^2 < 100\)", to force them to think about the issue. I also include simple example proofs that conspicuously lose information in one step. Again, it's best to use familiar algebraic manipulation and have a step that will not seem legitimate to students who are confused about this point. Simple proofs involving inequalities appear in the middle section of the course, along with explicit discussion of upper and lower bounds. Somewhat difficult inequality proofs appear towards the end.

This course emphasizes constructing proofs starting from both ends and working towards the middle. One motivation for this method is claims involving algebraic inequalities. When working forwards from the start of the proof, no reasonable person considers a step that loses information. Those steps are written into proofs because the author has sketched out the later parts and knows what inequality will be required to reach the conclusion at the end.

Students are not familiar with the classic method for proving a subset inclusion, i.e. pick an element from the smaller set and show that it lives in the larger set, and they are somewhat resistant to learning it. Therefore, it's important to present this proof technique on its own, proving a one-way inclusion, rather than immediately asking them to use two copies of the method to prove a set equality. It's also helpful to use sets with concrete definitions, for which the smaller set is obviously not equal to the larger one.

When teaching proofs, it's important to use examples where the middle of the proof involves some actual work, e.g. several lines of algebra. This helps them feel that there is a point to building the proof, because the conclusion isn't obvious. To construct elementary but non-trivial proofs of set inequality, define one of the two sets as the union or intersection of two other sets.

Teaching two-way bounding

Once they are somewhat familiar with one-way bounds, we need to teach them how to constrain a value by bounding it from both directions. For this, I rely heavily on graph coloring. In and of itself, graph coloring is interesting but not required core material for a course at this level. However, four properties make it an excellent teaching example for this concept:

• It is very concrete, so students can feel confident about why the right answer is right.
• It's easy to create many examples for practice and exams.
• The correct answer is frequently not obvious, so their proof seems to have accomplished something rather than just being symbol pushing.
• The upper bound is proved using methods completely different from the lower bound.

The potential for using different methods for the upper and lower bounds is one reason the two-way bounding method is so powerful. When we can use the same method in both directions, as in most proofs of set identities, it's tempting (and sometimes even correct) to merge the two halves. In graph coloring, the upper bound is proved using a specific coloring of the graph. We usually prove the lower bound by finding a subgraph with a known chromatic number (e.g. a complete or wheel graph).

Lectures use some other motivating examples, notably packing problems (aka marker making). However, these typically involve complexities (e.g. geometry) that make them less suitable for homework and exams.

Graph coloring returns as a handy example when we discuss NP completeness late in the course. It's a really nice example of why it's so annoying that we don't know if P and NP are equal. Graph coloring strikes many people as a problem that should have an efficieint general algorithm, perhaps using a limited set of special graphs similar to the proof of the four-color theorem. So it's mysterious in just the right way that the details feel just slightly out of reach.