- mathfun@mailman.xmission.com - mailman.xmission.com

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

Re: [math-fun] Maximum orbit of an n-bit register with monotonic update rule
by Henry Baker 29 Nov '02

29 Nov '02

I don't know if this is relevant, but so-called 'Grey codes' have the property that they change only 1 bit for each 'increment'. I seem to recall that Grey codes can count through all 2^N states, although not in the usual order. Grey codes have another type of 'monotonic' property -- that, since only one bit changes on each increment, you don't need a clock to know when to sample the output of a 'counter' -- the change in any bit means that the output is available and stable. So these codes are 'self-clocking'.

2 1

Re: [math-fun] Puzzle: Find limiting angle as dimension -> oo
by clear.net.nz 29 Nov '02

29 Nov '02

I wrote, too late at night: > the dot product of the two vectors for n=12 (well, to within a power of 2): That should be n=13, and it's over n^2, not 2^n. -- Mike Stay staym(a)clear.net.nz

2 2

Re: [math-fun] combinatori(c)al
by asimovd＠aol.com 29 Nov '02

29 Nov '02

<< Which of the spellings is correct/usual, the one with or without the 'c'? At least in the U.S., one sees only "combinatorial" -- without the "c". P.S. A small request -- could you please sign your math-fun messages with your name, at least your first name? It would seem more friendly this way. Regards, Dan Asimov

1 0