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

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

05 Jun '03

On Thu, 5 Jun 2003, Dan Asimov wrote: > But given that a graph G that can embedded in the plane can be embedded with > all edges straight, however, doesn't immediately imply that the straight-line > embedding *is* topologically equivalent to the original embedding (even > though the graph itself is of course topologically the same). If the graph is 3-connected, then the topological embedding is unique up to the choice of the outer face. Tutte's "How to Draw a Graph" allows you to specify the outer face in the straight-line drawing it produces. So for 3-connected graphs, you get exactly the topological embedding you want. For graphs that are not 3-connected (like your square + a degree-2 vertex in the center), I assume you can decompose... E.g., suppose there is a vertex 2-cut {v,w}, and on one side you have G_1 and the other side you have G_2 (both of which contain v & w, and that is their only overlap). Let G'_1 be the graph & topological embedding obtained from G_1 with the edge {v,w} added where G_2 used to be. Ditto for G'_2. Then you can draw G'_1 and G'_2 by induction, and then nonuniformly scale G'_2's drawing down to be squished against the edge {v,w}, and then place it against the appropriate side of {v,w} in the drawing of G'_1. Erik -- Erik Demaine | edemaine(a)mit.edu | http://theory.lcs.mit.edu/~edemaine/

2 1

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

05 Jun '03

I wrote: >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 Neil Sloane wrote to me saying that his own calculations disagreed with mine. He's right; this is not how the sequence goes. Here's how the sequence actually starts: 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 2, 3, 4, 3, 3, 4, 3, 3, 4, 3, 3, 4, 4, 4, 3, 3, 4, 5, 4, 3, 4, 5, 4, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 7, 6, 4, 5, 6, 6, 5, 6, 6, 6, 6, 6, 7, 7, 6, 6, 6, 7, 7, 7, 7, 6, 6, 7, 7, 7 Thanks, Neil! Jim Propp

1 0

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

05 Jun '03

Erik Demaine asks: << 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? >> This looks fairly easy to prove. And I'm fairly convinced of John's assertion that a straight-line embedding of a graph G in the plane *can* be obtained by a continuous deformation of an arbitrary planar embedding of G. But given that a graph G that can embedded in the plane can be embedded with all edges straight, however, doesn't immediately imply that the straight-line embedding *is* topologically equivalent to the original embedding (even though the graph itself is of course topologically the same). For example consider a square with a 5th node making a triangle with one side of the square -- a graph with 5 nodes and 6 edges. This can be embedded in the plane with the 5th node either inside or outside the square. (Of course, straightenability is not an issue here.) --Dan

1 0

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