User austin mohr - MathOverflow

Does countable compactness imply local compactness in Hausdorff spaces?

2010-08-30T06:21:47Z

The question arose while comparing the notions of compactness, countable compactness, local compactness, and "Lindelofness" in Hausdorff spaces. It is straightforward to show that compactness implies any of the other properties. I found ready counterexamples (I will be glad to provide them if asked) for all but one of the other possible implications, namely the question of whether countable compactness implies local compactness. The paper "On Countably Compact Nonlocally Compact Spaces" by T. B. Rushing shows that, in general, countable compactness does not imply local compactness. The examples he provides, however, are not Hausdorff.

Answer by Austin Mohr for Locally compact Hausdorff space that is not normal

2012-11-12T20:38:05Z

Spacebook, a database-driven version of Steen and Seebach's Counterexamples in Topology, lists the following locally compact Hausdorff (i.e. T2) spaces that are not normal. (Some of these appear already in other answers.)

Deleted Tychonoff Plank

Open Uncountable Ordinal Crossed with Uncountable Cartesian Product of Unit Interval

Rational Sequence Topology

Thomas’s Plank

Answer by Austin Mohr for Non-enumerative proof that there are many derangements?

2012-10-12T06:47:44Z

L. Lu and L. A. Szekely have successfully applied the Lopsided (i.e. Negative Dependency Graph) Lovasz Local Lemma to this problem.

A negative dependency graph is as a dependency graph except that independence is replaced with the inequality $$ \Pr\left(A_k \mid \bigwedge_{i=1} A_i\right) \leq \Pr(A_i) $$ for any fixed event $A_k$ and collection $\{A_i \mid i \in [n]\}$ of non-neighbors of $A_k$. Erdos and Spencer showed the Lovasz Local Lemma holds with negative dependency graphs in place of dependency graphs.

Let $\Omega$ be the probability space of all perfect matchings of $K_{n,n}$ equipped with the uniform distribution. For a partial matching $M$ of $K_{n,n}$, define the event $$ A_M = \{M^\prime \in \Omega \mid M \subseteq M^\prime\} $$ (all perfect matching that contain the partial matching $M$).

Given a collection $\mathcal{M}$ of partial matchings of $K_{n,n}$, construct a graph with vertex set $\{A_M \mid M \in \mathcal{M}\}$ and set two matchings adjacent if their union is not again a matching. L. Lu and L. A. Szekely showed this graph is a negative dependency graph.

Finally we can address the problem at hand. Let the partite sets of $K_{n,n}$ be $\{1, \dots, n\}$ and $\{1^\prime, \dots, n^\prime\}$. For $1 \leq i \leq n$, let $M_i$ be the one-edge matching $ii^\prime$. Viewing perfect matchings of $K_{n,n}$ as permutations of an $n$-element set, the event $\bigwedge_{i=1}^n \overline{A_{M_i}}$ contains precisely those permutations not having a fixed point. Choosing $x_i = \frac{1}{n}$ for the purposes of the Lopsided Lovasz Local Lemma, we get $$ \Pr\left( \bigwedge_{i=1}^n \overline{A_{M_i}} \right) \geq \left(1 - \frac{1}{n}\right)^n, $$ which converges to $\frac{1}{e}$ as $n \rightarrow \infty$.

Interesting and Accessible Topics in Graph Theory

2011-05-10T02:43:58Z

This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope to use graph theory as a vehicle by which to convey a sense of developing "advanced" mathematics (remember, these students will have seen first-year calculus, at best).

What are you favorite interesting and accessible nuggets of graph theory?

"Interesting" could mean either the topic has a particularly useful application in the real-world or else is a surprising or elegant theoretical result. An added bonus would be if the topic can reveal gaps in our collective knowledge (for example, even small Ramsey numbers are still not known exactly). "Accessible" means that a bright, motivated student with no combinatorial background can follow the development of the topic from scratch, even if it takes several lectures.

