June 2003 - mathfun@mailman.xmission.com

RE: [math-fun] Geometry/topology question about planar graphs (fwd)
by Erik Demaine 05 Jun '03

05 Jun '03

John Conway wrote: > the "Carpenter's Ruler" problem (are the plane embeddings of a hinged ruler > interconvertible in this way, keeping the segment-lengths fixed) is > quite difficult - [...] > and the corresponding assertion for arbitary graphs is false. Andy Latto wrote: > Is there an easy-to-describe counterexample? It's false even with a single degree-3 vertex, i.e., 3 attached "rulers". See http://theory.lcs.mit.edu/~edemaine/papers/InfinitesimallyLocked_LasVegas/ for this example. A simpler (and older) example is in http://theory.lcs.mit.edu/~edemaine/papers/LockedTreeDAM/ Of course, these linkage problems are quite different from Dan's original question, which did not require edge lengths to stay fixed: > Still a mystery to me is this: Given a graph G embedded in the plane, under > what circumstances can a straight-line version of G be obtained through a > continuous deformation of the original embedding, through embeddings ? I don't quite see the issue of continuous deformation here. (As I understand it, only the final embedding has to be straight-line.) Can't any two topologically equivalent embeddings (in the sense that the cyclic order around each vertex is identical in two embeddings) be obtained by continuous deformation? (Perhaps this is what you're asking.) If so, then Tutte's theorem on graph drawing proves the rest: W. T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 13(52):743-768, 1963. I even wonder whether Tutte's construction (via springs & barycenters) might be adapted to give a continuous motion. This recent followup may be relevant: http://www.ehess.fr/centres/cams/person/pom/tutte-s-barycenter-method.ps Erik -- Erik Demaine | edemaine(a)mit.edu | http://theory.lcs.mit.edu/~edemaine/

1 0

[math-fun] Homogeneous linear integral equations
by Eugene Salamin 05 Jun '03

05 Jun '03

Does anyone know how to find analytic solutions to homogeneous linear integral equations? These are equations of the form int(K(x,y) f(y), y=a..b) = v f(x). K(x,y) is a known function over a<=x<=b, a<=y<=b, and I'm willing to assume that K(y,x) = K(x,y)*. (* means complex conjugate.) The problem is to find the eigenfunctions f(x) and eigenvalues v. This is equivalent to finding a set of orthonormal functions f[n](x) such that K(x,y) = sum(v[n] f[n](x) f[n](y)*, n=0..infinity), int(f[m](y) f[n](y)*, y=a..b) = delta[m,n]. The problem can be solved numerically by turning the integral into a sum, and then solving the resulting matrix eignevalue problem, however I'm looking for analytic solutions. __________________________________ Do you Yahoo!? Yahoo! Calendar - Free online calendar with sync to Outlook(TM). http://calendar.yahoo.com

1 0

[math-fun] Signatures of irrational numbers
by lkmitch＠att.net 05 Jun '03

05 Jun '03

Hi all, Lately, I've been playing with the signature of irrational numbers. My understanding, from what I've read on the web, is this: For a positive irrational number x, form the numbers y = i + j*x, where i and j are both positive integers. Since x is irrational, no 2 y values will be the same for different i and j. Arrange the ys by size, then the sequence of i values is a fractal sequence, and the signature of x. For x = phi ~ 1.618034, the first few entries are: i j y 1 1 2.618033989 2 1 3.618033989 1 2 4.236067977 3 1 4.618033989 2 2 5.236067977 4 1 5.618033989 1 3 5.854101966 3 2 6.236067977 5 1 6.618033989 And the signature begins: 1, 2, 1, 3, 2, 4, 1, 3, 5. If you strike the first occurence of every integer in the sequence, you get the original sequence back, which makes this a fractal sequence. My questions are: - What about the j sequence? From what I've seen experimentally, it seems to be a fractal sequence, too. Why is the signature the i sequence as opposed to the j sequence? What's known about the relation of the j sequence to the i sequence? - For a limited set of integers (both i and j run from 1 to 50), I plotted i vs. j, and the result was very interesting (I thought). You can find the picture here: http://www.fractalus.com/kerry/sigofphi.html The plot is one continuous zig-zag line which seems to never cross itself. But, the angle of the line changes slightly, causing some areas to bunch up and appear darker, and others to spread out and appear lighter. The overall effect is of a series of rectangles drawn in different shades of gray. Can anyone point me to other work that has been done on this? Thanks, Kerry Mitchell -- lkmitch(a)att.net www.fractalus.com/kerry

4 3

[math-fun] four coin changing
by Thane Plambeck 05 Jun '03

05 Jun '03

Three integer coin values 1 < a < b will make optimal (smallest number of coins) change for all amounts using the greedy ("pick the largest possible coin first") algorithm if and only if there is an integer m so that Floor[b/m] = a. For example: A) The penny=1, nickel=a=5, dime=b=10 has m=2; but B) If the coin set 1, 3, 4 the greedy algorithm uses three coins to make change for 6 = 4 + 1+ 1 cents using the greedy algorithm, while the non-greedy choice 3+3 uses fewer coins. There is no integer m such that Floor[4/m] = 3. Is there a similar criterion for four coins 1 < a < b < c? Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

