User günter rote - MathOverflow

Answer by Günter Rote for The Cayley Menger Theorem and integer matrices with row sum 2

2013-04-26T22:13:12Z

Let us first consider an $n\times n$ matrix with zero diagonal and $n(n-1)$ indeterminates. Every term (monomial) of the determinant corresponds to a permutation matrix $P$ with zero diagonal (i.e., an integer nonnegative matrix with trace 0 and row and column sums 1).

Let us now consider a symmetric $n\times n$ matrix with zero diagonal and $n(n-1)/2$ indeterminates $a_{ij}=a_{ji}$. Then every term corresponds to a permutation matrix $P$ as before, but the correspondence is not one-to-one, since symmetric elements are equal. We can get a one-to-one correspondence by associating the term to $P+P^T$ (the "symmetrized version" of $P$): an integer nonnegative matrix with trace 0 and row sums 2. The coefficient of the term is the $\det(P+P^T)$.

Now, in the Cayley-Menger determinant, the entries of the first row and column are not indeterminates but ones. We have to argue that this does not cause a "loss of information". In fact, the matrix $P+P^T$ is the adjacency matrix of a 2-regular undirected graph $G$ on $n$ vertices, without loops but potentially with multiple edges. This graph is a straightforward representation of every monomial in the determinant. Setting all variables $a_{12},a_{13},\ldots,a_{1n}$ to $1$ corresponds to eliminating the edges incident to vertex 1, resulting in a graph $G'$ on $n-1$ vertices. However, since $G$ was 2-regular without loops, we can uniquely identify the missing edges: they are incident to the vertices of degree less than 2 in $G'$.

The coefficient of the monomial is still the determinant of $P+P^T$, which equals $\pm2^k$, where $k$ is the number of cycles of length at least 3 in the graph $G$. The sign is the sign of the (more precisely, of any) permutation $P$.

Answer by Günter Rote for All possible linear combinations of positive half-integers with coefficients +/- 1

2013-03-06T01:27:47Z

Indeed it is the Subset Sum Problem (or closely related to it). This problem asks essentially whether $\mu(P)>0$. It is only weakly NP-complete, and there is a pseudopolynomial dynamic-programming algorithm for it. You can find it in any textbook on algorithm design. More precisely, if the sum of the $p_i$'s is $B$, you can solve it in $O(nB)$ time. Whether this is practical depends on the size of the numbers. (The other suggested solutions, which multiply polynomials, are another way to express the same algorithm. Your question suggests that $\mu(P)$ is not just 0 or 1, and apparently, the numbers are not so big.)

Answer by Günter Rote for Brute force lattice problems

2013-02-27T16:48:25Z

This sounds like you should consider the Fincke-Pohst algorithm. There are many implementations, see for example these slides.

Answer by Günter Rote for Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

2013-02-19T21:27:24Z

The better analogy when the markers are distinct is not Sokoban, but the 15-puzzle. It is even on an undirected graph.

All my remarks below are about the undirected version. ADDITION: At the end there is a remark about the application to the directed case. (My brief literature search turn up only one paper with directed graphs, for a single pebble (robot) with obstacles whose final position is irrelevant.) The upshot is:

On undirected graphs, the decision version ("Does a solution exist?") is solvable in polynomial time, but minimizing the number of moves is NP-hard.

There is a short paper by Oded Goldreich, dating back to 1984 but published only in 2011, "Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard". Ratner and Warmuth showed (Journal of Symbolic Computation, 1990) that this is true even for the extension of the 15-puzzle to larger squares.

