User jc - MathOverflow

Answer by jc for How can I randomly draw an ensemble of unit vectors that sum to zero?

2013-05-20T11:48:53Z

Cantarella, Deguchi and Shonkwiler have recently begun investigating various ensembles of random polygons which, while not of the particular form you specified, may still be of interest.

I can't summarize their approach better than the abstract of their paper:

We build a new probability measure on closed space and plane polygons. The key construction is a map, given by Knutson and Hausmann using the Hopf map on quaternions, from the complex Stiefel manifold of 2-frames in n-space to the space of closed n-gons in 3-space of total length 2. Our probability measure on polygon space is defined by pushing forward Haar measure on the Stiefel manifold by this map. A similar construction yields a probability measure on plane polygons which comes from a real Stiefel manifold. The edgelengths of polygons sampled according to our measures obey beta distributions. This makes our polygon measures different from those usually studied, which have Gaussian or fixed edgelengths. One advantage of our measures is that we can explicitly compute expectations and moments for chordlengths and radii of gyration. Another is that direct sampling according to our measures is fast (linear in the number of edges) and easy to code.

Some of our methods will be of independent interest in studying other probability measures on polygon spaces. We define an edge set ensemble (ESE) to be the set of polygons created by rearranging a given set of n edges. A key theorem gives a formula for the average over an ESE of the squared lengths of chords skipping k vertices in terms of k, n, and the edgelengths of the ensemble. This allows one to easily compute expected values of squared chordlengths and radii of gyration for any probability measure on polygon space invariant under rearrangements of edges.

In a follow-up paper Cantarella, Grosberg, Kusner and Shonkwiler compute the total expected curvature for these random $n$-gons and thus extract bounds on knotting probabilities of hexagons and heptagons.

It turns out there is a relatively large literature on "random equilateral polygons", which is the model you are interested in. I don't think there is any known analytic formula for the probability - you would be looking for the measure of some rather complicated semi-algebraic sets corresponding to the components of the configuration space which correspond to knotted polygons. Thus people have primarily been studying properties of such random knots with Monte Carlo sampling.

Ken Millett is one of the experts on random knots and would be a great person to chat with about these questions. Here's one of his papers titled "The Generation of Random Equilateral Polygons"; which contains a discussion of methods used in the literature following variations of the idea that Joseph O'Rourke described above.

Of course, the hexagonal case has been studied numerically but I couldn't find a precise estimate in my searches. An early paper by Ken Millett which shows it as a data point on a curve of knotting probability versus number of edges can be found here.

Answer by jc for Picturing a Certain Torus and Klein Bottle

2013-05-15T11:03:38Z

Recall the following well-known picture of $K^2$ as a square with one pair of edges identified and the other pair identified with a twist.

Similarly, you can draw a picture of $K^2\times S^1$ as a cube with opposite faces identified, except that one pair of faces is identified with a twist as well (here the twist means that the faces are identified after a reflection through a line).

By thinking about various surfaces in this model, you can find the creatures you are searching for. The two-sided Klein bottle is just an obvious copy of the above picture of the Klein bottle - it's any slice of the cube such that the induced identifications of the edges from the face identifications looks like the picture above.

The one-sided torus is a different square slice of the cube, which we can identify from Kevin Walker's answer. The intersection of the one-sided torus with the picture of the two-sided Klein bottle above is the circle represented by a vertical line running from one blue edge to the other.

Answer by jc for Maximum number of edges $f(n,k)$ in a graph on $n$ vertices with no $k$-core?

2013-03-01T18:40:51Z

If I'm not confused, I believe the graphs you are searching for (with a $k-1$ core but no $k$-core, and adding any edge creates a $k$-core) are also called "maximal $(k-1)$-degenerate graphs," see e.g. the wikipedia article on degeneracy.

The paper "k-degenerate graphs" of Lick and White proves the following:

Corollary 1: Let $G$ be a maximal $k$-degenerate graph with $p$ points, $p\geq k$. Then $G$ has $kp-\binom{k+1}{2}$ [edges].

Answer by jc for Some questions about ideal knots

2013-02-28T01:07:19Z

Questions 1 and 2 are addressed in the paper "On the Minimum Ropelength of Knots and Links" by Cantarella, Kusner and Sullivan, which is cited in the wikipedia article on ropelength.

The proof of the existence (and $C^{1,1}$ regularity) of minimizers is in Section 2 and is an application of the direct method.

Some examples pertinent to your question about the uniqueness of minimizers are discussed at the end of section 3. Apparently there is a 1-parameter family of minimizers of a five-component link with length $2\pi+8$. I am not sure if there are any examples of non-uniqueness for knots though.

Jason Cantarella has probably written the most on finding numerical approximations to ropelength critical and ropelength minimal knots and links so he may be able to answer question 3. See for instance this paper on the shapes of ideal composite knots.

Largest hyperbolic disk embeddable in Euclidean 3-space?

2009-10-15T00:23:48Z

Hilbert proved that there's no complete regular (C^k for sufficiently large k) isometric embedding of the hyperbolic plane into R^3. On the other hand, the pseudosphere is locally isometric to the hyperbolic plane up to its cusps (though it has the topology of a cylinder). What's the largest hyperbolic disk (with Gaussian curvature -1) that can be smoothly (or C^2, say) isometrically embedded in R^3?

edit: This doesn't seem to be getting many views, so I'll bump this by adding in a rather easy lower bound from the pseudosphere. First, the pseudosphere is parametrized by the region PS={z | Im z ≥ 1, -π < Re z ≤ π} on the upper half plane model of H^2. Let z=x+iy, so that ordered pairs (x,y)∈ H^2 when y>0.

Next, Euclidean circles drawn on in the upper-half plane model with center (x,y\cosh r) and radius y\sinh r correspond to hyperbolic circles with center (x,y) and radius r. I can fit a Euclidean circle of radius π centered at (0,1+π) into the region PS. This corresponds to a hyperbolic disk of radius arctanh(π/(1+π)) ~ 0.993.

Surely one can do better?

