August 2019 - mathfun@mailman.xmission.com

Re: [math-fun] Who has written a clear summary of what research mathematicians do?
by Steve Witham 01 Oct '19

01 Oct '19

Scott Kim wrote-- > I think it's an occupational hazard of being an > expert in any field, not just math, that it can be hard to explain what you > do to an outsider. Nonetheless I think it's important to do, and not just > for outsiders, but also for people inside the field. At least it's > important to me Â— the dearth of mathematicians talking about what > mathematics is I find intolerable, and makes me distrustful of mathematics > as a field. Ted Nelson's _Computer Lib_ (1974) for me was a taste of what the good thing can be: An enthusiastic insider in a field who is also a skeptical outsider without missing a beat. There's the public-facing importance of that (especially with something commercial like computers), but also I like the way I oriented myself after reading that book. Stewart Brand, Martin Gardner, Aubrey de Grey, Vi Hart. https://youtu.be/v-pyuaThp-c "Doodling in Math Class: Connecting Dots" (talk about not missing beats) --Steve

3 2

Re: [math-fun] Random nonempty intersection of cube and plane, revisited
by Keith F. Lynch 28 Sep '19

28 Sep '19

Sorry it took me a while to finish my program that finds the average perimeters and areas of the intersection of a plane with a cube. On July 28th, I wrote: Okay, I think I figured it out. Where n is the order of the intersection polygon, 3 through 6, there are n intersection points between the cube and the plane, hence n! possible sequences of intersection points. Since the polygon is convex, I'm pretty sure that the correct order to visit the n intersection points, returning to my starting point (i.e. a Hamiltonian circuit) will simply be the one with the shortest total distance. Someone please politely tell me if I'm wrong. This got me the correct perimeter length. Correct as supported by the program's agreeing with Fred Lunnon's and my ideas of what the smallest and largest perimeters should be for each n-gon. Since it doesn't matter which intersection point I start on, I only have to try (n-1)! sequences. Make that (n-1)!-1, since there are two correct solutions (the same solution in opposite directions) and they can't both be in the last place. So for the largest possible n, 6, 119 tries. Make that (n-1)!/2 sequences. I precomputed all permutations of 1-3, 1-4, 1-5, and 1-6, and discarded the ones that were reversals of others already in the table. So for the largest possible n, 6, 60 tries. On July 29th I wrote: Once I know the order of the intersection points, all I have to do is run a line from one intersection point to each of the other intersection points, to divide the polygon into triangles, then Heron each of the triangles and add their areas together. This should have worked. I spent most of my time trying, without success, to figure out why it didn't work. I knew it wasn't working because I was getting impossibly large areas. (Except for triangles, where it appeared to be correct, given the maximum area it found.) I was hampered in debugging by the fact that I have no way of generating graphics. All I have to look at are lists of numbers. And I'm not a visual thinker, anyway. Eventually, I figured it must be that I was somehow mistaken that the sequence of vertices with the smallest sum of successive distances was the actual perimeter. I couldn't visualize how that could possibly be, but visualization isn't my strong suit. Yes, the perimeter maxima were correct, but that's no surprise given that a hypothetical incorrect vertex order with a smaller distance sum wouldn't affect that maximum. I looked forward to finding an exception, then drawing it by hand. So I implemented a variant of James Propp's suggestion that I rotate the polygon into the x,y plane, then convert from rectangular to polar coordinates, with the centroid as the origin, and sort by theta. Since at that time I only cared about the order of vertices, I instead simply discarded the z coordinate rather than doing a 3D rotation. (I am perhaps irrationally prejudiced against unnecessary trigonometry, as I'm under the perhaps outdated impression that trig makes programs very slow.) Much to my surprise, I discovered that the orders were the same. (At least for all of ten million random planes.) The flaw in my area algorithm was elsewhere. I continued looking for it until I started running out of time. (James Propp's talk is on August 7th, and today is the 6th.) Then I tried getting the area from my projection into the x,y plane, using the shoelace formula (which was suggested by both James Propp and Tom Duff). The projection is obviously going to be foreshortened, so I tried multiplying it by the slope of the original polygon to fix it. Apparently I computed the slope wrong, as the areas of triangles (hence presumably also all other figures) were wrong. Fortunately, Tom Duff also said, "In 3 dimensions you can either rotate everything into the plane or compute the projected areas in the xy, yz and zx planes and take the square root of the sum of the squares." Since it was easy to adapt my code which projected into the x,y plane and worked there into doing the same with the other two orthogonal planes, so I did it that way. Then I had a tenacious bug that was due to the modulo function in C being broken. -1 mod 3 should be 2, not -1. Once I changed at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][(j-1)%g]][(l+2)%3])); to j1 = (j-1)%g; if (j1 < 0) j1 += g; at[l] += fabs(v2[pe[g][im][j]][(l+1)%3] * (v2[pe[g][im][(j+1)%g]][(l+2)%3] - v2[pe[g][im][j1]][(l+2)%3])); it started working perfectly. (That's the shoelace formula.) In retrospect I should have documented better, used more meaningful variable names, and unrolled those nested subscripts. But the program started two years ago as a quick and dirty hack to measure the average number of edges of the intersection polygon, so I used "alpine programming," by analogy with "alpine style mountain climbing," which means not bothering with those tedious base camps and pre-positioning supplies, but instead just racing for the summit. In my defense, mountains, unlike programming tasks, seldom suddenly get much taller. Anyhow, without further ado, here are the results, based on the average of two runs of a billion random planes. Again, the cube's side length is 2. Smallest, average, and largest perimeters: 3 sides: 0.0000 3.0613 8.4736 4 sides: 4.0001 7.1700 9.6550 5 sides: 6.8314 8.2032 9.6521 6 sides: 8.4853 8.6827 9.6511 All over average perimeter: 6.2841 Smallest, average, and largest areas: 3 sides: 0.0000 0.5496 3.4546 4 sides: 0.0001 3.2519 6.9252 5 sides: 3.0088 4.6743 6.9218 6 sides: 5.1975 5.8310 6.9240 All over average area: 2.8819 Proportion of each polygon type: 3 sides: 27.97% 4 sides: 48.68% 5 sides: 18.70% 6 sides: 4.65% I'm CCing James Propp so that he'll get this in time for tomorrow's talk even if he's on the digest option and no digest goes out before that talk. Tomorrow I'll return to trying to figure out why my original area formula isn't working.

8 26

[math-fun] Returns to zero when subtracting and adding squares
by Allan Wechsler 08 Sep '19

08 Sep '19

A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule: B0 = A0 and for n > 0 Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise. If An is the non-negative integers (A001477), then Bn is A008344. If An is the perfect squares (A000290), then Bn is A076042. Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either. Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis. Can any funsters contribute additional insight?

6 11

[math-fun] Who has written a clear summary of what research mathematicians do?
by Scott Kim 08 Sep '19

08 Sep '19

Does anyone know of a clear explanation written for nonmathematicians of the fundamental types of things research mathematicians do, and why? I'm planning to write about how the process of inventing puzzles is similar to the process fo doing mathematical research, and how we can teach kids about mathematical research by having them invent puzzles. I'd like to reference other authors, and wonder what has been written that isn't just mathematicians talking to mathematicians. The authors I know who have attempted this are Keith Devlin in Introduction to Mathematical Thinking, written to tell math grad students how "real" mathematics differs from how math is conventionally taught in K-12, and Eugenia Cheng in many of her books, starting with How to Bake Pi. These are good, but there's room for more voices.

15 21

Re: [math-fun] Draft of short essay on Scott Kim's motley dissections
by Bill Gosper 04 Sep '19

04 Sep '19

On Thu, Jul 11, 2019 at 3:14 AM rwg <rwg(a)ma.sdf.org> wrote: > > > -------- Original Message -------- > Subject: Re: [math-fun] Draft of short essay on Scott Kim's motley > dissections > Date: 2019-07-10 12:59 > From: James Propp <jamespropp(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Reply-To: math-fun <math-fun(a)mailman.xmission.com> > > Beautiful! > > Thanks, Fred! > > Jim > I'll second that! How hard would it be to twist the whole scene so that the front face doesn't rotate? We can change the problem so that the answer is an ancient Macsyma animation most of you should recall. Problem: Reshape the six "squares" so they can simply rotate, while four "triangles" alternately swell, then shrink away, while the other four complementarily follow suit in the opposite phase. The edges need no longer lie on great circles. Spoiler Lissajous arcs <http://gosper.org/lisspump.gif> On Wed, Jul 10, 2019 at 3:41 PM Fred Lunnon <fred.lunnon(a)gmail.com> > wrote: > > > I have posted an animation at > > https://www.dropbox.com/s/5yrmef1djjuatfc/pseudo_movie.gif > > of a spherical pseudo-cuboctahedron (SPCO) morphing continuously via > > octahedron -- big triangles -- cuboctahedron -- big squares -- cube, > > then back again via the mirror-images; Maple program is available > > on request. > > > > This should run continuously when the link is opened in a browser: > > please advise me of any problems! > > > > Time is proportional to `twist' angle t between (plane containing) > > SPCO edge arc and associated edge of scaffolding cube, modulo pi . > > SPCO vertices are given by 24 cube symmetries (with even resigned > > permutations of components) of point with Cartesian coordinate > > P(t) = (a^2 + a*b, a^2 - a*b, a^2 + b^2)/d , > > where > > b = cos t , a = (1/sqrt2) sin t , d^2 = 1 - a^4 . > > > > For octahedron t = 0 , for cube t = pi/2 ; for cuboctahedron > > t = arccos(-1/3)/2 . For Jim Propp's case, where edge plane meets > > 4 vertices of the scaffold cube, rather unexpectedly t = > > arccos(+1/3)/2 > > --- just pi/2 minus the cuboctahedron angle! > > > > While I was busily upstaging his previous version, Christian has > > quietly replaced that static CGI view with a 3D-printed solid model: > > see > > https://www.thingiverse.com/thing:3726912 > > > > Hmmm ... a mechanically functional solid morphing model, anybody? > The only hope would be van Deventer. —rwg > > > > Finally, note that a similar method should cope straightforwardly > > with morphing pseudo-octahedron and pseudo-icosidodecahedron. > > > > Fred Lunnon > > > > > > On 7/6/19, James Propp <jamespropp(a)gmail.com> wrote: > > > I've figured out one way to make a 3D realization of a > pseudo-octahedron, > > > by decorating the faces of a tetrahedron. (Maybe this was obvious to > you > > > all, but I didn't see it.) See > > > > > > http://faculty.uml.edu/jpropp/mathenchant/semi-pseudo-octahedron.JPG > > > > > > which shows how two of the four faces should be decorated, with three > > > vertices per face. If you breathe into the tetrahedron to inflate it to > > > become a sphere, the pattern of decorations on the tetrahedron should > > > become a motley dissection of the sphere with 12 vertices, 6 > > pseudo-edges, > > > and 8 three-sided pseudo-faces. > > > > > > Can Christian (or someone else) create an image of this for me? I'd > love > > to > > > use it in my next mini-essay (~ 1000 words) for the Big Internet > > Math-Off, > > > as well as in the longer Mathematical Enchantments piece on the subject > > of > > > motley dissections that I plan to write later this summer or in the > Fall. > > > > > > Thanks, > > > > > > Jim > > > > > > > > > > > > On Thu, Jul 4, 2019 at 10:39 AM ed pegg <ed(a)mathpuzzle.com> wrote: > > > > > >> Related: > > >> Moritz W. Schmitt, On Space Groups and Dirichlet-Voronoi Stereohedra > > >> https://refubium.fu-berlin.de/handle/fub188/10176 > > >> > > >> I want to see pictures of all of these space filling plesiohedra. > I've > > >> been wanting to see Engel's 38-sided spacefiller for years. > > >> --Ed Pegg Jr On Thursday, July 4, 2019, 07:58:05 AM CDT, Christian > > >> Lawson-Perfect <christianperfect(a)gmail.com> wrote: > > >> > > >> Scott, I'm interested in giving it a go. I've got a couple of student > > >> working with me over the summer on 3d printing mathematical objects, > so > > >> this'd be great. > > >> > > >> On Thu, 4 Jul 2019 at 06:46, Scott Kim <scott(a)scottkim.com> wrote: > > >> > > >> > The pseudo octahedron as drawn has bar 3 symmetry, meaning 4-fold > > >> > rotational symmetry plus top and lower hemispheres congruent but > > mirror > > >> > images (I think...not sure). The pseudo-cube needs to be redrawn to > > work > > >> > nicely on a sphere, as does the pseudo-dodecahedron. The 3d models I > > >> really > > >> > want to have 3d printed are the pseudo 5-cell (easy) and pseudo > > 16-cell > > >> > (hard), which have exteriors that are concave curivlinear > tetrahedra. > > I > > >> can > > >> > provide drawings if anyone's interested in giving them a try. — > Scott > > >> > > > >> > On Wed, Jul 3, 2019 at 9:07 PM James Propp <jamespropp(a)gmail.com> > > wrote: > > >> > > > >> > > And it would be good to have a picture of the pseudo-cube as an > > actual > > >> > > motley dissection of the sphere, but I have no idea how to realize > > it. > > >> > I've > > >> > > put Scott's sketch of the combinatorial structure of the > pseudo-cube > > >> > > at > > >> > > http://mathenchant.org/pseudo-cube.png; in both this picture and > > the > > >> > > pseudo-octahedron picture, it's important to keep in mind that the > > >> > > noncompact region in the picture is also a pseudo-face. In the > > >> > symmetrical > > >> > > pseudo-cube, the six pseudo-faces would be centered at the > vertices > > of > > >> an > > >> > > octahedron, but I don't see how the pseudo-faces fit together. Can > > any > > >> of > > >> > > you figure this out? > > >> > > > > >> > > Jim > > >> > > > > >> > > On Wed, Jul 3, 2019 at 9:28 PM James Propp <jamespropp(a)gmail.com> > > >> wrote: > > >> > > > > >> > > > It would also be good to have a picture of the > pseudo-octahedron. > > >> I've > > >> > > put > > >> > > > Scott Kim's picture of it at > > >> > > http://mathenchant.org/pseudo-octahedron.png; > > >> > > > there should be a realization of it as a motley dissection of > the > > >> > surface > > >> > > > of the sphere that has all the rotational symmetries of the > > >> octahedron > > >> > > (but > > >> > > > none of the reflection symmetries). Can Christian (or anyone > else) > > >> > > > construct a virtual model? In some ways it might be harder to > > >> visually > > >> > > > parse the pseudo-octahedral motley dissection than the > > >> > > pseudo-cuboctahedral > > >> > > > motley dissection, even though the former is simpler, because > the > > >> > visible > > >> > > > hemisphere offers less information. But an interactive rotatable > > >> > version > > >> > > > (or just a GIF that shows the object rotating) would solve that > > >> > problem. > > >> > > > > > >> > > > Jim > > >> > > > > > >> > > > On Wed, Jul 3, 2019 at 2:49 PM James Propp < > jamespropp(a)gmail.com> > > >> > wrote: > > >> > > > > > >> > > >> Wow; this is great! > > >> > > >> > > >> > > >> Is there a way to rotate the view? > > >> > > >> > > >> > > >> Jim > > >> > > >> > > >> > > >> On Wed, Jul 3, 2019 at 3:38 AM Christian Lawson-Perfect < > > >> > > >> christianperfect(a)gmail.com> wrote: > > >> > > >> > > >> > > >>> I've made a 3d model in OpenSCAD and uploaded it to > thingiverse: > > >> > > >>> https://www.thingiverse.com/thing:3726912. I've put a simple > > >> > rendering > > >> > > >>> of > > >> > > >>> the shape on that page; I'm going to both 3d print it and do a > > >> nicer > > >> > > CGI > > >> > > >>> rendering now. > > >> > > >>> > > >> > > >>> On Tue, 2 Jul 2019 at 19:24, James Propp < > jamespropp(a)gmail.com> > > >> > wrote: > > >> > > >>> > > >> > > >>> > The link to the video apparently didn't survive the > conversion > > >> from > > >> > > >>> HTML to > > >> > > >>> > PDF, so here's the URL for Scott Kim's video: > > >> > > >>> > > > >> > > >>> > https://youtu.be/xK1QA0Oi7iE > > >> > > >>> > > > >> > > >>> > Jim > > >> > > >>> > > > >> > > >>> > > > >> > > >>> > > > >> > > >>> > > > >> > > >>> > On Tue, Jul 2, 2019 at 12:03 PM James Propp < > > >> jamespropp(a)gmail.com> > > >> > > >>> wrote: > > >> > > >>> > > > >> > > >>> > > At > > http://faculty.uml.edu/jpropp/mathenchant/motley-draft3.pdf > > >> > > >>> you'll > > >> > > >>> > > find a draft of an essay that will be published on July > > 11th. > > >> > > >>> Comments > > >> > > >>> > are > > >> > > >>> > > welcome, but even more welcome would be a good picture of > > the > > >> > > >>> "spherical > > >> > > >>> > > pseudo-cuboctahedron"! In principle I know how to make > such > > a > > >> > > >>> picture, > > >> > > >>> > sort > > >> > > >>> > > of: take the motley dissection of the surface of the cube > > >> (shown > > >> > in > > >> > > >>> the > > >> > > >>> > > essay), push all the vertices out onto a sphere, and draw > > >> > spherical > > >> > > >>> arcs > > >> > > >>> > > joining up those vertices. This seems like a job for > > >> Mathematica, > > >> > > >>> but my > > >> > > >>> > > mastery of 3D graphics isn't up to the job. I'll > gratefully > > >> > > >>> acknowledge > > >> > > >>> > > anyone who can create a picture I can use! > > >> > > >>> > > > > >> > > >>> > > Thanks, > > >> > > >>> > > > > >> > > >>> > > Jim Propp > > >> > > >>> > > > > >> > > >>> > _______________________________________________ >

4 10

[math-fun] Cognitive Dissonance: The Homology Concept
by Brad Klee 01 Sep '19

01 Sep '19

Subtitle: A Curious Case of Batesian Mimicry. During late August in Arkansas it is often possible to glimpse a black-bodied insect darting through the tree tops. Looking closer, the dorsal side of the hind wings reflects a blue-green hue. You might naturally wonder, what species is that? On the running trail: https://0x0.st/z4Wy.JPG On U of A campus: https://0x0.st/z4Wt.JPG Or At Devil's Den State Park: https://0x0.st/z4Wv.JPG https://0x0.st/z4Ww.JPG It could easily be confused for a swallowtail, either pipevine or spicebush, when in fact the creature is from family Nymphalidae rather than Papilionidae. During a flight, it is impossible to closely observe the fore-wing venation, so humans nor birds can be blamed for falling fool to an effective mimic (at least at first). Even upon a closer look at the ventral side, the poorly-named red-spoted purple admiral ( why not orange-spotted blue? ) appears very similar to the pipevine swallowtail. Both butterflies have seven orange ocelli along the border of the hind wing. The ocelli are homologous under biological definitions, but they certainly are not mathematical homologs. Compare data: https://www.butterfliesandmoths.org/species/Battus-philenor https://www.butterfliesandmoths.org/species/Limenitis-arthemis Roughly speaking, if evolution acts as an anatomical homotopy, then two organisms along separate branches of a family tree should end up biological homologs. With Batesian mimicry, survival depends on homology, because predators need to see similar biological features to confuse a palatable species (here arthemis) with an unpalatable species (here philenor). However, biological homology is a looser concept than mathematical homology, and it is very possible that evolution introduces additional structures that disrupt mathematical homology. Comparing arthemis and philenor, the idea of a common ancestor is easy to accept. As it so happens, evolution has produced mathematically distinct ocelli. With arthemis, the eyespots are usually sole orange disks, each possibly connected to another black disk. Philenor has more complicated geometry involving an orange disk with black and white surroundings. To characterize the homology of two typical patterns for Philenor eyespots, I made the following disk-edge-vertex decomposition graphs: https://0x0.st/z4WA.png A next step would be to collect lots of data and measure area of disks, length of edges, and angles around each vertex. This would associate each graph vertex to a metric, thus would give a decent idea as to what an average philenor eyespot looks like. Of course, the same could be done for Arthemis. It would be an interesting exercise of bio-statistics to compare the orange-disk area metric between species. It looks that Arthemis has smaller spots, but survival of the species implies that the spots are not too small to ruin the mimicry effect. Another interesting question: is there a tolerance limit for pattern agreement, which bounds the ability of one species to effectively mimic another? Cheers --Brad

2 1

Re: [math-fun] Sugar + water paradox:
by Bill Gosper 01 Sep '19

01 Sep '19

On Wed, Mar 20, 2019 at 11:37 AM <Shy respondent> wrote: > [just us] > > I think you may just need to wait longer. > Yes. > If the water isn't stirred (either manually or by boiling) > then the liquid near the sugar pile will be highly saturated > and you'll have to wait for random thermal stirring to transport it away > But for several minutes, at least, the amount of dissolved sugar actually declines. On 2019-03-20 12:17, Allan Wechsler wrote: > The obvious question, for me, is how are you measuring this process? I > imagine that you could extract a cc of solution each minute, then evaporate > them and weigh the amount of sugar in each. But I think you're probably not > doing that, but rather relying on some kind of visual measure. What is the > observed dynamic? Does it dissolve for a while until the concentration hits > a plateau, and then sugar starts to precipitate out? Exactly! There's way more sugar in the bottom after it cools for a while. Huge density gradient from lack of stirring. You should have no trouble observing this. Unless I decontrolled it with a teabag of Stash Double Bergamot. —rwg > > On Wed, Mar 20, 2019 at 1:57 PM Bill Gosper <billgosper(a)gmail.com> wrote: > >> Dump a couple of Tbsp of sugar into a quart or two jar of tepid water. >> Don't stir. >> 𝜇wave a couple minutes, hot but not boiling. Let it sit. Experimental >> claim: >> The total dissolved sugar is not an increasing function of time, even >> though a >> couple of Tbsp is << enough to saturate even cold water. >> —rwg > > > > On Mar 20, 2019, at 10:57 AM, Bill Gosper <billgosper(a)gmail.com> wrote: > > > > Dump a couple of Tbsp of sugar into a quart or two jar of tepid water. > > Don't stir. > > 𝜇wave a couple minutes, hot but not boiling. Let it sit. Experimental > > claim: > > The total dissolved sugar is not an increasing function of time, even > > though a > > couple of Tbsp is << enough to saturate even cold water. > > —rwg > > _______________________________________________ > >

2 2

[math-fun] Online bipartite matching question
by Richard Chatwin 31 Aug '19

31 Aug '19

Hi all, I wonder if anyone can provide some insight into the following problem. The idea is to analyze the performance of the Ranking algorithm for online bipartite matching with random arrivals as applied to a specific graph. Background: - Given a bipartite graph; call the two sides L and R - Assume a perfect matching exists - The nodes from R arrive in an online manner - The order of arrival is a random permutation of the nodes in R selected uniformly from among all such permutations - When node j in R arrives, its edges to nodes in L are revealed - The algorithm then selects one of the neighbor nodes in L that has not previously been matched to match to j - The Ranking algorithm selects a random permutation of the nodes of L uniformly from all such permutations - When node j in R arrives, Ranking matches j to the highest ranking unmatched neighbor to j in L Goal: - Given a bipartite graph, compute the competitive ratio achieved by Ranking on the graph - The competitive ratio is the expected size of the matching achieved by Ranking divided by the size of the perfect matching Specific graph G: - L consists of 2n nodes, labeled 1, …, 2n. Nodes 1, …, n are in L1; nodes n+1, …, 2n are in L2 - R consists of 2n nodes, labeled 1, …, 2n. Nodes 1, …, n are in R1; nodes n+1, …, 2n are in R2 - The adjacency matrix is given by: - A(i, j) = 1 if i = j - A(i, j) = 1 if i <= n and j > n - A(i, j) = 0 otherwise - In summary: - each node in L1 is adjacent to a unique neighbor in R1 - each node in L2 is adjacent to a unique neighbor in R2 - all nodes in L1 are adjacent to all nodes in R2 - Ranking will match all nodes in L1 and all nodes in R2 but whenever it includes edge (i, j) with i in L1 and j in R2, then the neighbor to i in R1 and the neighbor to j in L2 remain unmatched Specific goal: - Show that the competitive ratio of Ranking on G is a decreasing function of n with limit 0.75 Context: - This graph has been proposed in Karande, Mehta and Tripathi, Online Bipartite Matching with Unknown Distributions, to provide an upper bound on the performance of Ranking on online bipartite graphs with random arrivals. They provide a theoretical analysis to establish the 0.75 bound but I don’t believe their analysis. - I believe the bound can be established empirically via simulation. - I don’t see an obvious way to approach this from a theoretical perspective so, as it’s a cute problem that seems like it should be amenable to some form of probabilistic analysis, I thought I’d see if anyone here has any insight. Cheers, Richard

1 0

Re: [math-fun] https://en.wikipedia.org/wiki/Dragon_curve
by Bill Gosper 28 Aug '19

28 Aug '19

On 2019-08-28 09:34, Brad Klee wrote: > The article should also say something about limit-periodicity. > For example try: > > SetDragon[Root_, BinaryBranching_] := Append[ > Flatten[Reap[FoldList[(Sow[ > {x_Integer /; IntegerQ[ > Divide[x - #1 - (2^#2[[2]])*BitXor[0, #2[[1]]], > 2^(#2[[2]] + 1)]] :> 1, x_Integer /; IntegerQ[ > Divide[x - #1 - (2^#2[[2]])*BitXor[1, #2[[1]]], > 2^(#2[[2]] + 1)]] :> 0}]; #1 + (2^#2[[2]])* > BitXor[0, #2[[1]]] + 2^(#2[[2]] - 1)) &, > Root, Transpose[{BinaryBranching, > Range[Length@BinaryBranching]}]] > ][[2]]], _Integer :> "?"] > > ArrayPlot[ > Map[Range[0, 2^6] /. SetDragon[0, #] &, > NestList[Append[#, RandomInteger[{0, 1}]] &, > RandomInteger[{0, 1}, 1], 6]], > Mesh -> True, ImageSize -> 500] > Wow, for the first time on Planet Earth, an actual brillathong keyboard. Brad, this is too dense for me. For starters, is a Fourier transform pure point the same as a periodic point? I can see why the Wikipedist dodged this can of worms. The simplest Fourier transform I can find for Heighway's Dragon has for its coefficients infinite products of non-triangular 3⨉3 matrices. first few dragon harmonics <http://gosper.org/FDrags128.gif> —rwg > This definition clearly shows relation of the tiling > space to a binary tree, and also explains why the > Fourier transform should have pure points. It also > helps to explain why the dragon sequence shows > up as a factor in Socolar-Taylor tiling, and in other > hexagonal or square quadtree tilings. > > --Brad > > > On Wed, Aug 28, 2019 at 10:30 AM Bill Gosper <billgosper(a)gmail.com> wrote: >> >> is the usual mix of good and bad. >> Good: Illustration that 4 Dragons joined at the nose >> < https://en.wikipedia.org/wiki/Dragon_curve#/media/File:Dragon_tiling1.svg> >> fill a tile different >> from four joined at the tail >> < https://en.wikipedia.org/wiki/Dragon_curve#/media/File:Dragon_tiling2.svg>. >> Oops: Fails to note that twin1 >> < https://en.wikipedia.org/wiki/Dragon_curve#/media/File:Dragon_tiling3.svg> >> and twin2 >> < https://en.wikipedia.org/wiki/Dragon_curve#/media/File:Dragon_tiling5.svg> are >> *both* twindragons*.* >> (Svgs, but painted with a horrible fat brush that *ruins* the symmetry.) >> Howler: (Re: the bounding box) >> "Note that the dimensions 1, and 1.5 are limits >> <https://en.wikipedia.org/wiki/Limit_(mathematics)> and not actual values." >> There remains almost universal ignorance of Dragon curves being merely >> lousy plots of the (almighty) Dragon Function. Axis-aligned >> tangents to the Dragon image intersect it in (uncountable) Cantor sets! >> E.g., some points on the bottom edge (Im(z) = -1/3) have spacings >> {1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, >> 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, . . .}/1023. Next term: 4⨉171 - 1 = 683 >> This is *a276391**,* the spacings of *preimages* of quadruple points of the >> *Hilbert *curve! >> More incredibly, another subset of the tangent points along x-i/3 has >> differences >> {1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 170, . . .}/4080, with 170 >> instead of 171! Next terms: 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 680, . . . >> —rwg

2 1

[math-fun] https://en.wikipedia.org/wiki/Dragon_curve
by Bill Gosper 28 Aug '19

28 Aug '19

is the usual mix of good and bad. Good: Illustration that 4 Dragons joined at the nose <https://en.wikipedia.org/wiki/Dragon_curve#/media/File:Dragon_tiling1.svg> fill a tile different from four joined at the tail <https://en.wikipedia.org/wiki/Dragon_curve#/media/File:Dragon_tiling2.svg>. Oops: Fails to note that twin1 <https://en.wikipedia.org/wiki/Dragon_curve#/media/File:Dragon_tiling3.svg> and twin2 <https://en.wikipedia.org/wiki/Dragon_curve#/media/File:Dragon_tiling5.svg> are *both* twindragons*.* (Svgs, but painted with a horrible fat brush that *ruins* the symmetry.) Howler: (Re: the bounding box) "Note that the dimensions 1, and 1.5 are limits <https://en.wikipedia.org/wiki/Limit_(mathematics)> and not actual values." There remains almost universal ignorance of Dragon curves being merely lousy plots of the (almighty) Dragon Function. Axis-aligned tangents to the Dragon image intersect it in (uncountable) Cantor sets! E.g., some points on the bottom edge (Im(z) = -1/3) have spacings {1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, . . .}/1023. This is *a276391**,* the spacings of *preimages* of quadruple points of the *Hilbert *curve! More incredibly, another subset of the tangent points along x-i/3 has differences {1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 170, . . .}/4080, with 170 instead of 171! —rwg

2 1