Richard Wilson has characterized in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on a general biconnected $n$-vertex graph, like in the 15-puzzle. According to a recent paper by Gabriele Röger and Malte Helmert, Kornhauser, Miller, and Spirakis ("Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984) extended these results to the case when fewer vertices are occupied and to more general graphs, and showed that there is a solution with $O(n^3)$ moves if there is a solution at all. (I haven't looked at this paper. Anyway, Röger and Helmert recommend to find more details in the tech-report, which contains Daniel Kornhauser's Master's theses.)

For directed graphs which are biconnected and strongly connected, one can apply the characterizations of the undirected graph case, because a "backward move" can always be simulated: Let $ab$ be an arc and suppose we would like to move a pebble $X$ from $b$ to $a$. Find a directed cycle through $ab$ and push the vertices on this cycle through, but don't make the last move of pebble $X$ from $a$ to $b$. This realizes a backward move by $O(n^2)$ forward moves. This yields a linear-time decision algorithm and an $O(n^5)$ upper bound on the number of moves (when a solution exists) for this digraph class.

Answer by Günter Rote for Minimal graphs with a prescribed number of spanning trees

2013-02-17T19:46:25Z

No answer, but a related question: The number $n$ of spanning trees in a graph with $k+1$ vertices is the determinant of a $k\times k$ matrix with integer entries between $-1$ and $k$.

For given $n$, what is the smallest $k=\beta(n)$ such that $n$ is the determinant of such a matrix?

Of course, $\alpha(n)\ge \beta(n)+1$. Variations of this problem might restrict to symmetric, or diagonally dominant matrices, or on the other hand allow entries between $-k$ and $k$.

Are any bounds known about THIS question?

Additions (incorporating the remark by Will Sawin): For example, $$\left| \begin {matrix} 4&7&1&3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&10 \end {matrix} \right| = 4713.$$ In this way, with $k$ as the base instead of 10, one gets all numbers up to $k^k$ (and a little more). The upper bound on the determinant from the Hadamard inequality is $k^{3k/2}$. With the lower bound $-1$ on the entries, this bound can probably be improved, since the row vectors of the matrix cannot be simultaneously "long" and close to orthogonal.

One can work this determinant into the number of directed spanning trees of a multigraph: $$\left| \begin {matrix} 4&-7&-1&-3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&10 \end {matrix} \right| = 4000-713=3287.$$ Let us add a fifth column to make column sums zero: $$ \begin {pmatrix} 4&-7&-1&-3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&10\cr -3& -2&-8&-7 \end {pmatrix} $$ The digits of the determinant are now in the last row. This number 3287 is equal to the number of oriented spanning trees (arborescences) on a directed multigraph $G$ on 5 vertices which are oriented away from the root node 5. The graph $G$ is obtained by taking the negative off-diagonal entries as edge multiplicities. (The arcs going into node 5, which would be the fifth column, are obviously irrelevant.) One can also figure out directly that this is the number of arborescences, by classifying them into those 3000 that use the arc $(5,1)$ and the remaining 287 that don't.

For directed graphs, one can get rid of multiple edges by subdividing them. The new intermediate vertex on an edge must have exactly one incoming arc in every tree, and since the indegree is 1 this arc is fixed, and the number of spanning arborescences is as in the original graph. Moreover, all multiple edges go out either from vertex 1 or from vertex $k+1=5$. Multiple edges emanating from one vertex and going to different vertex can share the intermediate subdivision vertex. Thus, we need in total only $2(k-2)$ extra vertices to eliminate multiple arcs, $k-2$ from vertex 1 and $k-2$ from vertex $k+1$, for a total of $3k-3$. (I did not work out how this argument looks when translated into matrix terms.)

Every integer up to $k^k$ can be realized as the number of spanning arborescences with a fixed root in a digraph on $3k-3$ vertices without multiple arcs.

In other words, $\alpha(n)$ for digraphs is bounded by $O(\log n/\log\log n)$. Much better than what is known for undirected graphs, settling the conjecture at least for directed graphs.

The next remaining open challenge is to investigate $\beta(n)$ for symmetric matrices.

Answer by Günter Rote for Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equalities between Distance Sums or Differences

2013-02-17T21:19:40Z

Here is a sketch of an answer that involves the squared Euclidean distances between the four points $A,B,C,D$ (and only the squared ones, not a mixture between squared and non-squared distances.)

Suppose $D$ is the origin, and consider the vectors $a=DA, b=DB, c=DC$. From $$AB^2 = \langle a-b,a-b \rangle = DA^2 -2\langle a,b\rangle + DB^2,$$ we get $\langle a,b\rangle$ as a linear expression in terms of the squared distances, and similarly for the other mixed inner products. The inner "self"-products like $\langle a,a\rangle=DA^2$ are directly available anyway. Assuming that $a$ and $b$ are linearly independent, we can write $$c=\lambda a + \mu b.\ \ \ \ \ (1)$$ Then $D$ (the origin) is in the convex hull of $A,B,C$ iff $\lambda\le 0$ and $\mu \le 0$. Multiplying (1) by $a$, $b$, and $c$ gives an overdetermined system of three equations $$\langle a,c\rangle = \lambda\langle a,a\rangle+\mu\langle a,b\rangle,$$ etc. from which an expression (actually, three equivalent expressions) for $\lambda$ and $\mu$ can be derived using Cramer's rule, as a quotient of determinants. Hence, the sign of these determinants tells us if $D$ is a vertex of the convex hull or not.

So in the end it boils down to $2\times 2$ determinants whose entries are linear in the squared distances, i.e., degree-2 polynomials in the squared distances. One would have to work out what these expressions are. Who knows, maybe a clever combination of the various redundant expression gives even linear expressions, or expressions that can be factorized into nice linear terms.

Answer by Günter Rote for Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equalities between Distance Sums or Differences

2013-02-17T01:14:06Z

No. (This was an answer to a previous, not entirely clear version of the problem.) Take an equilateral triangle ABC of side length 1, plus the midpoint D of the side AC. By pushing D slightly in or out parallel to the line BC, you can make ABCD nonconvex or convex. BD is the only irrational distance among the 6 distances. By taking the perturbation sufficiently small (say $\pm0.01$), you cannot distinguish from sums and differences whether BD is larger or smaller than in the original (degenerate) position.

Answer by Günter Rote for Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

2013-02-15T20:46:47Z

Here is a polynomial-time algorithm. I assume that the chips are identical, as in Dima's reformulation and in Sokoban. (Another version would be that the chip from Init$_i$ has to go to Final$_i$, for every $i$.)

Find out which chips should go to which target positions:
1. Set up a bipartite graph, with an arc from Init$_i$ to Final$_j$ if Final$_j$ is reachable from Init$_i$ in the graph (ignoring the chips).
2. If some Init$_i$ and some Final$_j$ coincide, it means that that some chip can be regarded as lying already on its target position. We take such pairs of vertices out of the graph.
3. Find a perfect matching. If there is none, abort. The problem has no solution.
4. The matching gives a 1-1 assignment between initial and final positions.
Now we realize these movements one by one. Say, we want to move chip $A$ from Init$_i$ to Final$_j$, which is not occupied. Find any path from Init$_i$ to Final$_j$ in the graph (ignoring the other chips). Try to push the chip along this path. It may happen that some other chip $B$ blocks the path. In this case, move $B$ one step along the path, and then let $A$ take the previous place of $B$. Since the chips are identical, the effect is the same as if $A$ had jumped over $B$. The same trick can "jump" over several adjacent chips that block the path.

Answer by Günter Rote for sparse binary vector

2013-02-15T19:25:59Z

After a Cholesky factorization $R=T'T$, your problem becomes the maximization of the Euclidean norm over the parallelotope formed by the points $Tw$. This problem is discussed in H. L. Bodlaender, P. Gritzmann, V. Klee, J. van Leeuwen: Computational complexity of norm-maximization, Combinatorica 10 (1990), 203-225.
If your matrix is just symmetric, not necessarily p.s.d., then it is essentially the maximum cut problem. For this problem, there are (famous) convex relaxations, using for example semidefinite programming.

Answer by Günter Rote for Is the empty graph a tree?

2013-02-07T14:22:29Z

I checked Reinhard Diestel's textbook on Graph Theory. p.2

A graph of order 0 or 1 is called trivial. Sometimes, e.g. to start an induction, trivial graphs can be useful; at other times they form silly counterexamples and become a nuisance. To avoid cluttering the text with non-triviality conditions, we shall mostly treat the trivial graphs, and particularly the empty graph, with generous disregard.

Only nonempty graphs are defined to be connected. (p.9)

Answer by Günter Rote for An elementary probability question

2013-01-29T19:24:25Z

YES, trivially. Even $E(\|X_0-X_1\|^2)$ is already bounded by 4x the variance. (or even 2x ?)

For $n < d$, this is optimal up to a constant factor. Take the uniform distribution on the $d$ unit vectors. (All (non-centered) moments are 1.) Then the distance is 1 if $X_0$ is distinct from $X_1,\dots,X_n$ and 0 otherwise. The expected distance is thus the probability of the first event: $(1-1/d)^n$. For $n < d$, this is between $1/e$ and $1$.

If the distribution is smooth, then $n\ge d$ makes no sense, the $n$ vectors will span the whole space with probability 1, and the expected distance is 0.

(I had also considered the uniform distribution on the sphere, but after discovering the above example, I was too lazy to calculate the expectation there, although it's just a univariate integral.

Answer by Günter Rote for Classification of finite groups of isometries

2013-01-20T19:55:53Z

Surprisingly, I found explicit lists of discrete subgroups of the orthogonal group O(n) for up to n=8 dimensions on the wikipedia page for point groups, with rather unspecific references, however. Point groups is another name for discrete subgroups of O(n). [UPDATE+CORRECTION: For dimensions n=4 and larger, only the point groups which are generated by reflections (Coxeter groups) are listed. In particularly, subgroups of SO(n) (which include no matrix of determinant $-$1) are missing.]
There is an old sequence of two long papers by Threlfall and Seifert, part I Mathematische Annalen 1931, Volume 104, Issue 1, pp. 1-70, part II 1933, Volume 107, Issue 1, pp. 543-586, where they apparently do the classification of discrete subgroups of SO(4) by associating to each element of SO(4) a pair of rotations from SO(3). (Although my native language is German, I had a hard time reading (through) this, because I am not used to the terminology that was used at that time.) [Addition: These results are mentioned in the book by Conway and Smith on quaternions and octonions; Conway and Smith say that the list is complete, but contains duplicates.]
I have a rather wild conjecture (true up to three dimensions).

Every discrete point group in n dimensions is the symmetry group of an n-dimensional polytope which is the Cartesian product of regular polytopes, or a subgroup thereof.

[UPDATE: Norman Johnson pointed out counterexamples: The symmetries of the root lattices E6, E7, E8 in 6, 7, and 8 dimensions. (I could not yet fully convinced myself that they are indeed counterexamples.) So dimensions 4 and 5 remain open. If I extend my conjecture to include the polytopes which have those E6, E7, or E8 symmetries, in addition to the regular polytopes, in which dimension would the next counterexamples be?]

For example, the symmetries of an $m$-gonal anti-prism in 3-space are contained in the symmetries of the $2m$-sided prism, which is the 1-simplex $\times$ the regular $2m$-gon.

~~Since the regular polytopes are known in all dimensions, this would give an easy way to obtain all finite point groups. (at least in principle).~~

Answer by Günter Rote for Find edge weights that fit given node weights

2013-01-30T18:30:40Z

You can solve it by using maximum network flow: First you duplicate every vertex $i$, creating a twin $i'$, which inherits the same degree $d_{i'}:= d_i$. Each edge $ij$ becomes two edges $i,j'$ and $i',j$. If you solve your problem on this new bipartite graph $G'$, you can recover a solution for $G$ by averaging the two copies of each edge. (and vice versa).

Now, the problem for the bipartite graph $G'$ becomes a network flow problem when you direct the edges from the $i$s to the $i'$s. The $d$s become supplies and demands. (I used this reduction in my thesis.)

Additional remarks.

The max-flow-min-cut theorem will then lead to the following characterization:

A solution exists iff there is no fractional vertex cover with cost less than $\sum d_i$.

A fractional vertex cover assigns a number $x_i$ to each vertex such that $x_i+x_j\ge 1$ for every edge $ij$. It is sufficient to consider values $0,\frac12,1$ for the $x$'s. (This corresponds to the dual linear program to your system of inequalities.) ADDITION: A vertex $i$ costs $x_id_i$, the total cost of a vertex cover is the sum of these quantities.
The set of feasible solutions of your system is related to the perfect $b$-matching polytope, see [A. Schrijver, Combinatorial Optimization, Vol. 1, p. 549]: The $b$s are your $d$s. In this problem, the $b$'s must be integral, and the perfect $b$-matching polytope is the convex hull of the integral solutions of your system of equations.

However, when all $b_i$'s are even, integrality plays no role, and you get directly the convex hull of all real solutions. This is a special section in Schrijver's book; Section 31.5. Theorem 31.5 then (if rephrased appropriately) would lead to the above characterization.

Answer by Günter Rote for Intersection of Cones in Three Space

2013-01-28T22:44:09Z

I am not sure I understand the question, see the remarks of Qfwfq. Here is something related which might nevertheless be interesting for some branches of applied mathematics: an algorithm for parameterizing the intersection of two arbitrary quadrics, given in implicit form with integer coefficients. There are several research reports and even an implementation. You can even input your coefficients on-line on the web and see the result. Maybe there is something easier for the special case of two circular cones.

ADDITION: Apparently they changed the structure of their web pages; The work of these people is based on solid algebraic work, which might be what you are looking for, in their publications; then (what I find remarkable), they often go through and implement their results (see the web page about the work in their lab; I hope the links work now. in particular the work about Constant-complexity geometric problems and algebraic invariants). Those algorithms, while producing "numerical results", do so in a completely reliable way, in contrast to what you conventionally expect from numerical floating-point computation. O.k. you don't want computations; you also don't want the "sum of squares=0" solution, but what DO you want then? I suspect you are interested in the real solutions, so there will be case distinctions, 0, 1, 2 components etc. How should a potential solution to your problem look like? A single polynomial? In which variables? What should the solutions to the polynomial describe?

When you write: "The solution should describe directly what the intersection "looks like" from the point of view of the origin". Does that mean you want the projection of the intersection curve from the origin? It will be some intervals on the circle which is the projection of the whole primary cone. Do you want the endpoint of these intervals?

Another group that you might check out is the work of the EXACUS project in Saarbrücken.

Answer by Günter Rote for Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$

2013-01-29T19:10:51Z

The answer is YES. (I am assuming you mean the angle between two adjacent edges on a common face. (The dihedral angles all go to $\pi$.)) The easy and brief reason is that, in a large random point set, everything (that depends on local conditions) happens almost surely.

Here is a sketch of a proof for your model (1).

Fix $\varepsilon>0$ arbitrarily, and take a (small) triangle $abc$ on the sphere with smallest angle $\varepsilon$.
Construct its circumcircle $K_0$.
Let $K$ be a concentric circle twice as large as $K_0$.
Construct some small neighborhoods $A,B,C$ around $a,b,c$ such that any triangle with vertices taken from these neighborhoods
1. has smallest angle $<2\varepsilon$.
2. has its circumcircle within $K$.
Now we let the number $n$ of points go to infinity. For each $n$:
1. Construct a scaled-down copy of the configuration $A',B',C',K'$ of $A,B,C,K$ (but still on the sphere) such that the expected number of points that falls into $K'$ is 3. (The area of $K'$ is a $3/n$ fraction of the whole sphere.)
2. Now, the probability that exactly 3 points fall into $K'$ is at least some positive probability $p_0$, independend of $n$. ($p_0$ is not so small, the number of points is essentially Poisson-distributed with mean 3.)
3. The probability that
  
  one point each falls into $A'$, $B'$, and $C'$ but no other point falls into $K'$
