User ross churchley - MathOverflow

Answer by Ross Churchley for Are there any non-planar graphs containing only K(3,3) as a subgraph that are not 4-colourable?

2012-10-26T18:23:42Z

There are a couple different answers to this question, depending on what question you're actually asking. You talk about a copy of $K_{3,3}$ to "assert their non-planarity," but it's unclear whether you mean this in the context of Kuratowski's Theorem (a graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3}$) or Wagner's Theorem (a graph is planar if and only if it does not contain $K_5$ or $K_{3,3}$ as a minor).

In general, subdivisions and minors are very different things: there are graphs, like the Petersen graph, which have no $K_5$ subdivision but do have a $K_5$ minor.

As Agol points out, there is a major conjecture – Hadwiger's conjecture – that claims every $K_k$-minor free graph is $(k-1)$-colourable. It's a very difficult open problem, but has been proved for the cases $k\leq 6$. In particular, your question (if you're talking about minors) is about the case $k=5$: Wagner proved way back in 1937 that this is equivalent to the Four-Colour Theorem. Since the Four-Colour Theorem is true, we can conclude that every graph with no $K_5$-minor is $4$-colourable.

What about forbidding $K_5$-subdivisions? As I mentioned above, this could have a different answer, because the class of graphs with no $K_5$-subdivision is strictly larger than the class of $K_5$-minor-free graphs. As it turns out, Hajos made a parallel conjecture in the 1940's: he suggested that every graph with no $K_k$ subdivision is $(k-1)$-colourable. However, Hajos' conjecture is false for $k\geq 7$; in fact, Erdős and Fajtlowicz showed that it fails for almost all graphs. Your question (if you're talking about subdivisions) again relates to the case $k=5$, which is actually still open. So it might be the case that every graph with no $K_5$-subdivision is $4$-colourable, but we just don't know!

For more information on these problems, see Toft's survey on Hadwiger's Conjecture (Congressus Numerantium 115 p. 249--283, 1996).

Cops and drunken robbers

2011-03-11T05:21:51Z

Consider a game of cops and robbers on a finite graph. The robber, for reasons left to the imagination, moves entirely randomly: at each step, he moves to a randomly chosen neighbour of his current vertex. The cop's job is to catch the robber as quickly as possible:

How do we find a strategy for the cop which minimizes the expected number of steps before she catches the robber?

If I'm reading this paper correctly, the minimum expected catch time is finite even if the graph is not cop-win. [Edit: as mentioned in the comments below, the cop and robber will never meet if they move at the same time and are in opposite parts of a bipartite graph. Provided this is not the case, I think the paper's argument can be modified to show that the expected catch time is finite. If the cop and robber take turns, there is no need for an additional assumption and the paper can be used directly. I'd be interested in either setup.] For example, chasing a robber around the cycle $C_n$ gives an expected catch time of $$\sum_{k=0}^\infty\ k\cdot\frac{\binom{k}{d/2}}{2^k},$$ where $d$ is the initial distance between the cop and the robber. (Since the cycle has so much symmetry, it can be shown that this strategy is the best possible.)

I'm curious as to whether, for instance, the usual optimal strategy in a cop-win graph is optimal in this sense. I'm also interested in some generalizations of this problem (by giving weights to various things). But I don't know whether the basic problem is open, trivial, or somewhere in between, so I'll ask the catch-all question:

What is known about this problem?

Answer by Ross Churchley for On a special kind of graph connectig n point to n points.

2010-10-15T22:36:51Z

Let $G$ and $H$ be graphs. The graph $G\times H$, called the tensor, direct or categorical product of $G$ and $H$, has vertices $V(G\times H)=V(G)\times V(H)$, and has an edge between $(u, v)$ and $(u', v')$ whenever $u$ is adjacent to $u'$ in $G$ and $v$ is adjacent to $v'$ in $H$.

I believe you're describing the product $K_2\times K_n$. If we label each vertex by a pair $(i, j)$ where vertices in the same "parallel row" are assigned the same $i$, and vertices "in front of" each other are assigned the same $j$, then your description says that two vertices $(i, j)$ and $(i', j')$ are adjacent if and only if $i\not=i'$ or $j\not=j'$. Since two vertices in a complete graph are adjacent if and only if they are distinct, this is just the same adjacency conditions as in the definition above.

The categorical product is an incredibly useful (and well-studied) concept in the study of graph homomorphisms. Chapter 2 of Graphs and Homomorphisms collects a number of results relating to this product. There are many other product operations defined for graphs, which are useful in other contexts; I believe the book Product Graphs: Structure and Recognition has more on them.

Answer by Ross Churchley for NP-Hard solution question

2010-10-12T18:34:33Z

For concreteness, let's pick an NP-hard problem to talk about. Given a graph $G$, the 3-colouring problem asks: "can the vertices of $G$ be painted by three colours such that for any edge $uv$, $u$ and $v$ get different colours?" This is a decision problem --- its possible answers are "yes" or "no" --- but a "yes" answer can be certified by a proper 3-colouring.

Say you had a polynomial-time algorithm that found, for any input graph, a proper 3-colouring if one exists. Then your algorithm would solve the 3-colouring problem: it answers "yes" or "no" correctly, and even gives a nice certificate (or witness) of a "yes" answer. This would be enough to show that P=NP. It is not necessary to find all possible 3-colourings (indeed, there may be exponentially many of them).

Now, if you had some sort of "partial algorithm," which solves an NP-hard problem only for some specific instances, then this is not enough. For example, the 3-colouring problem can be easily solved for bipartite graphs, split graphs, and more. The reason for this is that the restriction of an NP-hard problem is not necessarily NP-hard.

Finally, just to elaborate on Jim's answer: many popular descriptions of NP-hard problems, like Travelling Salesman, don't sound like decision problems. But they are, really: they can be retranslated as a series of questions with yes or no answers (e.g. "does there exist a travelling salesman route of length at most $x$?").

Answer by Ross Churchley for Most harmful heuristic?

2010-10-03T03:28:54Z

Similar to Tom's answer,

a vector is a mathematical quantity with both a magnitude and a direction.

Useful for distinguishing between speed and velocity but little else. The above is a typical definition from a physics textbook I had on the shelf; here in British Columbia, vectors are introduced in high school physics but not high school math. By the time students get to linear algebra in first- or second-year university, it can be hard to convince them that a real number (much less a polynomial) can be a vector. Usually, you have to resort to "a real number does too have a direction: positive or negative" and even then they don't believe you because

a scalar is a mathematical quantity with a magnitude and no direction

and so if real numbers are vectors, how can they be scalars?

Don't even ask about function spaces.

Answer by Ross Churchley for Where can I find questions motivating important ideas in math?

2009-11-16T21:08:30Z

If you're interested in middle school/high school math education, I'm sure you already know about Dan Meyer's excellent blog dy/dan. In case you haven't, he shares (classroom-tested) lesson ideas and media under the label "What Can You Do With This?" (the individual posts are also tagged by subject area).

Answer by Ross Churchley for Alternatives to pi day

2009-11-06T05:37:38Z

For better or worse, Pi Day seems to be already fairly well established. I propose a modified Pi Day holiday 'weekend' which would aim to broaden its focus and break some of the stereotypes your question concerns, while cashing in on its 'name recognition'.

March 13. 313 is a twin prime and a palindrome, so there are plenty of ways we could go with this, although I can't think of any specific activities. It might be fun to kick off the festivities with an organized Trimathlon event - that is, some sort of grand scavenger-hunting, puzzle-solving, team competition.

March 14. Pi Day. I'd like to second the recommendation of Buffon's Needle related activities for this.

March 15 happens to be Leonhard Euler's birthday. As Mensen suggests, celebrating individual mathematicians helps humanize the discipline. Perhaps a famous-mathematican costume contest? Euler's contributions in particular are another source of activities; the video game Katamari Damacy is a great one to do with exponential growth.

EDIT: Removed a couple overly cynical remarks in the first paragraph expressing skepticism about whether alternatives would catch on with the general public.

Answer by Ross Churchley for Do good math jokes exist?

2009-11-04T04:26:18Z

Less of a joke than an observation, but...

I've always found it appropriate that online identity thieves are in the business of stealing ones and zeroes.

Answer by Ross Churchley for Text for an introductory Real Analysis course.

2009-11-04T04:07:01Z

I was introduced to real analysis by Johnsonbaugh and Pfaffenberger's Foundations of Mathematical Analysis in my third year of undergrad, and I'd definitely recommend it for a course covering the basics of analysis. I'm not sure if it's still in print (that would certainly undermine it as a text!) but even if it isn't, it would make a great recommended resource or supplementary text.

Comment by Ross Churchley

2012-10-27T17:58:24Z

Oops! I meant Hajos both times.

Comment by Ross Churchley

2012-10-26T18:26:21Z

@Algol Kuratowski's theorem actually characterizes planar graphs in terms of subdivisions; you're thinking of Wagner's theorem. As I explain in my answer, the distinction between subdivisions and minors is actually very important!

Comment by Ross Churchley

2011-03-14T00:49:13Z

Anyways, thanks! This problem seems to be really interesting and perhaps a little bit unpredictable (at least to me!). If nobody knows of any papers covering this problem, I might have to devote a big chunk of time to this once I'm done my thesis research.

Comment by Ross Churchley

2011-03-14T00:35:07Z

I see that your optimal strategy, along with the optimal strategy for cycles, has the cop always decreasing her distance with the robber (although you show that this isn't sufficient to describe the optimal strategy; the cop has to move to A, not D, if the robber moves to E). However, I think it's possible to construct examples where this isn't the case.

Comment by Ross Churchley

2011-03-14T00:25:24Z

Interesting! Well, you learn something new every day. I originally thought that this graph couldn't possibly be cop-win because of the $C_4$, but the "dismantlability" characterization of cop-win graphs relies on the robber being able to stay put. As you point out, the cop has a winning strategy on this graph when the robber is forced to move every turn.

Comment by Ross Churchley

2011-03-13T16:38:58Z

@Nick My curiosity is strongest in the case where the cop has to move every turn and only catches the robber when they occupy the same vertex. But to be honest, I'd be interested to hear about any work that has been done on any variation of this problem.

Comment by Ross Churchley

2011-03-11T16:53:49Z

@Anthony Quas For general graphs, I had been thinking of the cop and robber acting asynchronously; moving back and forth between the same two vertices has essentially the same effect as standing still. But I'd actually be more interested in synchronous movement, in which case we'd assume that the graph is either nonbipartite or the cop and robber start at an even distance apart.

Comment by Ross Churchley

2010-12-11T19:55:03Z

In order for a problem to be NP-complete or NP-intermediate, it has to itself be in NP. Do you have reason to believe this problem is in NP? I'm not entirely convinced that it's even computable...

Comment by Ross Churchley

2010-11-12T01:48:11Z

Man, I'm really going back and forth on this one. On the one hand, a StackExchange/MathReviews/arXiv/"errata-base" hybrid site sounds awesome. On the other hand, how would that even work?

Comment by Ross Churchley

2010-11-05T20:10:10Z

+1 because I see a lot of calculus/precalculus students struggling with elementary school math and --- regardless of how they got that way --- I'd love to have some resources to point them towards. I'll second Willie's suggestion as I'd hate for this useful question to be derailed by a debate over the source of student misunderstandings.

Comment by Ross Churchley

2010-10-21T04:21:39Z

I have no idea what you are trying to ask here. It is a basic fact of undergraduate algebra, however, that the identity of any group is unique. If by "zero" you mean "the identity in the group of integers under addition" --- though it's really unclear what you mean by zero here --- then there can be only one of them.

Comment by Ross Churchley

2010-10-21T03:51:55Z

For a similar reason, Munkres uses $a\times b$ instead of $(a,b)$ for an element of $A\times B$.

Comment by Ross Churchley

2010-10-15T23:48:36Z

D'oh! I guess we'll have to spin off his birthday as a separate holiday, and March 15th can be "Ross has to learn the order of the months day"...

Comment by Ross Churchley

2010-10-15T23:16:37Z

Abosolutely. In particular, it ensures that both projections $\pi_1: G\times H\rightarrow G$ and $\pi_2: G\times H\rightarrow H$ are graph homomorphisms. (A graph homomorphism, by the way, is an adjacency-preserving function $f$ between graphs: i.e. if $uv$ are adjacent, then $f(u)f(v)$ should be adjacent.)

Comment by Ross Churchley

2010-10-15T22:45:37Z

The skeleton of a polyhedron should be a planar graph, yes? But $K_{6,6}$ minus a matching still contains an induced $K_{3,3}$.