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.
These days we hear about medians of all kinds of things: household income, lifetime of items such as lightbulbs, and so on. It’s time to get a rigorous grip on the concept.
Definition. Suppose is a set, a totally ordered set, and a function. Then is said to be a median of if the sets and have equal size.
It is a reflex of mathematicians to ask about existence and uniqueness of any concept they stumble upon. (Note that I wrote “a median” and not “the median” above.) Indeed, as much as the definition above seems to make sense: Even for simple example, the median needs not exist. Let and let be defined by and . Then has no median according to the definition above. On the other hand, if and is the inclusion map, then every element of the open interval is a median!
There are many common fixes to the problems of existence and uniqueness, but no definition is really elegant. (Most resort to listing the elements in ascending order and to pick the arithmetical middle of the “middle elements” in the list or something similar.)
Other difficulties arise when we want to pick medians of infinite sample sets. Let be a totally ordered set. We say that is a median of if the sets and have equal cardinality. Note that in every element is a median, but has no median at all!