is at least some (small) constant $p_1>0$ (independent of $n$). The reason is that $A'$, $B'$, $C'$ have some (almost) constant fraction of the area of $K'$.
1. If this event happens, there will be a face angle smaller than $2\varepsilon$.
2. Now, place const$\cdot n$ disjoint copies $A',B',C',K'$ on the sphere. Then these copies behave essentially like independent Bernoulli experiments with success probability $p_1$. As $n\to\infty$, the probability of having at least one "success" approaches 1.

Answer by Günter Rote for Continuity of barycentre in Hausdorff metric

2013-01-29T18:21:14Z

This question has been first discussed in the paper [ABB] below. They show that, in the plane, the barycenter of the boundary has the desired property: It is Lipschitz-continuous with respect to the Hausdorff distance. (However, the Lipschitz constant is larger than 1.)
Other such "reference points" which are Lipschitz-continuous w.r.t. the Hausdorff-distance, or w.r.t. some other metric (like the area of the symmetric difference) have been investigated. The objective is to get a fast heuristic or initial solution for matching two shapes under translation. A good starting point into the literature might be Oliver Klein's Ph.D. thesis "Shape Matching With Reference Points" from 2008.
The best Lipschitz constant (for the Hausdorff distance) is achieved by the so-called Steiner point (or Steiner center). In functional analysis, such "reference points" are known under the name "continuous selectors". It has been proved (by non-constructive methods, however) that the Steiner point has the smallest possible Lipschitz constant w.r.t. the Hausdorff distance.
One can show by an elementary example that a reference point (a mapping from compact convex sets to points that is equvariant under, say, isometries) cannot have Lipschitz-constant 1 in dimension 2 or larger. (Thus the answer to the first, strong, part of the original question is NO, even if you think of other points than the barycenter.)

