September 2006 - mathfun@mailman.xmission.com

[math-fun] Graph Question
by franktaw＠netscape.net 28 Sep '06

28 Sep '06

Is there a name for the operation which takes one graph to another, such that the points of the new graph are the edges of the original graph, and there is an edge between two such points if their originating edges shared a point? I.e., each edge becomes a point, and a point with valence n becomes C(n,2) edges. Franklin T. Adams-Watters ________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.

1 0

Re: [math-fun] Amazing appearances of 7
by N. J. A. Sloane 27 Sep '06

27 Sep '06

Dan said: 7 is the lowest dimension d *known* for which the sphere S^d of d dimensions (all points at a distance of 1 from the origin in R^(d+1) has more than one inequivalent differentiable structure. (This was discovered by John Milnor in 1956, in his coyly titled paper "On manifolds homeomorphic to the 7-sphere". At that time it had been expected that each topological manifold admits a unique differentiable structure. Later work showed that S^7 has exactly 28 inequivalent (classes of) differentiable structures. Me: There is the following entry in the OEIS - any comments or updates would be welcomed. I believe further terms are known to the toplogists, but I have not been able to get hold of them. Neil %I A001676 M5197 N2261 %S A001676 1,1,1,1,1,1,28,2,8,6,992,1,3,2,16256,2,16,16 %N A001676 Number of h-cobordism classes of smooth homotopy n-spheres. %C A001676 For n not equal to 3 or 4 (and possibly for all n) this is the number of oriented diffeomorphism classes of differentiable structures on the n-sphere. %C A001676 a(3) = 1 follows now that the Poincare conjecture has been proved. %D A001676 M. A. Kervaire and J. W. Milnor, Groups of homotopy spheres: I. Ann. of Math. (2) 77 1963 504-537. %D A001676 S. O. Kochman, Stable homotopy groups of spheres. A computer-assisted approach. Lecture Notes in Mathematics, 1423. Springer-Verlag, Berlin, 1990. 330 pp. ISBN: 3-540-52468-1. [Math. Rev. 91j:55016] %D A001676 S. O. Kochman and M. E. Mahowald, On the computation of stable stems. The Cech Centennial (Boston, MA, 1993), 299-316, Contemp. Math., 181, Amer. Math. Soc., Providence, RI, 1995. [Math. Rev. 96j:55018] %D A001676 J. P. Levine, Lectures on groups of homotopy spheres. In Algebraic and geometric topology (New Brunswick, NJ, 1983), 62-95, Lecture Notes in Math., 1126, Springer, Berlin, 1985. %D A001676 J. W. Milnor and J. D. Stasheff, Characteristic Classes, Princeton, 1974, p. 285. %D A001676 S. P. Novikov ed., Topology I, Encyc. of Math. Sci., vol. 12. %D A001676 H. Whitney, The work of John W. Milnor, pp. 48-50 of Proc. Internat. Congress Mathematicians, Stockholm, 1962. %H A001676 A. Hatcher, <a href="http://www.math.cornell.edu/~hatcher/stemfigs/stems.html">Stable Homotopy Groups of Spheres</a> %H A001676 N. J. A. Sloane, <a href="http://www.research.att.com/~njas/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98). %H A001676 E. W. Weisstein, <a href="http://mathworld.wolfram.com/ExoticSphere.html">Link to a section of The World of Mathematics.</a> %Y A001676 Cf. A047680, A053381, A057617, A048648. %K A001676 nonn,hard,nice %O A001676 1,7 %A A001676 njas

1 0

[math-fun] Re: inconvenient directed graphs
by James Propp 27 Sep '06

27 Sep '06

In answer to my question << For each positive integer n > 0, what is the maximum value of N for which there exists an n-by-n posipotent stochastic matrix A such that the matrix A^N has all its entries positive but the matrices I , A , A^2 , ... , A^(N-1) do not? >> Dan replied << The answer is n^2 - 2n + 2. >> Can Dan (or someone else) provide a proof or a reference? Jim

1 0

Re: [math-fun] Re: inconvenient directed graphs
by Daniel Asimov 27 Sep '06

27 Sep '06

Jim asks: << For each positive integer n > 0, what is the maximum value of N for which there exists an n-by-n posipotent stochastic matrix A such that the matrix A^N has all its entries positive but the matrices I , A , A^2 , ... , A^(N-1) do not? >> The answer is n^2 - 2n + 2. --Dan

1 0

[math-fun] Re: inconvenient directed graphs
by James Propp 26 Sep '06

26 Sep '06

"(Dear me! I am not certain quite That even now I've got it right!)" - "Eletelephony", by Laura Elizabeth Richards Dan has pointed out that I still didn't pose my problem correctly, so let me see if I can finally get it straight: Let's say a stochastic matrix A is posipotent if some power of A has all its entries positive. (This is Dan's nice coinage; I had used the standard but bulkier phrase "irreducible and aperiodic".) For each positive integer n > 0, what is the maximum value of N for which there exists an n-by-n posipotent stochastic matrix A and a probability vector v such that the vector A^N v has all its entries positive but the vectors v , A v , A^2 v , ... , A^(N-1) v do not? This can be shown to be equivalent to the following question: For each positive integer n > 0, what is the maximum value of N for which there exists an n-by-n posipotent stochastic matrix A such that the matrix A^N has all its entries positive but the matrices I , A , A^2 , ... , A^(N-1) do not? This can also be recast as a combinatorial question. Suppose we restrict attention to finite directed graphs with n vertices with the property that for every ordered pair of vertices (v,w) there is a way to get from v to w in exactly M moves. Define the "inconvenience" of such a digraph as the smallest M that works for all v,w. How large can the inconvenience be? (Note that we are limiting ourselves to directed graphs for which there exists a universal M such that for every ordered pair of vertices (v,w) you can get from v to w in M moves. Of course, if M is a number with this property, so is M+1.) To clarify what I mean by "moves": When I say "There is a way to get from v to w in exactly K moves" I mean "There exists a sequence of not necessarily distinct vertices v = v_0, v_1, ..., v_K = w such that for each j in {1,2,...,K-1} there is a directed edge from v_{j-1} to v_j." Example: Consider the direct graph on 4 vertices {A,B,C,D} with edges A->B, B->C, C->D, D->A, and D->B. Then, starting from A, the vertices that are reachable in a specified number of moves are as follows: In 1 move: B In 2 moves: C In 3 moves: D In 4 moves: A,B In 5 moves: B,C In 6 moves: C,D In 7 moves: A,B,D In 8 moves: A,B,C In 9 moves: B,C,D In 10 moves: A,B,C,D So we have shown that the inconvenience of this digraph is at least 10. Correspondingly, consider the matrix and vector ( 0 1 0 0 ) ( 1 ) ( ) ( ) ( 0 0 1 0 ) ( 0 ) A = ( ) , v = ( ) ; ( 0 0 0 1 ) ( 0 ) ( ) ( ) (1/2 1/2 0 0 ) ( 0 ) A^10 v has all its entries positive, but A^9 v does not. Here is a proof that the inconvenience can be at most 2^n-2: Each probability vector can be represented by an n-tuple of 0's and +'s, where 0 stands for 0 and + stands for any positive number. Call this the signature of the vector. It is easy to see that the signature of a vector v determines the signature of its image A v. If the 2^n - 1 vectors v , A v , A^2 v , ... , A^(2^n-2) v all have signatures different from (0,0,...,0) and (+,+,...,+), then by the pigeonhole principle two of the vectors must have the same signature. But then the sequence of signatures must cycle forever and never hit (+,+,...,+), which contradicts our assumptions. So either (0,0,...,0) must occur (which is impossible since all our vectors are probability vectors) or (+,+,...,+) must occur (in which case that signature recurs forever after). Hence, for every v, A^(2^n-2) v has all its entries positive. Clearly one can do better than the upper bound N(n) leq 2^n - 2. My question is, how much better can one do? Jim Propp

1 0

Re: [math-fun] Amazing appearances of 7
by Daniel Asimov 26 Sep '06

26 Sep '06

I overlooked some early posts to this Subject, so I'm not sure if this was mentioned yet: 7 is the lowest dimension d *known* for which the sphere S^d of d dimensions (all points at a distance of 1 from the origin in R^(d+1) has more than one inequivalent differentiable structure. (This was discovered by John Milnor in 1956, in his coyly titled paper "On manifolds homeomorphic to the 7-sphere". At that time it had been expected that each topological manifold admits a unique differentiable structure. Later work showed that S^7 has exactly 28 inequivalent (classes of) differentiable structures. A rumored connection with Howard Johnson ice cream flavors has never been proven.) The only possible exception is the 4-sphere, but no one knows at this time whether it supports a differentiable structure other than the standard one. --Dan

1 0

RE: [math-fun] Decimal question
by Daniel Asimov 26 Sep '06

26 Sep '06

Christian writes: << With a = 17537 = prime number, And b = 12800(...0) = 2^(9+k) * 5^(2+k), my last family produce always reduced fractions a/b, i.e. on (0, 1): 17537/128000 = 0.1370078125 >> Very nice example. Now I wonder if there's an example p/q in lowest terms, with 1/10 < p/q < 1, so that the most compact way of writing the decimal uses the same digits (with the same multiplicity). (By compact I mean no leading or trailing zeroes.) Okay, we can start with binary. How about a binary fraction p/q in lowest terms, 1/2 < p/q < 1, with its compact binary representation using the same number of 0's & 1's as there are in p_2 & q_2 (with multiplicity) ? --Dan

3 5

Re: [math-fun] Decimal question
by Daniel Asimov 26 Sep '06

26 Sep '06

Christian wrote: << > Including the crazy results on base 4, including the sudoku-like solution > 124,983/576 = 216.984 375 >> Mike, I think the above refers to different cases. The equation 124,983/576 = 216.984 375 is true in base 10. --Dan

2 1

[math-fun] Re: inconvenient directed graphs
by James Propp 26 Sep '06

26 Sep '06

Let me respond to Dan's thoughtful response with a clarified restatement of the problem: We say a stochastic matrix A is irreducible and aperiodic if some power of A has all its entries positive. For each positive integer n > 0, what is the maximum value of N for which there exists an n-by-n aperiodic stochastic matrix A and a probability vector v such that A^N v has all its entries positive but v , A v , A^2 v , ... , A^(N-1) v do not not? This can be recast as a purely combinatorial question. Suppose a finite directed graph with n vertices has the property that for every ordered pair of vertices (v,w), there is a way to get from v to w in exactly N moves. Define the "inconvenience" of such a digraph as the smallest N that works for all v,w. How large can the inconvenience of an n-vertex directed graph be? Example: Consider the direct graph on 4 vertices {A,B,C,D} with edges A->B, B->C, C->D, D->A, and D->B. Then, starting from A, the vertices that are reachable in a specified number of moves are as follows: In 1 move: B In 2 moves: C In 3 moves: D In 4 moves: A,B In 5 moves: B,C In 6 moves: C,D In 7 moves: A,B,D In 8 moves: A,B,C In 9 moves: B,C,D In 10 moves: A,B,C,D So we have shown that the inconvenience of this digraph is at least 10. Correspondingly, consider the matrix and vector ( 0 1 0 0 ) ( 1 ) ( ) ( ) ( 0 0 1 0 ) ( 0 ) A = ( ) , v = ( ) ; ( 0 0 0 1 ) ( 0 ) ( ) ( ) (1/2 1/2 0 0 ) ( 0 ) A^10 v has all its entries positive, but A^9 v does not. Here is a proof that the inconvenience can be at most 2^n-2: Each probability vector can be represented by an n-tuple of 0's and +'s, where 0 stands for 0 and + stands for any positive number. Call this the signature of the vector. It is easy to see that the signature of a vector v determines the signature of its image A v. If the 2^n - 1 vectors v , A v , A^2 v , ... , A^(2^n-2) v all have signatures different from (0,0,...,0) and (+,+,...,+), then by the pigeonhole principle two of the vectors must have the same signature. But then the sequence of signatures must cycle forever and never hit (+,+,...,+), which contradicts our assumptions. So either (0,0,...,0) must occur (which is impossible since all our vectors are probability vectors) or (+,+,...,+) must occur (in which case that signature recurs forever after). Hence, for every v, A^(2^n-2) v has all its entries positive. Clearly one can do better than the upper bound N(n) leq 2^n - 2. My question is, how much better can one do? My example for n=4 shows that N(4) geq 10. Suitably generalized, this example gives a quadratic lower bound on N(n). I suspect that the true behavior of the inconvenience function is quadratic. But is O(n^2) the "inconvenient truth"? :-) I'd be grateful for a proof, disproof, or reference. In any case, thanks Dan! Jim Propp

1 0

[math-fun] First differences are composites
by Eric Angelini 25 Sep '06

25 Sep '06

> (I'm working on seq. T : > « Primes sequence whose first differences show all non-primes, once » ... T is impossible to build because any prime +9, or +15, or + any other odd composite will give an even result... (once "2" has been used) Best, É.

1 0