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