edit2: fixed mistakes in formulas above (didn't affect the bound). Here're some pictures:

Answer by jc for Homotopy $\pi_4(SU(2))=Z_2$

2012-12-10T17:20:49Z

This is really just a handwavy but perhaps more "visual" description of Pontryagin's result as cited by solbap in the comments above. Though I've written a huge block of text, there are some reasonably concrete three-dimensional pictures that you can build up in your head in this case, but it does take quite a bit of practice.

First, I assume that you are familiar with Pontryagin's construction relating the homotopy classes of maps to the k-sphere with framed (co-)bordism classes of codimension k submanifolds.

Check out Milnor's book Topology from the Differentiable Viewpoint if you're not familiar with this. Because your user profile says that you are interested in condensed matter physics, I'll add that this idea is used in the case of $k=2$ to draw some nice pictures of "homotopies around defects" in this paper of Teo and Kane.

Warmup, $\pi_3(S^2)$

As a warmup, let's try to visualize homotopy classes of maps from $S^3$ to $S^2$, i.e. the situation of the Hopf fibration. Pontryagin's construction says that we should be looking at bordism classes of framed codimension 2 submanifolds in $S^3$. 3-2=1, so we should be looking at 1-dimensional submanifolds, i.e. links in $S^3$. Here we have framed links in $S^3$ which can be visualized by drawing each component of the link with another parallel copy that winds around it, much like a ribbon.

You should convince yourself that all components in these framed links can be merged together into a single unknot with some integer framing. Thus what matters ultimately is the classification of possible framings. Imagine taking a 2D slice of $S^3$ transverse to a point $p$ of the framed link and placing the point $p$ at the origin of that plane. Then the framing at that point is just a choice of the $x$- and $y$- axes (i.e. a 2-dimensional frame). As we carry this plane along the original unknot, this choice of axes can rotate in that plane and so the classification of framings is naturally an integer. You may check that the inverse image of the North pole of the Hopf fibration is an unknot, and the inverse image of any other point on the sphere is an unknot which is linked once with it. Finally, you should see how you can build up any other homotopy class from "adding" Hopf fibrations together by putting multiple copies of this framed unknot together (possibly with opposite orientations), which gives a visualization of the group structure on the set of homotopy classes.

In this way you get a visualization of $\pi_3(S^2)$ by means of some pictures of framed circles. I can't resist here adding a link to this paper of DeTurck et al which gives some beautiful illustrations and description of the homotopy classes of maps from $T^3$ to $S^2$ with this tool.

$\pi_4(S^3)$

Now, you are interested in the case of homotopy classes of maps from $S^4$ to $S^3$. In this case you are now looking at framed links in $S^4$. You can still arrange for the link to become a single framed unknot by a sequence of bordisms. However, the framing can no longer be drawn with simply just a single parallel knot. Consider taking a 3-dimensional slice transverse to a point $p$ on the link in $S^4$ and let us place $p$ at the origin of our $R^3$ that we sliced with. In $S^4$, the framing of the link yields a choice of a 3-dimensional frame in this $R^3$ slice. And just as the relevant topological invariant of the framing in $S^3$ was how this frame rotates as we travel along the $S^1$ corresponding to our link component, leading to an element of $\pi_1(S^1)$ (the winding number), in $S^4$, we must now track how this 3-d frame rotates as we follow the $S^1$ of the link component. But now we are considering a continuous loop of choices of 3-dimensional orientations, i.e. an element of $\pi_1(SO(3))$, which is well known to be $\mathbb{Z}/2\mathbb{Z}$.

With this key ingredient of the 3-dimensional framing, hopefully you can see that $\pi_4(S^3)=\pi_1(SO(3))=\mathbb{Z}/2\mathbb{Z}$.

Answer by jc for The geometry of crinkled aluminum foil

2012-11-05T01:48:12Z

Crumpled structures are certainly of great interest among some soft matter physicists; you might with this review article of Tom Witten's. He also has a nice webpage with some nice pictures and summaries of papers of his on related topics.

My understanding is that while we have some handle on the behavior of the cone-like and ridge-like singularities that are forced by the crumpling, not much is known about how they end up distributed after crumpling, though see this nice recent PNAS article from UMass on X-ray scans of crumpled metal foil balls.

I might add more later, but these references and their references, etc. should be enough to get you started. There are indeed many beautiful problems in the area of elasticity of thin sheets.

Answer by jc for Surfaces in $\mathbb R^3$ with negative curvature bounded away from zero

2012-11-01T09:40:33Z

Efimov proved that there are no $C^2$ isometric immersions of complete surfaces with negative Guassian curvature bounded away from zero.

N.V. Efimov, "Imposibility of a complete regular surface in euclidean 3-space whose Gaussian curvature has a negative upper bound" Soviet Math. Dokl. , 4 : 3 (1963) pp. 843–846 Dokl. Akad. Nauk SSSR , 150 : 6 (1963) pp. 1206–1209

One reference I know for this is chapter 10 of the book of Han and Hong, "Isometric Embedding of Riemannian Manifolds in Euclidean Spaces."

Edit: Tilla Klotz Milnor's paper "Efimov's theorem about complete immersed surfaces of negative curvature" is an exposition of this theorem in English. I've only looked at the introduction so far but it looks rather thorough.

Answer by jc for Determining homotopy classes [T^2, RP^2]

2012-10-24T00:43:00Z

The set of homotopy classes $[T^2,\mathbb{RP}^2]$ actually consists of the following:

The set $[S^1\vee S^1,\mathbb{RP}^2]$ consists of four elements, which I'll call $(1,1)$, $(-1,1)$, $(1,-1)$ and $(-1,-1)$. The notation refers to which element in $\pi_1(\mathbb{RP}^2)$ each $S^1$ maps to.

The homotopy classes $[T^2,\mathbb{RP}^2]$ which restrict to $(1,1)$ are indeed in one-to-one correspondence with the integers if you are looking at based homotopy and the natural numbers if you are looking at free homotopy.

The classes which restrict to $(-1,1)$, $(1,-1)$ and $(-1,-1)$ fall into only two distinct homotopy classes, corresponding to even/odd parity of the degree of that map $S^2\rightarrow \mathbb{RP}^2$ that you mentioned. You get the same count for both free and based homotopy here.

This is essentially worked out in a paper of Klaus Jänich. This paper of Bechtluft-Sachs and Hien uses the "Whitehead sequence" to calculate this as well.

There is however a hands-on way to see this:

The following Pontryagin-Thom type construction is a "computation in $T^2$" rather than in $\mathbb{RP}^2$ as you asked for but I hope it may help shed some light on these maps. These ideas are also very related to Ryan's last paragraph in his answer. A version of this written up for a physics audience is in section 2.3 of my thesis.

Recall that the Pontryagin-Thom construction give us bijections between the homotopy classes of maps from a manifold into another space and bordism classes of framed submanifolds. Most people who are familiar with this are familiar with the case of maps into spheres, but there are versions which work for maps into other spaces as well. In particular, since $\mathbb{RP}^2$ is the one-point compactification of a real line bundle (the Mobius strip), just as $S^n$ is the one-point compactification of $\mathbb{R}^n$ viewed as a bundle over a point, we get something relatively pretty here.

Given $f:T^2\rightarrow\mathbb{RP}^2$, we consider the inverse image of a copy of $\mathbb{RP}^1$ in $\mathbb{RP}^2$. For instance, a geometrical interpretation of $f$ is as an assignment of a line in $\mathbb{R}^3$ to each point on the torus; then we consider the locus of points on the torus such that the line field has no $z$-component.

Generically, "$f^{-1}(\mathbb{RP}^1)$" (abusing notation) is a set of curves on the torus (this is where the business of transversality comes into play). Furthermore, these curves carry maps to $\mathbb{RP}^1$ induced by $f$. I like to visualize this map by a rainbow coloring on the curves, i.e. points on the torus mapping to the same point on $\mathbb{RP}^1$ are colored the same.

Here's a picture of $\mathbb{RP}^2$ with a copy of $\mathbb{RP}^1$ colored.

We also need to keep track of how $f$ maps the normal bundle of these curves into the Mobius strip (I mean here the real line bundle version of the Mobius strip, which arises here from being the normal bundle of $\mathbb{RP}^1$ in $\mathbb{RP}^2$). That is, $f$ also gives a "Mobius-framing" to these colored curves.

One way to do keep track of this pictorially on $T^2$ is to do the following. First choose some point on $\mathbb{RP}^1$, say the point which we have decided to color blue; the fiber of the Mobius strip bundle over this point is a copy of $\mathbb{R}$ and we choose one ray to be the "positive" ray. Now, on each colored curve on $T^2$, whenever you see the color blue, draw an arrow pointing towards the side of the curve which points in the positive direction.

In this picture, I show the Mobius-framed colored curves in $T^2$ (the rectangle has opposite sides identified, of course) corresponding to the inverse image of $\mathbb{RP}^1$ from a certain map $f$. Note that I am marking the "positive side" of the normal bundle of the curves with + signs.

These Mobius-framed colored curves should be considered up to bordism. In terms of the pictures I've been describing, this works out to saying that we can isotope the colored curves, homotope the colorings on the curves (i.e. the maps to $\mathbb{RP}^1$) as well as performing the two following local operations:

For instance, the colored curves I showed above are related by a bordism to the following:

A version of the Pontryagin-Thom construction thus yields that the bordism classes of Mobius-framed colored curves on $T^2$ are in one-to-one correspondence with the elements of $[T^2,\mathbb{RP}^2]$. My reference for this is the last chapter of tom Dieck's recent book Algebraic Topology.

It's quite late here so I'm going to leave the details of the classification on $T^2$ for you to play around with (there's also more in 2.3.1 of my thesis).

Apologies for cutting this off so abruptly, feel free to ask for clarification in the comments.

Answer by jc for Applications of the notion of of Gromov-Hausdorff distance

2012-10-19T09:35:49Z

The scaling limits of several families of random graphs are shown to exist by using the idea of Gromov-Hausdorff convergence to certain random metric spaces.

For instance, uniformly chosen triangulations of the sphere with $n$ faces endowed with the graph distance have been proved to converge (in the Gromov-Hausdorff sense) after rescaling distances by $n^{-1/4}$ to a particular random metric space called the Brownian map. See the references in this earlier answer of mine.

Answer by jc for Ising entropy of a finite L_1 x L_2 lattice

2012-09-28T15:32:42Z

I had a fairly useless comment posted earlier which I apologize for. It turns out much is known though. Below everything is restricted to zero applied field.

For a finite square grid of size $m$ by $n$ with periodic boundary conditions, the expression for the partition function $Z$ (from which the entropy per site can be worked out) was given already by Kaufmann (note that you can find freely accessible copies of this paper through google) very shortly after Onsager's solution:

$Z=\frac{1}{2}(2\sinh(2H))^{mn/2}\left\{\prod_{r=1}^n\left(2\cosh(\frac{m}{2}\gamma_{2r-1})\right)+\prod_{r=1}^n\left(2\sinh(\frac{m}{2}\gamma_{2r-1})\right)+\prod_{r=1}^n\left(2\cosh(\frac{m}{2}\gamma_{2r})\right)+\prod_{r=1}^n\left(2\sinh(\frac{m}{2}\gamma_{2r})\right)\right\}$

where, $H=J/k_BT$, $H'=J'/k_BT$, $\cosh\gamma_j=\cosh(2H)\cosh(2H')-\sinh(2H)\sinh(2H')\cos(\pi j/n)$, with $J,J'$ being the coupling constants in the horizontal and vertical directions, respectively.

A fuller explanation is in chapter IV of McCoy and Wu's book "The Two-dimensional Ising model". Another way to derive the partition function which has proved useful for generalizations to antiperiodic boundary conditions was worked out in this paper by V.N. Plechko.

On an infinitely long cylinder with circumference $L$ I was able to find in a 2004 paper by Huang et al an expression for the free energy (with $J=J'=1$):

$f=-\frac{1}{2}\ln(4z)-\frac{1}{2L}\sum_p\int_0^{2\pi}\frac{d\phi}{2\pi}\ln\left[z+z^{-1}-\Phi_p(\phi)\right]$

where now $z=\sinh(2\beta)$ and $\Phi_p(\phi)=\cos\phi+\cos\frac{2\pi p}{L}$.

Answer by jc for slam-dunk or Kirby move

2012-08-08T21:12:39Z

The point of the slam-dunk is that it transforms a surgery diagram with two link components $K_1,K_2$ (satisfying the conditions you've already pointed out) to a surgery diagram with just the link component $K_2$ but with a different surgery coefficient. I believe the "second Kirby move" is called a 2-handle slide in Gompf and Stipsicz's book which is where I've learned this material. I may be misunderstanding your question or more likely, missing something, but a 2-handle slide doesn't change the number of components in your surgery diagram, whereas the slam-dunk does, so I don't see how to interpret the slam-dunk as a 2-handle slide.

What follows is how I see that the framing changes and is really a rewrite of pp.163-164 in Gompf and Stipsicz's book.

Let $T$ be the solid torus glued in during surgery on $K_2$. Because the surgery coefficient of $K_2$ is integral, $K_1$ intersects the disk $\{\text{pt}\}\times D^2$ once, and so once you pull $K_1$ into $T$, it is isotopic to $S^1\times\{\text{pt}\}$ in $T$. This means that $T$ is a tubular neighborhood of $K_1$. Thus if we were to perform the surgery specified by the coefficient $r$ on $K_1$ now, we would again just cut out $T$ and glue it back in a second time.

What has happened is that the integral surgery coefficient of $K_2$ ensures that surgery on $K_1$ ends up working with the same solid torus $T$ -- in some sense $K_1$ has been moved into the same spot that $K_2$ was (though strictly speaking $K_1$ sits in a new manifold after surgery on $K_2$). This means that we could instead of doing two surgeries on $K_2$ then $K_1$ which end up involving the same $T$, just perform one on $K_2$, but with a different surgery coefficient.

To see what that surgery coefficient is, let's consider the case where $n=0$. There the first surgery on $K_2$ is simply a $\pi/2$ rotation of $H_1(\partial T)$. This changes the slope of surgery on $K_1$ from $r$ to $-1/r$. For general $n$, we have $n$ additional twists in this picture so we get $n-1/r$.

Answer by jc for Homotopy of random simplicial complexes

2012-07-08T07:14:15Z

Babson, Hoffman, and Kahle have written a paper on fundamental groups of random 2-complexes. They worked with the Linial-Meshulam model whereby you begin with a complete graph on $n$ vertices and then add independently uniformly random 2-simplices.

Babson has just written a paper on the fundamental groups of clique complexes of Erdős–Rényi random graphs using similar techniques.

Answer by jc for Optimal pebble-packing shape

2012-07-08T10:03:05Z

As Brendan McKay and Aaron Golden pointed out in the comments, the density of these packings is extremely protocol dependent in experiments (that is, it matters a lot how exactly you throw and shake the particles). I believe a better defined question would be the "jamming"-type problem studied in the paper mentioned in my comment. (For readers who would like to know a little bit more about what I mean about jamming, see my answer to Joseph O'Rourke previous question). In jamming, there are many shapes that jam at densities higher than spheres; aside from the paper I cited above, you can see section 5 of the really quite nice review by Martin Van Hecke that I mentioned at the end of my previous answer. I don't know that anyone has searched for the shape that jams at maximum density in this paradigm though, and to me at least it is not as of high physical interest. This is because the particular density at the transition for each shape is not expected to be "universal" for this jamming transition, whereas quantities like the dependence of the various elastic constants as one approaches the transition are apparently universal.

Let me now get off my soapbox and give some evidence for my first paragraph by returning to the experimental situation of throwing bodies into a container and shaking until little changes. Here is a reference related to the paper cited in the comment by Ricky Demer which yields rather different results.

Baker and Kudrolli also did a series of experiments in 2010 on packing of various shaped dice under various protocols. Their results on the volume fraction are here:

Their comment on the paper of Jaoshvili et al is "Experiments on random packed tetrahedronal dice have been reported recently in Ref. 16. Volume fractions were said to be $0.76\pm.02$ if the observed packings were extrapolated to inﬁnite systems, but the protocol by which the packings were prepared was not clear."

Actually, back in 2006, Yu, An, Zou and Kendall wrote a simulation / experimental paper which explores various vibration and packing protocols; they claim that they can get balls to pack into close-packed configurations consistently. Despite only showing data for packings of balls, it has the intriguing comment "This packing method can also produce densest packing for nonspherical particles. For example, for cubes, we obtained $\rho_{max}\approx1$, and interestingly 1D, 2D, and 3D vibrations produced comparable results. "

The above is by no means exhaustive, there are many other such protocols and papers with a broad variety of results.

Answer by jc for Packing and isoperimetrics

2012-07-06T11:16:04Z

You probably already know this, but the problem of dividing 3-dimensional space into equal volumes with minimal interfacial area is called Kelvin's problem. It may be one limit of the problem you're considering.

You can read about the currently best-known solution in 3D on Wikipedia here and there are links to pages with 3D models and data. The Weaire-Phelan structure uses two types of cells though, which I guess would be rather inconvenient from your applied perspective. Kelvin's original conjectured solution uses only one type of cell.

In 2D the minimal perimeter solution is the honeycomb, as bees know and Thomas C. Hales proved.

While googling I found some talk slides by Hales on some recent work on the 3D problem which I found interesting as well.

Orbifold fundamental group in terms of loops?

2010-04-06T15:27:33Z

In chapter 13 in his notes on 3-manifolds, Thurston defines the orbifold fundamental group to be the group of deck transformations of the universal cover of the orbifold. He also makes a statement "Later we shall interpret $\pi_1(O)$ in terms of loops on $O$, but this interpretation doesn't seem to appear in his notes.

My question is, well, what is this interpretation, precisely?

Here are my thoughts so far:

The example I'm currently interested in is the 1-D orbifold S¹/ℤ₂. Its universal cover is ℝ. Deck transformations are generated by a translation by 2π, which I'll call T and a reflection about the origin R. There's relations $R^2=1$ and $TR=RT^{-1}$. If I haven't messed up, this is the same as the fundamental group of the Klein bottle as well (if someone can explain how to construct the Klein bottle from S¹/ℤ₂, I would greatly appreciate it as well!). How can I relate paths on S¹/ℤ₂ to loops in the Klein bottle? Oops, I mixed up something in my head. I'll have another question on this in the future, perhaps.

I think my main trouble is making all of these observations precise, so a good reference with standard terminology / theorems (with lots of examples like the one I've been thinking about) would be appreciated as well.

Answer by jc for Max/min problems related to associahedra or their duals (ions on balls revisited)

2012-03-14T21:31:11Z

If your question is simply whether the 4-D associahedron is dual to a simplicial polytope, the answer is yes, because all associahedra are simple polytopes. To see this, note that the vertices of $K_{d+2}$ correspond to strings of $d+2$ letters "saturated" by $d$ pairs of parentheses. The $d$ edges in the star of a vertex therefore correspond to removing any one of those $d$ pairs of parentheses.

However, deltahedra are simplicial polyhedra whose faces are all equilateral triangles, so maybe you are asking whether the simplicial polytopes dual to associahedra may be realized with faces that are regular simplices? Then the results of this paper of John Sullivan's which classifies "convex deltatopes" imply that the duals of higher dimensional associahedra cannot be convex deltatopes (I checked that the convex deltatopes he constructs do not have the right number of faces once the dimension is greater than 3), and I suspect that one may be able to show that the dual simplicial polytopes of associahedra can't be made into deltatopes at all.

On a side note I recommend changing the title of the question and making it more clear in the body precisely what you are asking. The reference to equilibrium positions of ions, while interesting, threw me off.

Answer by jc for Topological spaces made by identifying opposite faces of a cube?

2012-03-05T18:45:18Z

The ones that are manifolds were considered by Poincaré, and a nice discussion is on this page of the Manifold Atlas.

Answer by jc for Are there examples of non-orientable manifolds in nature?

2010-11-12T15:30:43Z

The real projective plane is the space of orientations for "nematic liquid crystals": these are materials (often found in your TV or computer screen!) composed of molecules shaped roughly like rods, which can point in any direction in 3D. However, they have no head or tail, so two antipodal orientations are identified. We can model nematic liquid crystals thus by a map from $U\subset \mathbb{R}^3$ to $\mathbb{RP}^2$.

The topology of the real projective plane thus comes into play when one thinks about "topological defects" in these materials. A topological defect is a sort of singularity, where in some tubular neighborhood of this defect the material is continuous, but at the points of the defect, there is a discontinuity. Furthermore, this defect is topological, in that it cannot be homotoped away locally.

With a bit of oversimplifying, $\pi_1(\mathbb{RP}^2)=\mathbb{Z}_2$ means that there is one nontrivial type of line defect (since $S^1$ surrounds a line) and $\pi_2(\mathbb{RP}^2)=\mathbb{Z}$ means that there are an infinite number of types of point defects in 3 dimensional nematic liquid crystals.

Here's a schematic image of a cross section of a line defect and a corresponding path on $\mathbb{RP}^2$ corresponding to a circuit around it. These are both from Jim Sethna's page:

Here's a photograph of droplets of nematic liquid crystal under crossed-polarizers from the lab of David Weitz. I won't say too much about the colors, but they correspond roughly to the orientation of the molecule. The sharp points at the center of each droplet are one or more point defects, discontinuities in orientation. The dark brush-like structures coming out of each point are the regions where molecules are oriented in directions parallel to the polarizers - thus it's kind of like the inverse image of two different points on $\mathbb{RP}^2$.

Roughly speaking, a homotopy class of a map from a 1- or 2-sphere to the projective plane being nontrivial, means that the defect cannot be smoothed away (otherwise there would be a homotopy to a constant).

This is part of a much bigger picture of course; and there are other nonorientable spaces that describe the order of materials. I've been vague above because all of this is explained quite beautifully in the article by N.D. Mermin, The topological theory of defects in ordered media Rev. Mod. Phys. 51, 591–648 (1979). For a quicker introduction, this online essay "Order Parameters, Broken Symmetry, and Topology" by Jim Sethna covers the basics.

I love this stuff, so let me know if you have any questions and we can correspond further.

Classifying maps into homogeneous spaces up to homotopy

2009-10-27T00:32:28Z

I'm still just a beginner in algebraic topology, but there's a specific problem I'd like to understand, which is how to classify maps from one space into another up to homotopy -- for instance, I've really enjoyed learning about the Pontryagin-Thom construction which yields homotopy classification of maps into S^2. For some applications that I'm interested in, it turns out that the homotopy classification of maps from manifolds into homogeneous spaces (of strictly lower dimension, if that helps) are of interest.

I guess what I'm asking is for a pointer in the right direction, since algebraic topology is such a large subject. I've read scattered results here and there on specific examples of the above, but I haven't found any systematic way of thinking about it yet. Is there one? Someone once said "equivariant cohomology" to me, is that useful?

Answer by jc for Maximum number of different 4-colorings of planar graphs of a given size

2012-01-06T19:50:59Z

This has been studied in the statistical mechanics literature on the antiferromagnetic 4-state Potts model. One place to start reading about recent work from this perspective is the introduction and first few sections of this paper by Salas and Sokal.

One particularly studied family is triangular lattice graphs, which is expected to be an integrable system in some sense of the term.

This structure has led to one result due to Rodney Baxter which I can easily quote here: For graphs with $n$ sites forming a triangular lattice, in the limit of large $n$, the number of 4-colorings is asymptotically $W^n$ where $W=\frac{3\Gamma(1/3)^3}{4\pi^2}\approx 1.46099$.

Jesper Lykke Jacobsen has conjectured formulas for corrections to this due to boundary and corner effects here.

I'm afraid my understanding is not developed enough to write further, but in any case you might write to Alan Sokal or some of the other authors of these papers for their perspective.

Answer by jc for A percolation problem

2011-12-02T22:08:51Z

I don't have anything rigorous to say, but let me share some images that may be useful or interesting to you. The Mathematica code to generate them is here. It's sparsely commented, so feel free to ask in the comments for clarification.

Below, the "out-component" is the set of vertices which are reachable by a directed path from the origin.

Here are a few example out-components at various $p$ in your model for a 161 by 161 grid:

I'm quite fond of this animated GIF file which shows the "averaged" out-component of the vertex at the origin in a 41 by 41 square grid as $p$ is tuned from 0 to 1 (in steps of 0.02). The intensity of a pixel corresponds to the frequency that that vertex was reachable from the origin in a set of 1000 pseudorandom configurations.

I'm not sure what to make of this pattern -- in particular, are they an artifact of the square boundary conditions, as they might cut off longer paths that would have made the dark regions parallel to the $x$ and $y$ axes reachable?

From the same data, here's the probability of percolation (existence of a directed path from the origin to the boundary of that 41 by 41 square grid) as a function of $p$:

And here's the mean fraction of the full grid that is reachable from the origin as a function of $p$:

Perhaps someone with more computer time can run do this with larger system sizes (my run took somewhere around an hour). I might do this for the last two graphs I showed, just to see how the transition sharpens for larger system sizes.

Edit. The last plot doesn't quite tell the full story about the distribution of out-component sizes.

Here's a plot showing the standard deviation of the out-component sizes:

Here's a sequence of plots showing histograms (from 1000 pseudorandomly generated configurations) of the fraction of total vertices reachable from the origin in a 41 by 41 grid at various $p$:

The distribution is bimodal sufficiently near $p=0.5$!

Here's a density plot of the fraction of vertices in the out-component as a function of $p$:

Answer by jc for Configuration space of points in Euclidean Space with fixed distances

2011-11-22T23:15:02Z

Your question is close to the setup for rigidity theory, though the results there are typically phrased in terms of a perhaps more modest goal:

Let $G=(V,E)$ be a graph. Is the space of embeddings $p:V\rightarrow\mathbb{R}^n$ of the vertex set which preserve the distances between vertices joined by edges in $E$, modulo isometries, discrete (local rigidity), or perhaps even a single point (corresponding to the concept of global rigidity)?

Some basic results are described in this paper of Asimow and Roth, and there are many other references on a variety of aspects of this theory on this REU webpage of Dylan Thurston's.

Answer by jc for Isostatic graphs and the Henneberg conjecture

2011-11-03T19:23:36Z

Question 2 can be addressed computationally by computing the ranks of generic rigidity matrices corresponding to the sequence of graphs.

I'll show below that the 6th 2-extension for one choice of sequence creates a non-isostatic set from an isostatic one (because a $K_{6,6}$ is formed exactly then). I'm not sure how much this changes as we change the sequence of 2-extensions, nor even how much freedom we have in performing these 2-extensions if we want to go from $K_6$ to $K_{7,6}$. I suspect that the key is in the formation of the cycle $K_{6,6}$.

Below I share what I did in Mathematica; perhaps the code will be helpful for further experimentation. It is a bit tedious, so search this page for "G6" if you want to skip to the exciting part.

First, I wrote some ugly code to compute a 4 dimensional rigidity matrix. No doubt this can be improved.

(* p is a list of 4 dimensional vectors corresponding to vertex positions, 
E is a list of the pairs of vertices {i,j} (with i<j) that are joined by edges *)
RigidityMatrix4[p_, E_] := 
 Module[{e = Length[E], nd = Length[p] Length[p[[1]]], px, py, pz, pw},
  Table[
   px = p[[E[[j, 1]], 1]] - p[[E[[j, 2]], 1]];
   py = p[[E[[j, 1]], 2]] - p[[E[[j, 2]], 2]];
   pz = p[[E[[j, 1]], 3]] - p[[E[[j, 2]], 3]];
   pw = p[[E[[j, 1]], 4]] - p[[E[[j, 2]], 4]];
   Insert[Insert[Insert[Insert[
       Insert[Insert[Insert[Insert[
           Table[0, {nd - 8}], px, 4 E[[j, 1]] - 3], py, 
          4 E[[j, 1]] - 2], pz, 4 E[[j, 1]] - 1], pw, 4 E[[j, 1]]],
       -px, 4 E[[j, 2]] - 3], -py, 4 E[[j, 2]] - 2], -pz, 
     4 E[[j, 2]] - 1], -pw, 4 E[[j, 2]]], {j, e}]]

Here's a function to create the list of edges corresponding to a complete graph:

makecompletegraph[l_] :=  Reap[Do[If[i != j, Sow[{i, j}]], {i, l}, {j, i, l}]][[2, 1]]

Now I begin by creating $K_6$ and deleting the edge {5,6}. The output is a list of the edges as pairs of vertices:

G = makecompletegraph[6][[1 ;; 14]]

{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}}

I next compute the number of nontrivial infinitesimal motions of a generic embedding of G and the number of redundancies among its edges:

R = RigidityMatrix4[RandomReal[{0, 1}, {6, 4}], G];
{MatrixRank[NullSpace[R]] - 10, Length[G] - MatrixRank[R]}

{0,0}

Thus G is isostatic.

I now perform the first 2-extension, by deleting the edges {1,2} and {3,4} and connecting a new vertex 7 to vertices 1 through 6, and check that the resulting graph "G1" is isostatic:

G1 = Join[Select[G, # != {1, 2} && # != {3, 4} &], Table[{i, 7}, {i, 6}]]
R1 = RigidityMatrix4[RandomReal[{0, 1}, {7, 4}], G1];
{MatrixRank[NullSpace[R1]] - 10, Length[G1] - MatrixRank[R1]}

{{1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}}

{0,0}

In the second step, I remove {1,3} and {2,4} and attach vertex 8 to vertices 1 through 6 to form G2, which is also isostatic:

G2 = Join[Select[G1, # != {1, 3} && # != {2, 4} &], Table[{i, 8}, {i, 6}]]
R2 = RigidityMatrix4[RandomReal[{0, 1}, {8, 4}], G2];
{MatrixRank[NullSpace[R2]] - 10, Length[G2] - MatrixRank[R2]}

{{1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}}

{0,0}

Next {1,5} and {2,6} are removed and vertex 9 is attached to vertices 1 through 6 forming the isostatic G3:

G3 = Join[Select[G2, # != {1, 4} && # != {2, 5} &], Table[{i, 9}, {i, 6}]]
R3 = RigidityMatrix4[RandomReal[{0, 1}, {9, 4}], G3];
{MatrixRank[NullSpace[R3]] - 10, Length[G3] - MatrixRank[R3]}

{{1, 5}, {1, 6}, {2, 3}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}}

{0,0}

{1,5} and {2,6} are removed; vertex 10 is attached, G4 is isostatic:

G4 = Join[Select[G3, # != {1, 5} && # != {2, 6} &], Table[{i, 10}, {i, 6}]]
R4 = RigidityMatrix4[RandomReal[{0, 1}, {10, 4}], G4];
{MatrixRank[NullSpace[R4]] - 10, Length[G4] - MatrixRank[R4]}

{{1, 6}, {2, 3}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}}

{0,0}

{1,6} and {2,3} are removed; vertex 11 is attached, G5 is isostatic:

G5 = Join[Select[G4, # != {1, 6} && # != {2, 3} &], Table[{i, 11}, {i, 6}]]
R5 = RigidityMatrix4[RandomReal[{0, 1}, {11, 4}], G5];
{MatrixRank[NullSpace[R5]] - 10, Length[G5] - MatrixRank[R5]}

{{3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}, {1, 11}, {2, 11}, {3, 11}, {4, 11}, {5, 11}, {6, 11}}

{0,0}

{3,5} and {4,6} are removed and vertex 12 is attached. The resulting graph G6 is not isostatic! Of course, this is because a $K_{6,6}$ is formed.

G6 = Join[Select[G5, # != {3, 5} && # != {4, 6} &], Table[{i, 12}, {i, 6}]]
R6 = RigidityMatrix4[RandomReal[{0, 1}, {12, 4}], G6];
{MatrixRank[NullSpace[R6]] - 10, Length[G6] - MatrixRank[R6]}

{{3, 6}, {4, 5}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}, {1, 11}, {2, 11}, {3, 11}, {4, 11}, {5, 11}, {6, 11}, {1, 12}, {2, 12}, {3, 12}, {4, 12}, {5, 12}, {6, 12}}

{1,1}

Just for completeness, I performed the last 2-extension; removing {3,6} and {4,5} and attaching vertex 13. You can see this is $K_{7,6}$:

G7 = Join[Select[G6, # != {3, 6} && # != {4, 5} &], Table[{i, 13}, {i, 6}]]
R7 = RigidityMatrix4[RandomReal[{0, 1}, {13, 4}], G7];
{MatrixRank[NullSpace[R7]] - 10, Length[G7] - MatrixRank[R7]}

{{1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}, {1, 11}, {2, 11}, {3, 11}, {4, 11}, {5, 11}, {6, 11}, {1, 12}, {2, 12}, {3, 12}, {4, 12}, {5, 12}, {6, 12}, {1, 13}, {2, 13}, {3, 13}, {4, 13}, {5, 13}, {6, 13}}

{2,2}

Answer by jc for Growing random trees on a lattice $\rightarrow$ Voronoi diagrams

2011-09-28T16:35:05Z

Update:

I think your model for growth has been studied before and goes by the name of the Eden growth model (See section 4 of the (linked) original paper by Murray Eden). It seems what is usually studied is a "site addition" model, whereas your model is a "bond addition" model, but I bet the main results will be the same. I haven't managed to find any recent reviews focusing just on the Eden model yet (and the Wikipedia page is sadly very sparse), but I found a description of it in the first pages of this book chapter of Jean-François Gouyet's "Physics and Fractal Structures".

Famously, the interface of the Eden model was the motivation of Kardar, Parisi and Zhang when they defined the universality class now known as KPZ. Here's a nice review of the KPZ universality class by Ivan Corwin.

Thus a lot is (conjecturally) known about this -- in particular, the size of the fluctuations at the perimeter of a single tree with $N$ bonds should scale as $N^{1/6}$ (fluctuations go as radius$^{1/3}$, and I am pretty sure the radius goes like $N^{1/2}$). Because of this site versus bond addition discrepancy, I haven't found anything about colliding Eden clusters, but I think these ideas can justify that you do get Voronoi cells. I would be delighted to hear criticism or details from an expert!

I don't have anything rigorous to say yet, but some post-facto intuition for Q2 is as follows.

Consider the case of a single seed. I'll tell a story about why the growth from a single seed ought to look more or less like a disk with a wiggly edge, rather than something with a lot of branchy and spread-out fingers (like something one gets out of diffusion-limited aggregation, for instance). If you buy my story, then it should be clearer why there isn't that much "entanglement" at the interfaces between two such growing bodies.

At a given time step $i$, we have a tree $T_i$; let the set of edges that connect $T_i$ to $\mathbb{Z}^2\setminus T_i$ be $G_i$. Then we may form $T_{i+1}$ by choosing uniformly an edge in $G_i$ and adding it to $T_i$. So far, this is just your process in different terms. Here comes some handwaving. Any "protrusions" on $T_i$ will not get too long, because to grow a subset of $T_i$ which sticks out a significant distance from the rest of $T_i$, we'd have to had chosen edges near the "tip" of this protrusion repeatedly. But of course the tip of a long protrusion has a small perimeter compared to the sides of the protrusion, and thus it's much more likely that added edges will smooth out any such features instead of extending them.

Why does this end up with something disk-like? Your process is basically one where you add a "protrusion" to the tree centered somewhere uniformly random on the "boundary". Thus consider the following "off-lattice" version of your process. Let $T_0$ be a disk of radius 1 centered at the origin. $T_i$ is the union of $T_{i-1}$ with a disk centered at a point $p_i$ chosen uniformly from the boundary of $T_{i-1}$. I hope you can see that this is a stochastic version of normal evolution of the boundary. And as is well-known to doodlers, normal evolution tends towards to circular disks, so "intuitively" a stochastic version will tend to a wiggly disk. (One complication here is that your process isn't allowed to form loops in the tree, whereas the continuum version I have in mind does).

Answer by jc for Determine if circle is covered by some set of other circles

2011-09-29T01:41:52Z

I believe Herbert Edelsbrunner's work on alpha shapes may have some relevance, though when I was reading about it I was mainly interested in applications to determining volume and surface areas so I'm not sure if the precise question you are asking is addressed. See the papers here on his website, perhaps starting with the paper: H. Edelsbrunner. The union of balls and its dual shape. Discrete Comput. Geom. 13 (1995), 415-440.

The abstract of that paper:

Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in $\mathbb{R}^d$ . These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in $\mathbb{R}^3$ where unions of finitely many balls are commonly used as models of molecules.

I think the main idea is basically that suggested by Anton Petrunin.

Answer by jc for Random bipartite graphs

2011-09-23T19:59:00Z

I was interested in connectedness thresholds for random bipartite graphs a while back and have a few scanned journal articles that you might find helpful. I'll leave up the links until I am threatened by lawyers.

I think the most detailed work on thresholds is the paper A. Ruciński, "The r-connectedness of k-partite random graphs" Bull.de l'Acad. Pol. des Sci., 29/7-8 (1981) 321-330 which is tough to find electronically, but I have a rather poorly scanned copy here.

The abstract is:

In this paper we consider the asymptotic structure of $k$-partite random graph, when the number of its edges is a threshold function for the $r$-connectedness, $r\geq1$. We also give the probability of the $r$-connectedness of $k$-partite random graph. (Our theorem generalizes results of Palasti [10].)

Beware! I'm not kidding when I say the scan quality is poor.

The paper [10] (I. Palasti, On the connectedness of bichromatic random graphs, Publ. Math. Inst. Hung. Acad. Sci., 8 (1963), 341-440) cited in the abstract was also hard for me to get and I have a scan here. This paper only considers the case of $(n,cn)$ in your notation though, but it's the first paper I know of to look at connectedness of bipartite random graphs.

Two other somewhat related papers and my rough descriptions.

I.B. Kalugin shows in "The number of components of a random bipartite graph", Discrete Math. Appl. 1(3), 289-299 (1991) that for small probabilities $(p< 1/\sqrt{nN})$ the component sizes are Poisson distributed. Scan is here.

A.I. Saltykov shows in a similarly named paper "The number of components in a random bipartite graph", Discrete Math. Appl. 5(6) 515-523 (1995) that near the connectivity transition, there's really just one huge component and a Poisson distributed number of isolated vertices. Scan is here.

Answer by jc for Geodesics in $\mathbb{R^2} \times \mathbb{S^1}$ under "segment" metric

2011-09-23T06:24:18Z

What follows are just some illustrations, not a full answer; please refer to Anton Petrunin's answer for a nice description of the 4 dimensional geometry that the original question is embedded in.

Here's a bit of Mathematica code to generate some crude discrete approximations to geodesics. Given the two endpoint segments $s_0,s_1$, I create $n$ segments on the naïve $s_\alpha$ path I defined in the comments above, normalize their lengths to one, and then vary the positions of the endpoints of these intermediate segments with Mathematica's FindMinimum function to find an approximate geodesic. The code I wrote looks for a local minimum of an objective function with two terms: one is just the sum of the distances between all the intermediate segments and the other is a constraint that forces the distances between each pair of adjacent segments on the path to be equal (otherwise the intermediate segments all flow to the endpoints). The segments are all constrained to have unit length.

As Mathematica is not really good at a serious minimization problem, the code runs rather slowly (finding a discrete path with $n=10$ takes about 7 minutes), but perhaps you might still be able to get some more direct intuition for the geodesics by playing around with it in different cases. It's a start, anyways.

Below is an image of one example. The endpoints are a segment with endpoints $(0,0)$ to $(1,0)$ (orange) and $(1,0)$ to $(1,1)$ (red), and I approximated a geodesic with a chain of $n=10$ segments. The path begins with the orange segment sliding upwards a tiny bit to "yellow", and then the segments rotates counter clockwise and translate right until they reach red.

The segment distance between red and orange is $\frac{1}{8}\left(4+\sqrt{2}\log(3+2\sqrt{2})\right)\approx0.8116$, but the length of the approximate geodesic is $0.865$. Each pair of "adjacent" segments in the picture has a segment distance roughly 0.096 between them.

With $n=10$, the length has not converged to high accuracy! For $n=7,8,9$ the lengths of my approximations are $0.857,0.884,0.876$, respectively. In any case, it's clear that the length of the true geodesic will be greater than the distance between the endpoints. You might stare at this picture and imagine the true geodesic "hugging" the 3 dimensional unit length segment hypersurface in the 4D space, whereas the distance measures a "chord" through the 4 dimensional space of segments with arbitrary length.

update

As Joseph O'Rourke points out in the comments, the code is not very good with (anti-)parallel configurations. What seems to work is to give either segment a slight perturbation.

As an example, here's an approximate geodesic ($n=10$ points) between a segment with endpoints $(1,0)$ to $(2,0)$ (orange) and a segment with endpoints $(-1,0)$ to $(-1+\cos(\pi+0.001),\sin(\pi+0.001))\approx(-2+5\times10^{-7},0.001)$. The distance between the endpoints is $\approx3-2\times10^{-7}$, but the length of the depicted approximate geodesic is 3.30 (with steps of about 0.367).

Interestingly, this approximate geodesic seems to break symmetry in two ways. First, the segments rotate clockwise while traveling left. Second, the picture doesn't have left-right symmetry, which means that the first half of the journey is different from the second half (an analogue of this can be seen in the example above too, which doesn't have reflection symmetry across the -45º line). Is the second effect just due to discretization or non-convergence of the minimization? I don't know how to show that the true geodesics must be symmetric if there's some symmetry relating the two endpoints.

code snippet for this:

a1 = {1, 0}; b1 = {2, 0}; a2 = {-1, 0}; b2 = {-1 + Cos[\[Pi] + .001], Sin[\[Pi] + .001]};
Timing[anti3 = FindChain[{a1, b1}, {a2, b2}, 10]]
SegmentDist2[{a1, b1}, {a2, b2}]
Table[SegmentDist2[anti3[[i]], anti3[[i + 1]]], {i, 9}]
Sum[SegmentDist2[anti3[[i]], anti3[[i + 1]]], {i, 9}]
Graphics[Table[{Hue[i/Length[anti3]], Line[anti3[[i]]]}, {i, Length[anti3]}]]

Answer by jc for A formal definition of Scaling Limits?

2011-09-05T16:48:18Z

I think the notion of scaling limit is really more of a group of ideas than a single definition, since there are different types of objects being studied and hence different notions of convergence. Typically though one considers convergence of some (rescaled) sequence of probability measures on "discrete" objects as a spatial parameter $\delta\rightarrow0$ to a probability measure on some "continuum" object. Part of the trouble is that it can be tricky to figure out what the right "continuum" object is and further how to put a probability measure on it. A nice discussion about scaling limits and conformal invariance are these lecture notes by Lawler.

The fundamental example of such a scaling limit is the convergence of random walks to Brownian motion; one source is chapter 5 of the book of Mörtens and Peres.

An interesting scaling limit with a different flavor than the SLE ones described in other answers is Aldous's Continuum Random Tree. The following is from the linked page:

Take a critical Galton-Watson branching process where the offspring law has finite non-zero variance, and condition on total population until extinction being $n$. This gives a random tree. Rescale edge-lengths to have length $n^{-1/2}$. Put mass $1/n$ on each vertex. In a certain sense that can be formalized, the $n \to \infty$ weak limit of these random trees is the Brownian CRT (up to a scaling factor).

This is a beautiful object on its own but also a key tool in several other scaling limits.

The CRT is used in the study of random planar maps, see these lecture notes of Le Gall and Miermont. Recent developments not covered in these notes are their proofs of the convergence of certain families of random planar maps to the so-called Brownian map (see here and here).

The CRT is also part of the construction of the scaling limit of connected components of Erdős–Rényi random graphs in the scaling window.

Answer by jc for Random graphs in $\mathbb R^2$ (or random rays from $\mathbb Z^2$)

2011-08-31T07:53:29Z

edit:

At Tom LaGatta's request, here are a few more very rough graphs relating to the number of components. For $n=3,\dots,15$, I ran just 10 instances of each (took about 15-20 minutes). Hopefully that's enough to give a little bit of the idea of the spread.

Here are the total number of components (with size>1) versus $n$. I noticed that it appeared parabolic, so I plotted it on a log log scale with the function $n^2/3$ (the factor of 1/3 just happened to be close). Each data point corresponds to a different instance.

Here on a semi-log scale are the distributions of numbers of components (with size>1). The different colors correspond to distributions observed in different instances. They look much better on semi-log as opposed to log-log, though that's fairly meaningless with not even a decade of data and small number effects.

Code for this section (run with the functions in the notebook linked to below):

(* code to generate data, change parameters as needed *)
minn = 3;maxn = 15;numruns = 10;
data = Table[test = Flatten[makegrid[n, n], 1];Truncate[test], {j, numruns}, {n, minn, maxn}];
(* code to process and plot data *)
averagecomponents = Table[{n, Length[data[[i, n - minn + 1, 2]]]}, {n, minn, maxn}, {i, 
numruns}];
plot1 = ListLogLogPlot[averagecomponents, AxesLabel -> {"n", "total number of components"}];plot2 = LogLogPlot[x^2/3, {x, 1, maxn}];Show[plot1, plot2]
compdist = Table[Table[Tally[Table[Length[data[[j, n, 2, i]]], {i, averagecomponents[[n, j, 2]]}]], {j, numruns}], {n, maxn-minn+1}];
ListLogPlot[compdist[[12]], PlotStyle -> PointSize[Large]]
ListLogPlot[compdist[[13]], PlotStyle -> PointSize[Large]]
GraphicsGrid[Partition[Table[ListLogPlot[compdist[[j]], PlotStyle -> PointSize[Medium], PlotLabel -> "n=" <> ToString[j + minn - 1], AxesLabel -> {"size of component", "frequency"}], {j, maxn - minn + 1}], 3, 3, {1, 1}, {}]]
(* not shown: number of infinite rays *)
numinfinities = Table[{n, Count[data[[i, n - minn + 1, 1]], Infinity]}, {n, minn, maxn}, {i, numruns}]

original answer:

I wrote a bit of Mathematica code to try to simulate your process (link here). I only partially commented things, so let me know if you have trouble understanding how to use it. More on this after some pictures and graphs.

I apologize in advance, I don't have the time now to do a real systematic study or gather any real statistics on my computer. I'll have to leave it to you or other interested readers...

I didn't bother to add boundary conditions to cut off the rays leaving the grid. Below, components of size 1 are just rays that don't terminate.

5x5:

8x8:

15x15 #1:

Number of components of a given size for 15x15 #1:

Stopping time distribution for 15x15 #1 (excluding infinite rays, of which there are 6):

15x15 #2:

Number of components of a given size for 15x15 #2:

Stopping time distribution for 15x15 #2 (excluding infinite rays, of which there are 7):

Note: I didn't see any cycles at all, but I had to check this by eye, since I didn't write a routine to extract the graph structure of the connected components. What I have now just records their size.

There is what looks like a cycle in the upper left quadrant of 15x15 #1, but you can easily convince yourself by comparing the lengths of the edges that the rays couldn't actually touch.

I used pretty much the most naïve algorithm I could think of:

Generate a pseudorandom angle at each grid point, and thus get a set of lines.
Find the intersection times of all pairs of lines. (Lines are naturally parametrized as $x(t)=x_0+t(\cos\theta,\sin\theta)$, where $x_0$ is the starting point and $\theta$ is the angle.)
From this set of pairs, select pairs of rays that intersect in positive time rather than negative, and sort from smallest time to largest.
Choose the intersection that occurs at the smallest time, mark the two rays involved as truncated, and record the connected component formed by this as a new one, and record the time of intersection as the "ending time" for the two rays.
Check the intersection occurring at the next smallest time to see whether it's been preempted by existing rays (by comparing the intersection times with ending times), and if the intersection passes the test, mark these rays as truncated, and record the connected component and any new ending times as in 4.
Repeat 5. until all intersections or all rays have been eliminated.

What are smarter ways of doing this?

Because of 2., the code runs rather slowly, probably $O(n^4)$ for an $n$ by $n$ grid ($n^2$ gridpoints, thus $(n^2)^2$ possible intersections). An instance at $n=15$ takes about 40 seconds on my machine to run.

Comment by jc

2013-05-22T10:31:51Z

@Joseph O'Rourke The paper can be accessed here: citeseerx.ist.psu.edu/viewdoc/… However, it addresses the number of components of the space of embeddings (i.e. which types of knots are possible and how they may be realized) and not the relative measure of these components (how probable each knot type would be).

Comment by jc

2013-05-12T11:17:53Z

The question in the title differs substantially from the only question I see in the body "What did I wrong?"

Comment by jc

2013-05-07T20:31:26Z

You might find the following question interesting mathoverflow.net/questions/119095/…

Comment by jc

2013-04-26T13:04:03Z

The way you are understanding $\pi_3(S^2)$ is via the Pontryagin-Thom construction, which yields a correspondence between bordism classes of framed submanifolds (framed links in $S^3$) and homotopy classes of maps (elements of $\pi_3(S^2)$) via looking at inverse images. In the case of $\pi_4(S^2)$, the inverse images are (generically) framed surfaces in $S^4$, which are at least to me much harder to visualize. I did describe the situation for $\pi_4(S^3)$ here, which might help: mathoverflow.net/questions/115866/…

Comment by jc

2013-03-01T11:09:25Z

There are a few closely related questions here mathoverflow.net/questions/37708/… mathoverflow.net/questions/76955/…

Comment by jc

2013-02-19T18:18:49Z

As your question is about to be closed, please have a look at the FAQ and "how to ask" pages that are linked to at the top of every page on this site. Perhaps then you can edit your question and it might be reopened.

Comment by jc

2013-01-08T15:04:09Z

Here's a link to "On nuclear forces": dl.dropbox.com/u/8101832/PhysRev.50.846.pdf

Comment by jc

2012-12-13T11:59:51Z

Thanks, feel free to ask for clarification; it can be hard to describe the pictures without a chalkboard.

Comment by jc

2012-12-11T01:54:46Z

The monograph "Realization spaces of polytopes" by Jürgen Richter-Gebert covers much of what is known about such spaces. It is published by Springer though a PDF used to be available on his website. There are still copies archived on citeseer and other sites.

Comment by jc

2012-12-10T19:14:15Z

High rep users can probably see this deleted question, which I found using google: mathoverflow.net/questions/115642/…

Comment by jc

2012-12-10T17:39:47Z

By eye it seems this curve is quite hard to distinguish from an ellipse and I guess it probably looks quite like a circle (the radius in the x-direction seems to be about 45 and the radius in the y-direction maybe 47), though it apparently is not. Could you show a plot with aspect ratio of 1?

Comment by jc

2012-12-06T15:55:42Z

The homotopy that the question asks for is not obvious here; could you give some more detail?

Comment by jc

2012-12-06T12:57:15Z

Here are a few examples that I can't find homotopies for but are examples that fit the title. First, some obvious ones: tilings / wallpaper patterns are covering maps of the torus (certain orbifolds if you want); In nature, crystal structures give many nice examples as well e.g. en.wikipedia.org/wiki/Diamond_lattice . A nice set of examples are triply periodic minimal surfaces en.wikipedia.org/wiki/… , which amazingly are realized in certain soft materials e.g. jstor.org/stable/54307 .

Comment by jc

2012-11-22T09:55:12Z

You should edit your question so that you ask what you really want, and include some more details (see for instance mathoverflow.net/howtoask ). Then it might possibly be reopened.

Comment by jc

2012-11-18T12:33:05Z

re: 2) see community.middlebury.edu/~mathanimations/…