[ABB] Helmut Alt, Bernd Behrends, Johannes Blömer. Approximate matching of polygonal shapes. Ann. Math. Artif. Intell., Volume 13, Pages 251-266, 1995. The conference version may be easier to access: Proceedings of the seventh annual symposium on computational geometry, pp.186-193, June 10-12, 1991, North Conway, New Hampshire. ACM Press. doi>10.1145/109648.109669.

Comment by Günter Rote

2013-04-28T23:15:12Z

The exponent would not change. For example, take random points in a circular disk. Fit a triangle in the disk. A constant fraction of the n points falls inside the triangle (w.h.p.), and thus you get at least $c′n^{1/3}$ points in convex position; similarly, an ellipse (affine image of a disk) fits into any triangle, showing the other direction of the inequality. Any two convex shapes are related like this (after affine transformation).

Comment by Günter Rote

2013-04-28T22:46:44Z

Yes, it is. I have updated my answer.

Comment by Günter Rote

2013-04-26T21:40:34Z

I wonder how a matrix with positive entries can have trace 0?

Comment by Günter Rote

2013-03-06T18:21:11Z

@Noam. Clarification: I was not puzzled because I did not see that the product has "distinct" exponents, after expanding the product and before collecting terms with the same exponent. But why is this fact needed?