2 1

Re: [math-fun] Geometry/topology question about planar graphs
by asimovd＠aol.com 05 Jun '03

05 Jun '03

Thanks to all who responded to this question! Still a mystery to me is this: Given a graph G embedded in the plane, under what circumstances can a straight-line version of G be obtained through a continuous deformation of the original embedding, through embeddings ? --Dan

3 2

[math-fun] Re: a prime in each row?
by James Propp 05 Jun '03

05 Jun '03

I should mention that the conjecture is true for all n between 2 and 100. Moreover, if one looks at the minimum (over k) of the number of primes in the kth row of the n-by-n square, one gets the sequence 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 3, 2, 2, 2, 3, 4, 4, 3, 4, 3, 3, 4, 5, 4, 3, 4, 5, 4, 4, 5, 4, 4, 5, 5, 2, 6, 6, 5, 4, 6, 4, 5, 7, 7, 3, 7, 8, 4, 5, 10, 7, 5, 6, 5, 5, 10, 7, 8, 8, 6, 10, 7, 5, 5, 8, 7, 7, 5, 10, 7, 8, 10, 7, 7, 10, 10, 9, 12, 7, 11, 10, 10, 9, 7, 13, 11, 10, 10, 11, 10, 11, 10, 11, 12, 11, 8, 11, 9 which shows steady increase (up to slight fluctuations). So I suspect that the conjecture would yield to a two-pronged attack (brute force calculations for small n, rigorous asymptotics for large n). Jim Propp

2 1

Re: [math-fun] a prime in each row?
by asimovd＠aol.com 05 Jun '03

05 Jun '03

David Wilson writes: << Propp's conjecture* would imply a prime between n^2 and (n+1)^2, which conjecture I believe is stil outstanding. >> *That for any n >=2 and for each k in [0,n-1], there is at least one prime in the "row" of n consecutive numbers [kn+1,(k+1)n]. ------------------------------------------------------------------------------ ---------------------------------- I guess David Wilson's point is that the interval of 2n numbers [(n-1)^2, n^2], forms the last two rows in Propp's conjecture. But obviously, there's a prime in the first row, and there's one in the second row guaranteed by Bertrand's Postulate. Question: Where does the conjectural territory first begin? [2n+1,3n] ? [3n+1,4n] ? Etc. --Dan

3 2

Re: [math-fun] Geometry/topology question about planar graphs
by asimovd＠aol.com 04 Jun '03

04 Jun '03

Suppose a finite graph G is embedded in the plane topologically. When can it be embedded so that all the edges are straight lines? Most interesting to me is the case where the straight-line embedding is obtained via a continuous deformation, through embeddings, of the original one. (And I'm most interested in the case where each of the graph's finite complementary components is bounded by exactly 4 edges.) --Dan

4 3

[math-fun] problem at alum.mit.edu
by Richard Schroeppel 04 Jun '03

04 Jun '03

Several math-fun subscribers have addresses at alum.mit.edu. The MIT forwarder seems to have been a black hole for a few days, but is working at the moment. As near as I can tell, the missing messages were dropped. The recent archive is available from a web interface; see the List-Archive line in the message headers. Rich rcs(a)cs.arizona.edu

1 0

[math-fun] nice product for (1+y)^(1/a)
by Joerg Arndt 04 Jun '03

04 Jun '03

I like this one: Let y Y =y T(y) = + - 1 a and a a a (1+Y ) a -(a+Y ) (1+Y ) a k k k Y =----------------- = --------- - 1 k+1 a a (a+Y ) (a+Y ) k k then ___oo 1/a | | (1+T(Y )) = (1+y) | |k=1 k Convergence is quadratic. The ansatz (T(y)="terms 1..(n-1) of Taylor series") also works for 1/\sqrt[a]{1+y} and gives products with n-th order of convergence. -- p=2^q-1 prime <== q>2, cosh(2^(q-2)*log(2+sqrt(3)))%p=0 Life is hard and then you die.

1 0