Home

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.

Read more

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.

Read more

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}$.

Read more