December 2002 - mathfun@mailman.xmission.com

Re: [math-fun] Square (& other) chains and necklaces.
by asimovd＠aol.com 03 Dec '02

03 Dec '02

Edwin Clark asked: << Let G be a graph whose vertices are N, the natural numbers. Suppose for every n the subgraph G_n of G induced on {1,2,...,n} has a Hamiltonian path starting with 1. Does G necessarily have a Hamiltonian path? >> MIke Reid wrote: << no. a simple counterexample is the graph 4 --- 3 --- 6 --- 7 --- 8 --- 9 -- ... | \_ | _/ | \ | / ... 1 --- 2 --- 5 where 5 is connected to n for all n > 5 (as well as to 2 and 3 ). Since 1 and 4 each have degree 1 , they would both have to be endpoints of any infinite hamiltonian path, a contradiction. >> Nice example! Now suppose every vertex is required to have finite valence. Then I think this slight modification of Mike's example will still serve as a graph where every {1,...,n} has a Hamiltonian path, but not {1,2,3,...}. 4 --- 3 --- 6 --- 7 --- 9 --- 11 ... |\_ | _/ | _/ | _/ | | \ | / | / | / | 1 --- 2 --- 5 --- 8 --- 10 ---12 ... --Dan

2 1

[math-fun] A "cycle" in N and proving a quaternion-like group is infinite
by Thane Plambeck 03 Dec '02

03 Dec '02

While we're on the subject of the meaning of infinite paths in N, would anyone like to comment on the validity/invalidity of the following argument? I was looking at the group G defined by the quaternion-like relations ijk = l jkl = i kli = j lij = k If you define two "permutations of N" t = (1)(2 3)(4 5) (6 7).... u = (1 2)(3 4)(5 6)... their product is a sort of infinite-order "cycle" in N tu = (1 3 5 7 9 11 13 15 17 ...... 16 14 12 10 8 6 4 2). Now consider the mapping f f(i) = t f(j) = t f(k)= u f(l) = u The mapping f seems to be a homomorphism from G into the group of permutations of N that respects the 4 group relations I started out with (when you check the relations, the involutions t and u cancel each other out). So in particular the element f(ik) = tu has infinite order, so G is infinite. I'm sure this is nothing new, but I was happy to find it (even more happy if it is valid). Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0

Re: [math-fun] infinite paths & cycles
by asimovd＠aol.com 03 Dec '02

03 Dec '02

Re infinite graph connectedness: Assuming "connectedness" here means valence -- the number of edges emanating from a given vertex -- there certainly can be vertices with infinite valence in an infinite graph. In fact, the graph having aleph_0 vertices and one edge between every pair of vertices has infinite valence at every vertex. --Dan

1 0

Re: [math-fun] infinite paths & cycles
by Dan Hoey 03 Dec '02

03 Dec '02

Marc LeBrun <mlb(a)fxpt.com> wrote: > Only if we insist that everything be FINITELY connected are these > infinite hairpins a problem. But then it kind of begs the question > whether the infinite graph itself is "connected" in the first place. The only kind of graph connectedness I know of is finite. If you take the adjacency graph of (-1/2)^n, n=0,1,..., then you get two infinite paths with a limit point of zero, but I can't see any graphlike property that can make them connect. Thus any infinite path is either isomorphic to the adjacency graph of N or the adjacency graph of Z, and infinite cycles don't exist. Dan Asimove got what I meant. In general, I'm trying to figure out if we can make conditions on finite subgraphs of an infinite graph that will enforce a Hamiltonian path of either sort on the whole. Dan

1 0

Re: [math-fun] Square (& other) chains and necklaces.
by asimovd＠aol.com 03 Dec '02

03 Dec '02

