Equivalence of seven major theorems in combinatorics
PDF
Abstract
The seven following theorems, while seemingly unrelated, are equivalent (i.e., any one of them may be proved by assuming any other is true). These theorems relate to graph theory, set theory, flow theory, and even marriage: Menger's theorem (1929), Kőnig's theorem for matrices (1931), the Kőnig-Egeváry theorem (1931), Hall's marriage theorem (1935), the Birkhoff-Von Neumann theorem (1946), Dilworth's theorem (1950) and the Max Flow-Min Cut theorem (1962). I will attempt to explain each theorem, and give some indications why all are equivalent.
Well Ordering theorem
The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.
Well-ordering theorem: Every set is well-orderable.
Lifting the exponent
A nice and tricky lemma (lifting the exponent) Santiago Cuellar, Jose Alejandro Samper
Lambert w function
Keith Conrad
1. Introduction
The method of differentiation under the integral sign, due to Leibniz in 1697 [4], concerns integrals depending on a parameter, such as $\int_{0}^{1} x^2 e^{-t x} \mathrm{~d} x$. Here $t$ is the extra parameter. (Since $x$ is the variable of integration, $x$ is not a parameter.) In general, we might write such an integral as \[\tag{1.1} \int_{a}^{b} f(x, t) \mathrm{d} x, \] where $f(x, t)$ is a function of two variables like $f(x, t)=x^2 e^{-t x}$.Discrete poisson equation
The discrete Poisson equation is the finite difference analog of the Poisson equation. In it, the discrete Laplace operator takes the place of the Laplace operator. The discrete Poisson equation is frequently used in numerical analysis as a stand-in for the continuous Poisson equation, although it is also studied in its own right as a topic in discrete mathematics.
188 post articles, 21 pages.