Comment by Günter Rote

2013-03-05T20:42:23Z

Nice! I am puzzled by the remark that the $N$ monomials have distinct exponents. If they were not distinct, just collect terms and let them cancel if they want, and let $m_j$ only refer to the nonzero terms. This would reduce the number of terms of $P(X)$, and the argument goes through (with a reduced number $N$) as long as the polynomial does not become identically zero. But this is ok, as we know that the constant term is nonzero because it has abs. value 1. (And anyway, who is afraid of the Combinatorial Nullstellensatz? It doesn't even need such advanced stuff as "complex numbers;-)

Comment by Günter Rote

2013-03-01T11:27:05Z

There is also the inverse tendency that the German terms tend to be forgotten, now that English has become so prevalent. Many German students will happily use "Konvolution" when they read it in a paper before I teach them to use "Faltung". Similarly, "bottleneck" like in "bottleneck objective function" tends to be sometimes literally translated into "Flaschenhals" instead of "Engpass" (meaning narrow pass, which is (or used to be) the usual term in this situation). A case which I particularly deplore is the thoughtless translation of "line segment" into "Liniensegment" instead of "Strecke".

Comment by Günter Rote

2013-02-28T13:24:52Z

The question did not ask for the existence of a speed originally. Maybe $X(t)$ is concentrated around $f(t)$ for some function $f$. If we assume that $f(t)$ increases unboundedly, is there an example where the random walk is concentrated, but the modified random walk is not concentrated (around a different function $f'(t)$)?

Comment by Günter Rote

2013-02-27T17:04:25Z

Should the assumption hold for all $c$? Is it essential that the walk moves to the right on average (like $(1/3)t$ in your example) our would a movement to the left or a stationary concentration around $0$ be permitted? (In the last cases there would probably be easy counterexamples when some $p_n$ is changed from 0 to $\epsilon$.)

Comment by Günter Rote

2013-02-27T16:32:20Z

@userior, why don't you calculate the value for the square plus center and compare? Then at least we have a conjecture, and we only need to concentrate on one problem.

Comment by Günter Rote

2013-02-25T22:56:24Z

2nd proof: It would be nicer if the small strips were above and to the left of the big square.

Comment by Günter Rote

2013-02-24T19:51:36Z

Anyway, When you specify the steps in this form, another important 3-dimensional class of motions is excluded: screw motions (rotation around an axis with simultaneous translation along that axis). Of course such a motion can be approximated by a sequence of translations and rotations, but the number of steps might be large (not bounded in $n$). I imagine two chains that require a screw motion at one point. It would be analogous to allowing a point in the plane to move only vertically or horizontally. The necessary number of such steps inside a slanted strip can be as large as we like.

Comment by Günter Rote

2013-02-24T19:48:03Z

"rotation about a fixed point" is maybe inappropriate if 3d. It might be rotation about a fixed axis.

Comment by Günter Rote

2013-02-24T19:36:41Z

Please specify your definition of "stationary distribution", if what you mean does not coincide with the definition as an eigenvector.

Comment by Günter Rote

2013-02-24T19:25:58Z

@partial results: A natural conjecture is that the second quantity is minimized when the 5 points form a regular pentagon. Have you checked this? What is the value for a regular pentagon? Is the first quantity perhaps minimized for a square plus center? What is the value for this configuration? What is the best value that you know for each of these quantities?

Comment by Günter Rote

2013-02-24T19:18:16Z

1. perimeter/area = 2/inradius; so there is an equivalent formulation with "max min inradius($v_iv_jv_k$)". 2. Both quantities are constants. Wouldn't you rather know the value of those constants?