Asymptotic Methods in Combinatorics

2011-05-25T20:28:18Z

What are good texts to acquaint oneself with standard asymptotic techniques, particularly as they relate to probabilistic combinatorics?

A Bijection Between the Reals and Infinite Binary Strings

2011-05-14T19:28:22Z

Whenever possible, I like to present Cantor's diagonal proof of the uncountability of the reals to my undergraduates. For simplicity, I usually restrict to showing that the subset $$ A = \{x \in [0,1) \mid \text{ the decimal representation of $x$ uses only 0's and 1's} \} $$ is already uncountable. I was thinking recently that it would be nice to add a quick proof that $A$ is actually of precisely the same cardinality as $\mathbb{R}$. That is, I would like to:

Demonstrate a bijection between $A$ and $\mathbb{R}$.

My first instinct was to use find an injection from $A$ into $\mathbb{R}$ and vice versa, then appeal to Cantor-Bernstein to say that a bijection exists (even if we don't know how to construct it). The identity map suffices from $A$ into $\mathbb{R}$. For the other direction, I thought of something like "for $x \in \mathbb{R}$, map $x$ to its binary representation, disregarding the decimal point". I'm afraid this function fails to be injective, however. For example, 1 (base 10) can be represented as $.\overline{1}$ (base 2), and so 2 (base 10) can be represented as $1.\overline{1}$ (base 2). Thus, 1 and 2 (base 10) will have the same image under my map.

Any methods (not necessarily the one I've attempted to start here) are most welcome. I will accept as "correct" the method which demonstrates the bijection with the greatest level of clarity.

Answer by Austin Mohr for Best online mathematics videos?

2011-05-11T19:22:10Z

Timothy Gowers' "The Important of Mathematics" never fails to instill a sense of purpose in my work, even when I feel I'm doing "useless" mathematics.

Answer by Austin Mohr for If you could redesign a high school mathematics curriculum from the ground up, what would you include?

2010-09-29T05:27:50Z

In a perfect world, students would be exposed to formal logic and elementary proof theory. How can one meaningfully critique any media if one cannot negate a proposition, argue by contrapositive, etc.?

Intuition on Log-Concave Sequences

2010-09-19T20:58:43Z

A sequence $(a_n)$ is said to be log-concave provided $a_i^2 \geq a_{i-1}a_{i+1}$ for all $i$.

What sorts of intuition can one have about log-concave sequences? In particular, what kind of "picture" does the property of log-concavity conjure up with regard to its graph?

What nice things happen when a sequence is log-concave? What are typical "next steps" after one has established the log-concavity of a sequence?

Any other comments related to getting a feel for log-concave sequences are most welcome.

Answer by Austin Mohr for Mul + div using only add/sub ?

2010-09-12T20:12:38Z

Division is repeated subtraction. Take 11 \div 3 as an example.

11 - 3 = 8. Increment the quotient by 1. Since 8 > 3, keep going.

8 - 3 = 5. Increment the quotient by 1. Since 5 > 3, keep going.

5 - 3 = 2. Increment the quotient by 1. Since 2 < 3, set the remainder to 2 and terminate.

I'll leave it to you to figure out the code.

Answer by Austin Mohr for About measurable sets and intervals

2010-09-11T22:40:11Z

I actually worked this problem out during my Measure Theory course a couple years ago.

http://www.austinmohr.com/Work_files/hw2_3.pdf

Therein, you'll find a construction of a Cantor-like set having any measure strictly between 0 and 1. As with the Cantor set, you cannot find an interval contained in this Cantor-like set.

I don't suggest you accept my solution without checking it yourself, as it was written by one still coming to grips with the material. It should give you a good idea of how to construct your proof, however.

Induction vs. Strong Induction

2010-09-07T03:22:48Z

Is there ever a practical difference between the notions induction and strong induction?

Edit: More to the point, does anything change if we take strong induction rather than induction in the Peano axioms?

Comment by Austin Mohr

2013-02-15T02:11:46Z

If you are indeed interested in just spanning trees of $K(m,n)$, then you may find more information at www.austinmohr.com/work (under "Master's Thesis"). Moreover, the algorithm used to enumerate the trees should be easy to adapt to counting any sort of subgraph, though the runtime will suffer. There is a polytime algorithm for determining isomorphism between trees, but there is not yet one for general graphs.

Comment by Austin Mohr

2012-11-22T20:37:13Z

If you start with the phrase "Rational Points on Atkin-Lehner Quotients of Shimura Curves" and remove all the words the medical student did not know, you are left with "Points on of Curves" - almost precisely what he echoed back to you. :)

Comment by Austin Mohr

2012-05-15T19:09:38Z

There is a searchable version of the table in the book here: www.austinmohr.com/spacebook.

Comment by Austin Mohr

2011-11-21T06:08:51Z

Surely a pending publication is better than none at all.

Comment by Austin Mohr

2011-08-14T01:48:29Z

If all you are interested in is computing their values, Maple has a package for this: maplesoft.com/support/help/Maple/…. Apparently they are computed via generating functions.

Comment by Austin Mohr

2011-08-12T06:32:53Z

Exact duplicate of math.stackexchange.com/questions/57017/…

Comment by Austin Mohr

2011-05-31T17:27:13Z

Your question was closed primarily because it is very difficult to read. Please consider writing it more carefully and resubmitting. Also, your question is probably more appropriate for math.stackexchange.com/questions.

Comment by Austin Mohr

2011-05-23T19:54:23Z

You should try this question at math.stackexchange.com, as it will inevitably be closed here.

Comment by Austin Mohr

2011-05-20T21:48:02Z

The fact that 2 + 1 = 3 is not an element of $X$ does not bother this definition since, in constructing $H$, we restricted our domain so that we don't care what $H$ does to the element 2.

Comment by Austin Mohr

2011-05-20T21:47:21Z

In practical usage, you usually just restrict yourself to $D$ and say that $D$ is closed under $H$ if every element of $D$ gets mapped back into $D$. This text appears to be allowing a more general usage of the word "closed" where you allow $X$ to contain some elements that are outside the domain and still say "$X$ is closed under $H$". For example, if you took $X = \{1, 2\}$, $D = \{1\}$, and $H(x) = x + 1$, this definition says $X$ is closed under $H$, since we are only allowed to check that 1 + 1 = 2 is indeed an element of $X$.

Comment by Austin Mohr

2011-05-20T05:17:38Z

@Joseph: I will certainly do so. Thanks for your interest.

Comment by Austin Mohr

2011-05-14T05:24:56Z

Thanks for the many great suggestions. Reading all these has caused me to think that I could potentially structure the course in such a way as to introduce the widest number of adjectives that can precede "graph theory" or "combinatorics". For example, I see in the topics presented here: enumerative, extremal, geometric, computational, probabilistic, algebraic, and constructive (for lack of a better word - I'm referring to things like designs). As a sort of subquestion restricted to the comments, what other adjectives might I attempt to incorporate?

Comment by Austin Mohr

2011-05-12T01:29:02Z

I started to call this "absorption", but that is not quite correct (absorption is a relationship between two operations). Still, perhaps that name will jog someone's memory.

Comment by Austin Mohr

2010-09-29T18:54:42Z

Be that as it may, a first course in mathematical logic does much to untangle knotted intuitions about what it means to argue. The number of students who cannot perform simple logical operations is astounding. Present an average high school student with the following scenario: "I claim that any time it is cloudy, it will also be rainy. What kind of evidence would prove me wrong?". In my experience, many will respond "A day when it's neither cloudy nor rainy." A student who cannot handle a situation when the solution IS clear-cut is certainly not ready for a non-mathematical setting.

Comment by Austin Mohr

2010-09-28T00:42:35Z

Sorry for the unintended bump. I meant only to test the rollback feature.