Processing math: 100%

Tuesday, November 19, 2013

Interesting Arguments


An interesting line of reasoning that I came across in my Combinatorial Theory  course is
the minimal element method.

The general outline of a proof using this method is as follows : Suppose you want to prove that a given set of elements satisfy a given property P. Let the set of bad elements not satisfying that property be denoted by \mathcal{B}. Assume that b is the minimal element of \mathcal{B} in some sense. Then using the assumptions of the claim, show that there exists  another element b^\prime \in \mathcal{B} such that b^\prime < b.

Another interesting style of argumentation which is generally seen in information theoretic arguments is the probabilistic method in which a deterministic solution to a given problem is shown to exist by constructing a random candidate for a solution, and showing that this candidate solves all the requirements of the problem with positive probability.

No comments:

Post a Comment