User ross churchley - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:41:47Z http://mathoverflow.net/feeds/user/785 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110337/are-there-any-non-planar-graphs-containing-only-k3-3-as-a-subgraph-that-are-not/110774#110774 Answer by Ross Churchley for Are there any non-planar graphs containing only K(3,3) as a subgraph that are not 4-colourable? Ross Churchley 2012-10-26T18:23:42Z 2012-10-27T17:57:42Z <p>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 (<em>a graph is planar if and only if it does not contain a subdivision of</em> $K_5$ <em>or</em> $K_{3,3}$) or Wagner's Theorem (<em>a graph is planar if and only if it does not contain</em> $K_5$ <em>or</em> $K_{3,3}$ <em>as a minor</em>).</p> <p>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.</p> <p>As Agol points out, there is a major conjecture – <a href="http://en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29" rel="nofollow">Hadwiger's conjecture</a> – 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.</p> <p>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 <em>false</em> 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!</p> <p>For more information on these problems, see Toft's survey on Hadwiger's Conjecture (<em>Congressus Numerantium</em> 115 p. 249--283, 1996).</p> http://mathoverflow.net/questions/58129/cops-and-drunken-robbers Cops and drunken robbers Ross Churchley 2011-03-11T05:21:51Z 2011-03-13T19:51:10Z <p>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:</p> <blockquote> <p>How do we find a strategy for the cop which minimizes the expected number of steps before she catches the robber?</p> </blockquote> <p>If I'm reading <a href="http://dx.doi.org/10.1109/SFCS.1979.34" rel="nofollow">this paper</a> correctly, the minimum expected catch time is finite even if the graph is not cop-win. <em>[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.]</em> 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.)</p> <p>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:</p> <blockquote> <p>What is known about this problem?</p> </blockquote> http://mathoverflow.net/questions/42332/on-a-special-kind-of-graph-connectig-n-point-to-n-points/42335#42335 Answer by Ross Churchley for On a special kind of graph connectig n point to n points. Ross Churchley 2010-10-15T22:36:51Z 2010-10-15T22:36:51Z <p>Let $G$ and $H$ be graphs. The graph $G\times H$, called the <a href="http://en.wikipedia.org/wiki/Tensor_product_of_graphs" rel="nofollow"><em>tensor</em>, <em>direct</em> or <em>categorical product</em></a> 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$. </p> <p>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.</p> <p>The categorical product is an incredibly useful (and well-studied) concept in the study of graph homomorphisms. Chapter 2 of <em><a href="http://www.cs.sfu.ca/~pavol/hombook.html" rel="nofollow">Graphs and Homomorphisms</a></em> 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 <em>Product Graphs: Structure and Recognition</em> has more on them.</p> http://mathoverflow.net/questions/41915/np-hard-solution-question/41930#41930 Answer by Ross Churchley for NP-Hard solution question Ross Churchley 2010-10-12T18:34:33Z 2010-10-12T18:34:33Z <p>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 <em>certified</em> by a proper 3-colouring.</p> <p>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 <em>witness</em>) 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).</p> <p>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.</p> <p>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$?").</p> http://mathoverflow.net/questions/2358/most-harmful-heuristic/40901#40901 Answer by Ross Churchley for Most harmful heuristic? Ross Churchley 2010-10-03T03:28:54Z 2010-10-03T03:28:54Z <p>Similar to Tom's answer, </p> <blockquote> <p>a vector is a mathematical quantity with both a magnitude and a direction.</p> </blockquote> <p>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 <em>not</em> 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 </p> <blockquote> <p>a scalar is a mathematical quantity with a magnitude and no direction</p> </blockquote> <p>and so if real numbers are vectors, how can they be scalars? </p> <p>Don't even ask about function spaces.</p> http://mathoverflow.net/questions/5545/where-can-i-find-questions-motivating-important-ideas-in-math/5736#5736 Answer by Ross Churchley for Where can I find questions motivating important ideas in math? Ross Churchley 2009-11-16T21:08:30Z 2009-11-16T21:08:30Z <p>If you're interested in middle school/high school math education, I'm sure you already know about Dan Meyer's excellent blog <em>dy/dan</em>. In case you haven't, he shares (classroom-tested) lesson ideas and media under the label "<a href="http://blog.mrmeyer.com/?cat=70" rel="nofollow">What Can You Do With This?</a>" (the individual posts are also tagged by subject area).</p> http://mathoverflow.net/questions/1270/alternatives-to-pi-day/4338#4338 Answer by Ross Churchley for Alternatives to pi day Ross Churchley 2009-11-06T05:37:38Z 2009-11-06T06:20:32Z <p>For better or worse, Pi Day seems to be already fairly well established. I propose a modified <strong>Pi Day holiday 'weekend'</strong> which would aim to broaden its focus and break some of the stereotypes your question concerns, while cashing in on its 'name recognition'.</p> <p><em>March 13.</em> 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 <strong>Trimathlon</strong> event - that is, some sort of grand scavenger-hunting, puzzle-solving, team competition.</p> <p><em>March 14.</em> <strong>Pi Day</strong>. I'd like to second the recommendation of Buffon's Needle related activities for this. </p> <p><em>March 15</em> happens to be <strong>Leonhard Euler's birthday</strong>. 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 <em>Katamari Damacy</em> is a great one to do with exponential growth.</p> <p>EDIT: <em>Removed a couple overly cynical remarks in the first paragraph expressing skepticism about whether alternatives would catch on with the general public.</em></p> http://mathoverflow.net/questions/1083/do-good-math-jokes-exist/4050#4050 Answer by Ross Churchley for Do good math jokes exist? Ross Churchley 2009-11-04T04:26:18Z 2009-11-04T04:26:18Z <p>Less of a joke than an observation, but...</p> <p>I've always found it appropriate that online identity thieves are in the business of stealing ones and zeroes.</p> http://mathoverflow.net/questions/4023/text-for-an-introductory-real-analysis-course/4047#4047 Answer by Ross Churchley for Text for an introductory Real Analysis course. Ross Churchley 2009-11-04T04:07:01Z 2009-11-04T04:07:01Z <p>I was introduced to real analysis by Johnsonbaugh and Pfaffenberger's <em>Foundations of Mathematical Analysis</em> 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.</p> http://mathoverflow.net/questions/110337/are-there-any-non-planar-graphs-containing-only-k3-3-as-a-subgraph-that-are-not/110774#110774 Comment by Ross Churchley Ross Churchley 2012-10-27T17:58:24Z 2012-10-27T17:58:24Z Oops! I meant Hajos both times. http://mathoverflow.net/questions/110337/are-there-any-non-planar-graphs-containing-only-k3-3-as-a-subgraph-that-are-not/110340#110340 Comment by Ross Churchley Ross Churchley 2012-10-26T18:26:21Z 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! http://mathoverflow.net/questions/58129/cops-and-drunken-robbers/58356#58356 Comment by Ross Churchley Ross Churchley 2011-03-14T00:49:13Z 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. http://mathoverflow.net/questions/58129/cops-and-drunken-robbers/58356#58356 Comment by Ross Churchley Ross Churchley 2011-03-14T00:35:07Z 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. http://mathoverflow.net/questions/58129/cops-and-drunken-robbers/58356#58356 Comment by Ross Churchley Ross Churchley 2011-03-14T00:25:24Z 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 &quot;dismantlability&quot; 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. http://mathoverflow.net/questions/58129/cops-and-drunken-robbers Comment by Ross Churchley Ross Churchley 2011-03-13T16:38:58Z 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. http://mathoverflow.net/questions/58129/cops-and-drunken-robbers Comment by Ross Churchley Ross Churchley 2011-03-11T16:53:49Z 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. http://mathoverflow.net/questions/49056/is-pattern-recognition-np-complete Comment by Ross Churchley Ross Churchley 2010-12-11T19:55:03Z 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... http://mathoverflow.net/questions/3038/errata-database/45769#45769 Comment by Ross Churchley Ross Churchley 2010-11-12T01:48:11Z 2010-11-12T01:48:11Z Man, I'm really going back and forth on this one. On the one hand, a StackExchange/MathReviews/arXiv/&quot;errata-base&quot; hybrid site sounds awesome. On the other hand, how would that even work? http://mathoverflow.net/questions/44983/resources-for-teaching-arithmetic-to-calculus-students Comment by Ross Churchley Ross Churchley 2010-11-05T20:10:10Z 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. http://mathoverflow.net/questions/43000/since-there-is-more-than-one-notion-of-nothing-why-is-there-only-one-zero-axiom Comment by Ross Churchley Ross Churchley 2010-10-21T04:21:39Z 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 &quot;zero&quot; you mean &quot;the identity in the group of integers under addition&quot; --- though it's really unclear what you mean by zero here --- then there can be only one of them. http://mathoverflow.net/questions/42929/suggestions-for-good-notation/42984#42984 Comment by Ross Churchley Ross Churchley 2010-10-21T03:51:55Z 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$. http://mathoverflow.net/questions/1270/alternatives-to-pi-day/4338#4338 Comment by Ross Churchley Ross Churchley 2010-10-15T23:48:36Z 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 &quot;Ross has to learn the order of the months day&quot;... http://mathoverflow.net/questions/42332/on-a-special-kind-of-graph-connectig-n-point-to-n-points/42335#42335 Comment by Ross Churchley Ross Churchley 2010-10-15T23:16:37Z 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.) http://mathoverflow.net/questions/42332/on-a-special-kind-of-graph-connectig-n-point-to-n-points Comment by Ross Churchley Ross Churchley 2010-10-15T22:45:37Z 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}$.