This can be done by mistake: you might use a "well known" property B to prove property A, but the proof of B actually relies on knowing A is true.
Note that it is sometimes ok to assume something similar but weaker than what you're trying to prove, for instance with proof by induction.
Claiming that certain steps are obvious or simple facts, when they are actually just as difficult to prove as the main result.
Technically in a proof one can rely on extremely complicated results, as long as they are properly described and cited. In an introductory course (like one where you learn about proof techniques) you should avoid doing this, unless you're relying on something that has already been proved during the course, or is basic enough to be considered prerequisite material.
Making assumptions.
Example: assuming that a set of numbers are integers, when the statement to be proved made no such restriction.
In general, don't interpret problems in a way that is convenient to get a simple solution. For example, if I say "you have a deck of n cards", don't assume n=52 just because that's what a standard deck has. And of course,
don't do this.
Using results that are not applicable in the given situation.
This is like "making assumptions" without knowing about it. It typically arises when one hasn't really understood what they're relying on, specifically when one hasn't understood what assumptions were made to obtain the result they're relying on. One such example is that students often state as a fact that hashing always takes constant time.
Also, "proof by picture". For instance, I ask you to prove a property about planar graphs. You draw a planar graph, assume it is general enough, show the property is true, and incorrectly conclude that the property holds in general.
Make sure that your claims hold in general, not for specific situations.
Not defining things.
Not quite as bad, but still something to avoid: defining things and then not using them.
Not labeling things.
Often a proof will end up referring to something, like "therefore it is equal to 3", where "it" was actually last referred to about 10 lines and 5 sentences ago. This could be avoided by giving "it" a name.
It doesn't help to be more specific about "it" by saying "that object that I was talking about ten lines above".
Not simplifying (see section on logic as well).
For example, you have a case analysis proof with several cases, but many of those cases could have been eliminated. A typical situation might be: "Case 1: If A is true and B is true, do C. Case 2: if A is true and B is not true, do C."
Basically, writing a whole lot without getting to the point, or purposely fitting in lengthy complicated math to hide the fact that a crucial step is missing somewhere.
Scheinerman: 5(29). Note that the definitions for big-O and big-Omega differ slightly from mine. I assume that functions are positive, which is quite standard for CS.
Rosen: 3.2
CLRS : 2, p.43-52. This textbook is consistent with how I define things.
Recurrence relations using big-O
Prerequisite knowledge: sections 3B and 7. Geometric series.
Class notes:
full
slideshow
and
condensed (the beginning of these notes are tied to Mergesort, you can ignore this and begin at "How to solve...")
Video (to be updated in the context of discrete math; low priority)
My slideshow with audio describing mergesort and setting up its recurrence. This is just to give some context to the recurrence relation solved in the following links.
My lecture on how to solve recurrences:
part 1
and part 2. (45 min. total)
"Sim" (wiki) is a game where 2 players take turns
coloring the edges of K6. One player uses red and the other uses blue. Whoever completes a
triangle of their own color loses. An extended version of the game asks two players to color
K18, while avoiding coloring a monochromatic K4. There is a 3-player
version as well. Ramsey theory tells us that these games cannot end in a draw.
A variant of sim is Hajnal's triangle-free game, discussed
here.
Two players take turns adding edges, with the restriction that neither can complete a triangle. However, there are no
colors in this game. A player wins if the other player cannot add an edge.
The game can also be played using a score that
is just the total number of edges added. The goal of one player is to maximize the score, and the goal of the 2nd
player is to force a configuration where no edge can be added, as quickly as possible. Finally there is also a variant
with an additional constraint, where the graph must remain connected at all times.
The formula V-E+F=2 is just a particular case of a far greater body of work. As mentioned in class,
if you were to draw a connected graph on a sphere, you'd get the same relation;
The Euler characteristic would be 2.
Similarly, count the vertices, edges and faces on any convex
polyhedron. Other surfaces
have
other characteristic numbers.
The role of K5 and K3,3
The wiki on planar graphs starts out by mentioning the theorems of Kuratowski and Wagner,
which essentially say that a graph G is non-planar if and only if the shape of a
K5 or of a K3,3 is present in G.
See here.
Look at the two figures, showing two (non-planar) graphs not directly containing a
K5 or a K3,3, but that implicitly contain those shapes.
The section that follows in the wiki discusses other planarity criteria. Theorem 1 in particular is quite simple, and easy to prove.
(advanced) notes on Kuratowski's theorem.
The advanced part is proving that any graph not containing K5 or K3,3 as a subgraph -- or as a minor -- must be planar. In other words, non-planarity implies finding such a subgraph/minor.
In our class we only discuss the other direction: i.e., that containing one of those subgraphs implies non-planarity.
Hadwiger-Nelson problem: This is an awesome vetex coloring problem, with an infinite number of vertices: all points in the plane. It is explained nicely in this
wiki.
Edge coloring
The idea here is to color edges of a graph, so that no vertex is incident to 2 edges of the same color.
Of course, you must minimize the number of colors used.
wiki.
Besides the sections on the basic problem, look at section 7.4 ("near matches"). This concerns the third bet mentioned in the notes.
Also note that section 7.6 deals with the average number of people you have to ask, to find a birthday match. It is a bit higher than 23. This is discussed in the section on IRVs (14-D).
Somewhat related:
If we record birthdays of people queried iteratively (say, on the street; we won't run out of people to ask), how many people do we expect to ask before recording all possible birthdays?
This is known as the
Coupon Collector's Problem. Here, we have n "coupons". The answer is Theta(nlogn).
Various numbers in the universe. Near the very bottom of the table, you'll find 1080, the estimated number of particles in the universe.
Jump to the 30:00 mark in this youtube video,
which is part of Harvard's
Stat 110 course. This part of the lecture lasts 9 minutes.
After that is an explanation of the St. Petersburg paradox which is fun to think about.
Here's the wiki on that.
Counting inversions in permutations. (involves IRVs with 2 subscripts)
Look at problem 2 in this
homework set
from a course at WVU. This follows the hat check problem. Problem 3 is not related to IRVs, but is interesting.
A birthday problem. (involves IRVs with 2 subscripts)
The 2nd example in this
link
is a variant of our good old birthday problem. I discuss this and one more variant
here.
A problem with balls and bins.
See the second example in this link.
Evaluation of the expected value of each IRV is a bit more complicated in this example than in previous ones.
Note that the first example in this link is equivalent to the hat check problem. It deals with fixed points in permutations.
In a permutation of the integers 1...n, a fixed point occurs when integer k is placed at position k.
More fun with probability (no course notes required)
CLRS -- Introduction to Algorithms, 3rd edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
As the name suggests, this is a book on Algorithms, which is a topic that relies heavily on Discrete Math. It is not a discrete math book, but a few of the topics on this page are covered briefly in CLRS (some in the appendix, some in regular chapters). CLRS is the primary suggested textbook for my Algorithms course.