Dan Hoey asks: << Now suppose we require Hamiltonian cycles for every {1,...,n}. Is there then a Hamiltonian path for N (there can't be a cycle). Suppose we require Hamiltonian cycles for every {a, ..., b} for a,b in Z? Can we then find a Hamiltonian path through Z? >> Rich grumbles: << Could we be a bit more specific about what a Path or Cycle on an infinite graph is supposed to mean? >> Just kidding, Rich -- this is a fair question. Since a closed interval and a circle are each compact, neither one can be a subgraph of an infinite graph G that contains all vertices of G. (The open cover of a putative path or cycle consisting of the two (or one) edges containing each vertex is an open cover with no finite subcover.) So the ordinary definition of a "path" or "cycle" on a graph are ruled out for any (sub)graph containing infinitely many vertices. For a path having two endpoints or a cycle, I see no acceptable redefinition without adding at least one new vertex and changing the allowable topology. I suspect this is what Dan Hoey meant when he said "There can't be a cycle". But there are two natural ways to define a "path" containing infinitely many vertices of some graph G: 1) a map f from N into its vertex set, or 2) a map f from Z into its vertex set -- in each case such that vertices f(k) and f(k+1) have an edge between them in the graph for all k in N or Z, respectively. In an abuse of consistency, I propose calling the first one "a semi-infinite path" and the second one "a bi-infinite path". When f is a bijection in either case, we'd call such a path Hamiltonian. In each of Dan's two questions above, it would be interesting to know which of these two types of Hamiltonian cycle, if any, are implied by the hypothesis. --Dan (not the one who isn't me)

1 0

Re: [math-fun] infinite paths & cycles
by Henry Baker 03 Dec '02

03 Dec '02

Reminds me of when I first learned of non-standard models of mathematical logic. The most powerful axiom in the Peano axioms of the integers is the induction axiom that says you can start from zero and get to any integer in a finite number of steps. Without this axiom, all sorts of wierd models work for arithmetic, including those with disconnected (finite and infinite) loops of 'integers'. At 10:01 AM 12/3/02 -0800, Marc LeBrun wrote: > >=Richard Schroeppel > > Could we be a bit more specific about what a Path or Cycle on > > an infinite graph is supposed to mean? > >Exactly the question! Now I see why I've been very confused by this part >of the discussion. > >If we mean by Cycle simply something like "there exists a connected >subgraph with all nodes valence 2", and by Path "ditto, but allowing at >most two nodes of valence 1", then I see no contradiction with the examples >(and the desired proof becomes trivial). > >Only if we insist that everything be FINITELY connected are these infinite >hairpins a problem. But then it kind of begs the question whether the >infinite graph itself is "connected" in the first place.

1 0

[math-fun] infinite paths & cycles
by Richard Schroeppel 03 Dec '02

03 Dec '02

Could we be a bit more specific about what a Path or Cycle on an infinite graph is supposed to mean? Rich rcs(a)cs.arizona.edu

2 1

Re: [math-fun] Square (& other) chains and necklaces.
by reid＠hedgehog.math.arizona.edu 02 Dec '02

02 Dec '02

> Here's a more general question: Let G be a graph whose vertices are N, the > natural numbers. Suppose for every n the subgraph G_n of G induced on > {1,2,...,n} has a Hamiltonian path starting with 1. Does G necessarily > have a Hamiltonian path? (The converse is false as the graph > 1-3-2-5-4-7-6-... shows.) no. a simple counterexample is the graph 4 --- 3 --- 6 --- 7 --- 8 --- 9 -- ... | \_ | _/ | \ | / ... 1 --- 2 --- 5 where 5 is connected to n for all n > 5 (as well as to 2 and 3 ). since 1 and 4 each have degree 1 , they would both have to be endpoints of any infinite hamiltonian path, a contradiction. mike

1 0

[math-fun] stunning effects with gray scales and statistical analysis.
by Simon Plouffe 01 Dec '02

01 Dec '02

hello, take a look at this series of pages or paper at http://www-bcs.mit.edu/people/adelson/illusions_demos.html quite interesting what gray, black and white can do to your eyes. Simon Plouffe

1 0