Let be a finite, simple, undirected graph. Hadwiger’s conjecture states that
if then is a minor of .
Let’s call that statement (Hadw). We show that it is equivalent to the following statement:
(Hadw’): If is not a complete graph, then there is a minor of such that
- , and
It is clear that (Hadw) implies (Hadw’). For the other direction, take any finite graph and let . If is complete, we are done. If not, use (Hadw’) and let be a proper minor such that . If is complete, we are done, otherwise use (Hadw’) again to get a proper minor of with . And so on. Since is finite, this procedure is bound to end at for some . We
have , and since the procedure ended at , the graph must be complete. So we get statement (Hadw).
Here is something that I was certain would have an easy-to-prove positive answer; but it turns out that there is an exceedingly simple counterexample.
Let be the first infinite ordinal; its successor is .We consider a map , or put differently, a -Matrix of real numbers.
We assume that has the following properties:
(1) For all we have , or more informally, we have “convergence to the right”.
(2) For all we have , or more informally, we have “convergence to the bottom”.
(3) , or more informally, the right-hand entries of converge to the bottom right element .
Question: Does this imply that , that is, do the bottom entries of also converge to ?
Answer: There is, surprisingly (to me, at least) an easy example showing that the answer is No. Let be defined by if and otherwise. It is easy to verify that (1), (2), (3) above are satisfied. Note that the right-hand entries are all 0, and they trivially converge to ; but we have for all therefore .
For the kind of two-dimensional convergence we are looking for we need some form of “simultaneous” convergence (conceptually related to uniform convergence), which I might address in a later post.