User dima pasechnik - MathOverflow

Answer by Dima Pasechnik for Usage of complex moments in complex plane

2013-05-13T16:19:23Z

For instance, in the setting of the logarithmic potential theory, what you "measure" are complex moments, aka harmonic moments. You can find more references e.g. here.

Answer by Dima Pasechnik for automorphisms of graphs and finite permutation groups

2013-03-26T04:31:21Z

IMHO, the main message in Wielandt (you might want to supplement it by a more recent book, such as Peter Cameron's "Permutation groups") is that one can consider the adjacency matrix $A$ of your graph $\Gamma$ as an element of the centralizer ring {$X\in M_{|V\Gamma|}\mid Xg=gX$ for any $g\in G$} of the permutation representation of a subgroup $G$ of the automorphism group of $\Gamma$.

This idea has been used a lot since Wielandt's work, e.g. D.Higman and others axiomatised this point of view (one can throw away the group and look at rings which "look like" centralizer rings of permutation groups), resulting in emergence of a whole branch of algebraic combinatorics, the theory of coherent configurations and association schemes. It also had quite an influence on the theory of graph spectra.

The papers on this and other related ideas are too numerous. I'll mention (with apologies to the authors of relevant books I fail to mention) few books: apart from Peter Cameron's "Permutation groups", there are indeed books by Chris Godsil, the book "Algebraic combinatorics I. Association schemes" by E.Bannai and T.Ito, the book "Distance-regular graphs" by A.Brouwer, A.Cohen, and A.Neumaier.

A more graph-theoretic/CS point of view comes from work of L.Babai, see e.g. this survey.

The relations to spectra of graphs can be found in a recent book by A.Brouwer and W.Haemers.

Answer by Dima Pasechnik for Extremely messy proofs

2013-03-23T16:56:19Z

Invariant theory before Hilbert was quite messy and ad hoc, e.g. classical pre-Hilbert proofs of finite generation of various rings of invariants are quite unpleasant and long.

Answer by Dima Pasechnik for What is the dual of an semidefinitely representable (SDR) cone?

2013-03-19T16:31:23Z

It's a long comment, not an answer.

Already the well-known SDR cone $\Sigma_{n,d}$ of sums of squares of homogeneous $n$-variate degreed $d$ polynomials has an interesting dual (also SDR), described e.g. in B.Reznick's AMS Memoir, Theorem 3.16. At least this gives interesting examples to play with.

Answer by Dima Pasechnik for Rigorous numerics for maxima and minima (one variable)

2013-03-19T01:30:16Z

You can convert your problem into a multivariate one, with polynomial equality constraints, by introducing new variables for each square root and division. Thus you end up with the problem of minimizing a polynomial function on a semialgebraic set (add various necessary conditions for the optimum, too, e.g. what you get from $f'(x)=0$; this won't need more variables to be introduced), which you indeed can do rigorously, i.e. you could do even more: find your minimum and maximum as real algebraic numbers, by quantifier elimination. If you're lucky then necessary conditions for the optimum give you a zero-dimensional ideal to deal with, with zeros being (potential) optima.

Well, this is in theory; in practice, you might run into problems, and instead opt for using a sum of squares-based approach of polynomial optimization, which turns into solving a sequence of semidefinite programming problems of increasing size, with optimal values approximating the real optimum with increasing precision.

Answer by Dima Pasechnik for Does the cubic planar graph with 6 3-faces and 6 7-faces have a name?

2013-03-09T07:45:45Z

Sage has search facilities for graphs with specified properties, and "knows" a large number of "named" graphs. As you work within a system running Python, you can do much more much easier, compared to what you get just by searching online databases using a www interface. The manual of the corresponding part is here.

Answer by Dima Pasechnik for Permutation character of the symmetric group on subsets of certain size

2013-03-06T12:59:26Z

A classical construction of the Specht modules of $S_n$ says that $\chi_{(n-k,k)}$ is present in the character $\pi_k$ of the action $S_n$ on $V_k$, with multiplicity 1. Indeed $M^\lambda:=V_k$ is the permutation module arising along the way of constructing the Specht module $S^\lambda$ for the partition $\lambda=(n-k,k)$.

Moreover, it is easy to see that the centralizer of the action of $S_n$ on $V_k$ in the full matrix algebra of $\binom{n}{k}\times\binom{n}{k}$ is commutative, and has dimension $k+1$ (The centralizer is spanned as an algebra by the 0-1 matrices corresponding to the orbits of $S_n$ on the ordered pairs of $k$-subsets - this is a general fact about permutation representations of finite groups; here these matrices are symmetric, and thus it's a commutative algebra). Thus $\pi_k$ is a sum of $k+1$ irreducible characters, each of them with multiplicity 1. At this moment we know two of them, namely $\chi_{(n-k,k)}$ and $\chi_{(n)}$ (the latter is there, as it's the trivial character, present in every permutation character).

There is a description (see e.g. Volume 2 of the Richard Stanley's book) of irreducible characters arising in $M^\lambda$, for any $\lambda$. Namely, $$M^\lambda=S^\lambda\oplus \oplus_{\mu\triangleright\lambda} K_{\lambda\mu} S^\mu,$$ where $\triangleright$ stands for the dominance partial ordering on the partitions of $n$, and the $K_{\lambda\mu}$'s are famous Kostka numbers (in our case they are all 0 or 1). Using this, one can easily complete the proof of (1).

PS. In Stanley's book, this question is Example 7.18.8 on p.355, Volume 2.

Answer by Dima Pasechnik for What kind is this optimization problem

2013-03-04T19:01:19Z

Let us simplify your constraints. Namely, set $x=r\sin\phi$, $y=r\cos\phi$. Then it simplifies to $u\sin^2\phi + v\cos^2\phi \geq \sin\phi \cos\phi$, for all $0\leq \phi\leq 2\pi.$ Then divide both sides by $\cos^2\phi$, and set $z:=\frac{\sin\phi}{\cos\phi}$. You'll get quadratic inequality $f(z):=uz^2-z+v\geq 0$, for all $z$.

So we have to describe the set of $u$ and $v$ such that the latter always holds. The discriminant of $f(z)$ is $1-4uv$, and so one has $1-4uv\leq 0$, otherwise $f(z)$ has two distinct real roots, and $f$ can't be nonnegative everywhere. Note that also we see, by setting $x$ or $y$ to 0, that $u\geq 0$ and $v\geq 0$.

So we simplified your constraints, getting rid of $x$ and $y$, to the following form: $uv\geq 1/4$, $u\geq 0$, $v\geq 0$. The rest looks like a standard exercise in "elementary" nonlinear optimization.

as suggested by the comment by Noah below, an easier way is to directly specify the constraint is to write down $$ux^2+vy^2-xy=(x,y)\begin{pmatrix}u &-1/2\\-1/2 & v\end{pmatrix}\begin{pmatrix} x\\y\end{pmatrix}$$ and note that it is nonnegative everywhere iff $\begin{pmatrix}u &-1/2\\-1/2 & v\end{pmatrix}$ is positive semidefinite.

Answer by Dima Pasechnik for Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

2013-02-15T13:24:19Z

Edit: Sokoban is a harder problem than this one!

It is not hard to see that Sokoban is a particular case of this problem (the graphs arising in Sokoban are undirected and planar, of degree at most 4). Sokoban is known to be NP-complete. (thanks to my wife, who is a complexity theorist by training, and used to play Sokoban :-)).

Thus, in general, assuming that P is not equal to NP, any procedure to solve this problem will run in time exponential in $m$.

On the other hand, for any fixed $m$, this problem is solvable by repeated application of the shortest path algorithm, which need to iterate over all the possible assignments of chips in the initial configuration to the (ordered) elements of $F$ (i.e. the final nodes). If for no such an assignment the process of moving the chips completes, there is no solution. On the other hand, the procedure runs in polynomial time for $m$ fixed.

Answer by Dima Pasechnik for Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

2013-02-15T11:56:57Z

Not an answer, but an improved version of the question:

Consider a directed graph $G=(V,A)$, and a subset $F\subset V$ of final nodes. Let $m=|F|$ and consider the following game: one is given a configuration of $m$ chips on $V$, with not more than one chip per node (or, more formally, an injective function $c:[1,2,\dots, m]\to V$), and the following moves are allowed:

choose an arc $vu\in A$ with a chip on $v$ no chip on $u$;
move the chip from $v$ onto $u$.

(i.e., with the formalism of functions, we modify $c$ so that $u$ enters $c^{-1}(V)$, and $v$ leaves $c^{-1}(V)$.)

The goal: cover $F$ with chips. (i.e., achieve $c([1,2,\dots, m])=F$).

Question: what is the complexity of deciding whether the goal can be reached.

Answer by Dima Pasechnik for complexity of finding optimal matchings of given fixed size

2013-02-10T15:14:57Z

Yes, at least for bipartite graphs. Namely, the Hungarian algorithm builds a maximum weight matching incrementally, and at stage $j$ it has a maximum weight matching with $j$ edges. Cf. e.g. my old notes, or Sect. 3.5 of A.Schrijver's lecture notes.

IIRC, it is the case for the general graphs too, but you should check this in a monograph on the topic, e.g. Sect. 26 of A.Schrijver's 3-volume work.

Answer by Dima Pasechnik for Largest permutation group without 2-cycles or 3-cycles

2013-01-10T03:21:59Z

For small $n$ your construction is not optimal (e.g. for $n=6$ there is a group of size 120, isomorphic to $S_5$; $M_{12}$) is an example for $n=12$, the biggest exceptional $n$, it seems).

But for sufficiently large $n$, your construction is almost optimal; you can still add an extra 2 to the order of your group. Namely, add the permutation $(1,n/2+1)(2,n/2+2)\dots (n/2,n)$. A way to prove that this becomes optimal (for sufficiently large $n$) might go as follows:

prove that this is the best possible with intransitive groups
same for imprimitive groups
for primitive groups, invoke O'Nan-Scott theorem (eventually, the classification of finite simple groups).

Perhaps there is a better way to deal with the last step, I don't know.

Answer by Dima Pasechnik for A sum related to the Johnson association scheme

2013-01-09T12:24:29Z

This is a hypergeometric function times a binomial coefficient, isn't it? To see exactly which one, one can do the usual procedure described in books, e.g. in A=B.

Then, perhaps, hypergeometric identities can be applied, but at least having your sum encoded like this might help.

Answer by Dima Pasechnik for On the Positive Definiteness of a Linear Combination of Matrices

2013-01-06T17:30:26Z

A straightforward reformulation is in terms of polynomial inequalities is by taking $n$ consecutive chief submatrices $M_{KK}(\lambda)$ for $K=(1,\dots,k)$, $1\leq k\leq n$ of the matrix $M(\lambda)=\sum_{j=1}^m \lambda_j A_j\in \mathbb{R}[\lambda_1,\dots,\lambda_m]^{n\times n}$. Then $P$ contains a positive definite matrix if and only if the basic open semialgebraic set

{$y\in \mathbb{R}^m\mid \det M_{KK}(y)>0, \ K=(1,\dots,k), 1\leq k\leq n$} is nonempty.

At least these kinds of conditions were used in papers by L.Khachiyan and L.Porkolab, such as "On the complexity of semidefinite programs", J. Global Optim. 10 (1997). E.g. when $m$ is fixed, one gets a strong polynomial-time algorithm for checking non-emptiness of $P$.

Answer by Dima Pasechnik for automorphism group of orbital graphs

2013-01-01T17:01:15Z

The property of $G$ you are looking at is called 2-closure, i.e., you ask for a classification of 2-closed permutation groups. See the paper by Liebeck, Praeger, Saxl, On the 2-closures of finite permutation groups. J. London Math. Soc. (2) 37 (1988), no. 2, 241–252, where this question is investigated for a particular class of primitive permutation groups.

More precisely, this is not 100% equivalent to your question (it would be, if you allowed graphs have coloured arcs), as there exist 2-closed permutation groups $G$ such that for each orbital the automorphism group of the underlying (di)graph is strictly bigger than $G$.

In general such a classification is not known, and the problem is hopelessly hard, I think.

Answer by Dima Pasechnik for Graph of $S_n$ with respect to transposition

2012-12-30T05:23:02Z

1) One can say something about the $k$-neighbourhoods of a vertex $v$ (i.e. sets of vertices at distance $k$ from $v$). For $v=()$, the identity element of $S_n$, each $k$-neighbourhood is a union of conjugacy classes of $S_n$.

E.g. for $k=1$ you get $n \choose 2$ vertices, corresponding to involutions of type $2^1$, a.k.a. transpositions $(ab)$, and there are no edges between them. That is, there are no triangles in your graph. By the way this immediately tells you that $K_{888}$ for $G_4$ is very far off.

For $k=2$ you get two types of vertices, namely, the ones corresponding to involutions of type $2^2$, i.e. $(ab)(cd)$, and the ones corresponding to $3$-cycles $(abc)$. This will tell you that for any two vertices at distance 2 there is unique 4-cycle which contains them. Indeed, you can get $(ab)(cd)$ using two transpositions either as $(ab)\cdot (cd)$ or as $(cd)\cdot (ab)$, and you can get $(abc)$ either as $(ac)\cdot (bc)$ or as $(bc)\cdot (ab)$.

2) Another interesting and sometimes useful fact is that the eigenvalues of the adjacency matrix $A$ of $G_n$ can be computed from the values of the irreducible characters of $S_n$; namely, $A$ can be viewed as an element $\sum\limits_{\pi \text{ a transposition}}\pi$ in the center of the group algebra $\mathbb{C}[S_n]$, and the center is generated by such conjugacy class sums; this allows you to simultaneously diagnonalise them, etc.

Answer by Dima Pasechnik for Extreme rays in the cone of (semi)metrics

2012-12-28T13:14:37Z

There has been quite a bit of work done since 1980 on this. Did you check the book by M. Deza and M. Laurent "Geometry of cuts and metrics", Springer 1997 ?

There was a quite a bit of computer search done to go beyond $n=5$ in Avis' paper. E.g. I think here you can find results for $n=7$. There are more links on a page maintained by A.Deza.

I admit I don't recall asymptotic results, although it has been a while.

Answer by Dima Pasechnik for Confused about orbits

2012-12-24T17:42:13Z

The automorphism group of this graph is $S_{c-1}$. Note that the vertex 1 in your clique cannot be moved anywhere (look at the degrees). On the other hand, a permutation of the remaining vertices in {2,...,c} induces a permutation on these $s$ vertices $P$. The 14 orbitals (aka orbits on $V\times V$) are as follows:

{(1,1)}
{(x,x) | x in {2..c}}
{(p,p) | p in P}
{(x,y) | x,y in {2..c}, x not equal to y}
{(p,q) | p,q in P, the corresponding pairs of elements of {2..c} do not intersect}
{(p,q) | p,q in P, the corresponding pairs of elements of {2..c} intersect in one element}
{(1,x) | x in {2..c}}
{(x,1) | x in {2..c}}
{(1,p) | p in P}
{(p,1) | p in P}
{(x,p) | x in {2..c}, p in P, x in p}
{(p,x) | x in {2..c}, p in P, x in p}
{(x,p) | x in {2..c}, p in P, x not in p}
{(p,x) | x in {2..c}, p in P, x not in p}

Answer by Dima Pasechnik for Strongly regular cayley graphs

2012-12-21T10:51:34Z

no, this is certainly not true. IIRC already on 25 vertices there is a family of 15 non-isomorphic s.r.g.'s with the same parameters, some of them Cayley graphs, some not: see http://www.win.tue.nl/~aeb/graphs/Paulus.html.

Answer by Dima Pasechnik for What graph parameters are determined by parameters for strongly regular graph

2012-12-13T09:41:41Z

It's a classic result that a graph parameter called Lovasz theta-function $\theta(\Gamma)$ of a strongly regular graph $\Gamma$ is determined by its parameters. And the significance of $\theta(\Gamma)$ is that it is "sandwiched" between the clique number and the chromatic number.

In more detail, the parameters of the s.r.g. $\Gamma$ determine a 3-dimensional commutative algebra of symmetric matrices (the adjacency matrix $A(\Gamma)$ of $\Gamma$, the adjacency matrix of its complement, and the identity matrix span this algebra). Anything that can be expressed in terms of this algebra, which is specified by the eigenvalues of $A(\Gamma)$, is a parameter you are asking about, and $\theta(\Gamma)$ is one of them. Another one is the number of spanning trees, as by Matrix Tree Theorem it is determined by the eigenvalues.

Answer by Dima Pasechnik for Poles from the Continued Fraction Expansion of the Tangent Function?

2012-12-15T03:49:33Z

Just in case, there is a connection with Hankel determinants. Dividing both sides by $z^2$, one has $$\sum_k\mu_k z^k= \frac{\tan z}{z} = \frac{1}{1 - \cfrac{z^2}{3- \cfrac{z^2}{5 - \ldots}}} $$ Then one defines for all $m,n\geq 0$ the Hankel determinant $H^n_m$ is $$H^n_m=\det (\mu_{i+j})_{n\leq i,j\leq n+m-1}.$$ Let $z_1, z_2,\dots$ be the poles of $\frac{\tan z}{z}$, ordered by increase of the modulus. It's classically known (see Chapter 7 of Henrici's "Applied and computational complex analysis", Vol.1) that $$ \lim_{n\to\infty} \frac{H_m^{n+1}}{H_m^n}=\prod_{j=1}^m z_j^{-1},$$ whenever $|z_m|<|z_{m+1}|$. While I don't know $H_m^n$ for all $n$, for $n=0$ it can be read off directly from the continued fraction, using Theorem 11 of Krattenthaler's "Advanced determinantal calculus". In fact, it gives $H_m^0=1$. Perhaps $H_m^n$ are also directly related to the coefficients of the continued fraction.

Answer by Dima Pasechnik for K Paths between two nodes in a network

2012-12-14T13:44:28Z

my understanding that this basically can be done by linear programming, as a variation of the classical max-flow min-cut approach. See this paper in J. Graph Theory 67(2011) 34-37.

Needless to say, in the non-directed case one can replace each edge by a pair of arcs going in opposite directions.

Answer by Dima Pasechnik for are there pairs of combinatorial graphs that are both isospectral and have the same matroid?

2012-12-13T09:18:26Z

There exist co-spectral trees. As there are no cycles to preserve, they fit the bill.

As far as 2-connected graphs are concerned, I would try finding a 2-connected graph $\Gamma$ which can be obtained from disjoint graphs $\Gamma_1$ and $\Gamma_2$ by identifying a pair of vertices $u_1,v_1\in V\Gamma_1$ with $u_2,v_2\in V\Gamma_2$, so that the Whitney twist, i.e. identification of $u_1,v_1$ with $v_2,u_2$, gives a non-isomorphic graph, but preserves the characteristic polynomial of the Laplacian matrix of $\Gamma$.

Answer by Dima Pasechnik for Exact arithmetic for real algebraic numbers

2012-12-11T13:04:52Z

In the reference you posted there is a link to an online version of the monograph by S.Basu, M.-F.Roy, and R.Pollack, where algorithms like this are described (cf. Sect. 10.4, Algorithm 10.15).

The technique there is very general, and applies to non-Archimedean real closed fields, e.g. to fields of Puseaux series w.r.t. to an infinitesimal. There you don't have anything like "numeric evaluation".

Having said this, I wonder whether Thom encoding is really better for the range of problems like "straight" arbitrary precision computations with algebraic reals. For the latter, isolating roots by rational numbers works as well, and is faster, in theory, according to the reference.

Thom encodings really shine when one has a parametric (e.g. multivariate), or/and a non-Archimedean, setting.

Computation with isolating intervals is implemented e.g. in Sage.

sage: s=sqrt(AA(2))
sage: s.numerical_approx(prec=1000)
1.4142135623730950488016887242096980785696718753769480731766797379907324784...
sage: s>AA(0)
True
sage: t=s-sqrt(AA(3))
sage: t.minpoly()
x^4 - 10*x^2 + 1
sage: t.sign()
-1

Answer by Dima Pasechnik for Is the tensor product of polyhedra a polyhedron?

2012-12-07T11:45:33Z

An obvious route to a proof of 6 would be showing that conv($P\otimes Q$) decomposes as $$\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}((P_p+P_c)\otimes Q_c+P_c\otimes (Q_p+Q_c))+\mathrm{conv}(P\otimes Q_\ell+P_\ell\otimes Q)\qquad (*)$$ where $P=P_p+P_c+P_\ell$, for $P_p$ a polytope, $P_c$ a pointed cone, and $P_\ell$ a linear subspace, and $Q=Q_p+Q_c+Q_\ell$ a similar decomposition for $Q$. You have mentioned that $\mathrm{conv}(P_p\otimes Q_p)$ is a polytope, and I think a proof of this should be easily adaptable to showing that the second $\mathrm{conv}(...)$ is a polyhedral cone. And the third $\mathrm{conv}(...)$ is linear subspace. Hence $(*)$ would imply that $\mathrm{conv}(P\otimes Q)$ is a polyhedron.

The hard part seems to be showing $(*)$. Any closed convex set $C$ in $\mathbb{R}^m$ has a decomposition into the sum of a convex set $C'$ which does not contain straight lines, and a subspace $C_\ell$, with $C'$ contained in the orthogonal complement of $C_\ell$, so this boils down to identifying $C'$ with the sum of the first two conv(...), and $C_\ell$ with the third conv(...).

Answer by Dima Pasechnik for SAT and Arithmetic Geometry

2012-12-06T17:23:37Z

David mentioned in his answer results where Groebner bases are not used. However, Groebner bases for polynomial systems aren't the best available tools theoretically, either. E.g. the best theoretical results for complexity of solving 0-dimensional systems follow a route of symbolically deforming the system into one for which the Groebner basis is trivial to find, and then using Stickelberger Lemma to find roots of the deformed system, and finally taking the limit. Details of this are described e.g. in this book.

Groebner bases (in characteristic 0) are also usually beaten by the machinery of semidefinite programming relaxations. Perhaps not coincidentally, a lot of recent work in computational complexity (in particular, approximation algorithms) uses semidefinite programming relaxations, too.

There is also a line of research where the complexity is investigated w.r.t. arithmetic operations in $\mathbb{C}$ (or $\mathbb{R}$) having unit cost.

Answer by Dima Pasechnik for How to work with infinite random graph(s) ?

2012-12-03T14:50:14Z

Do you mean countably infinite random graphs with probability of any two vertices being joined a constant? Peter Cameron wrote about these graphs in his books, and in his blog (there are more posts on the topic there).

bounding the sum of the entries of the inverse of a 0-1 matrix away from 1?

2012-11-30T13:01:45Z

Let $A\in\mathbb{R}^{n\times n}$ be an invertible 0-1 matrix. Is it possible that the sum $a:=\sum_{i,j}(A^{-1})_{ij}$ of entries of $A^{-1}$ is not equal to 1, but exponentially close (w.r.t. $n$) to 1?

More precisely, the conjecture is that if $a\geq 1$ then either $a=1$ or $|a|\geq 1+p(n)/q(n)$, for $p$ and $q$ fixed polynomials (some other not too fast growing functions might do, too).

Remark. The condition $a\geq 1$ is not redundant, as there exist matrices $A$ with $a<1$, e.g. $$A=\left(\begin{array}{rrrr} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right), \quad A^{-1}=\left(\begin{array}{rrrr} -1 & -1 & 0 & 1 \\ -1 & -1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array}\right), \quad a=\sum_{i,j} (A^{-1})_{ij}=0. $$

An (admittedly very shaky) evidence for this is that it is true if the row sums $r_i$ of $A$ are all equal to each other. Indeed, let $\overline 1$ denote the all-1 vector. Then $a=\sum_{i=1}^n x_i$ for $x$ satisfying $Ax=\overline 1$, and $$ \overline{1}^\top Ax=\sum_i r_i x_i=\overline{1}^\top \overline{1}=n,\quad \text{implying }\quad a\geq \frac{n}{n-1} $$

lines through A_n reflection arrangement and permutations

2012-11-24T06:59:46Z

(updated; apologies for way too much room left for interpretation in the original post)

Let $\mathcal{A} =A_{n-1}$ be the $A_{n-1}$ arrangement in $\mathbb{R}^{n}$, i.e. the set of hyperplanes $H_{ij}$ specified by equations $x_i=x_j$, for $1\leq i\leq j\leq n$. It is well-known that the connected components $c$ of the complement of the intersection of $\mathcal{A}$ with the affine hyperplane $H$={$x\mid \sum_i x_i=1$} (let me call them cells) are in 1-to-1 correspondence with permutations $\sigma(c)\in S_{n}$, so that crossing the hyperplane $H_{ij}$ corresponds to multiplication by the transposition $(i,j)$. More precisely, $\sigma(c)$ records the order of (Euclidean) distances $d(x,e_k)$ at which the standard basis vectors $e_k$ are from every $x\in c$. E.g. for $\sigma(c)=()=12 \dots n$, the identity permutation, one has $d(x,e_1)$<$d(x,e_2)$<...<$d(x,e_n)$, and the arrangement hyperplanes on the boundary of this $c$ are $H_{k,k+1}$ for $k=1,\dots ,n -1$.

Let $\ell$ be a general position line in $H$. Then $\ell$ intersects $\binom{n}{2}+1$ cells. Two of these intersections are unbounded; let us denote the corresponding cells $c_0$ and $c_t$, respectively. As we follow $\ell$ from $c_0$ to $c_t$, from one cell to the next, the corresponding permutation $\sigma(c) = i_1 i_2...$ $i_n$ changes from $\sigma(c_0)$ to $\sigma(c_t)$; namely, it gets multiplied by $(i_k,i_{k+1})$ whenever we cross $H_{i_k,i_{k+1}}$. One can also view this as flipping the adjacent entries, i.e. applying the transposition $(k,k+1)$ to the sequence $\sigma(c)$.

Assume that $\sigma(c_0)$ is the identity permutation. Then $\ell$ specifies a sequence of flips $(k,k+1)$ that need to be applied to obtain $\sigma(c_t)=n, n-1, n-2, \ldots 1$. E.g. for $n=3$ there are two such sequences:

(12), (23), (12)
(23), (12), (23)

Question. Are all the sequences of $\binom{n}{2}$ flips leading from $1,2, \dots, n$ to $n, n-1, n-2, \ldots 1$ realized by general position lines in $H$?

Answer by Dima Pasechnik for A certain type of Quadratic Constrained Quadratic Programming Problem (QCQP)

2012-11-20T16:21:10Z

Quadratic optimization subject to fixed number of quadratic constraints is "easy", even without any convexity assumptions. The algorithms are polynomial-time, but in practice quite hard to implement efficiently. See e.g. this.

The complex case can obviously be reduced to the real one.

Comment by Dima Pasechnik

2013-04-22T13:30:59Z

algebraic combinatorics is a wide subject (Stanley naturally, only treats problems from "his" area) and what really is "biggest" is a very subjective question.

Comment by Dima Pasechnik

2013-04-04T13:17:36Z

1. The list contains a number of highly questionable entries...

Comment by Dima Pasechnik

2013-04-03T16:43:54Z

does $AB=BA$ hold, by any chance?

Comment by Dima Pasechnik

2013-04-01T13:17:12Z

What exactly do you mean by "any algorithm"? IMHO any procedure performing a sequence of arithmetic operations can be expressed by the tensor formalism, but beyond that one cannot say anything.

Comment by Dima Pasechnik

2013-03-31T06:53:54Z

It seems that he's interested in postdoc in Europe, and not many places in Europe use mathjobs. In fact, the postdoc market in Europe is quite different from the one in USA, as there are lots of grant-funded postdocs, tied up to particular topics, and relatively few equivalents to USA instructorships.

Comment by Dima Pasechnik

2013-03-27T14:14:35Z

I wonder if anyone looked at the non-convex case.

Comment by Dima Pasechnik

2013-03-26T11:49:09Z

regarding dessin d'enfant, I liked this book by S.Lando and A.Zvonkin: springer.com/mathematics/geometry/book/… Other than that, I can't help noticing that our answers have virtually empty intersection. :–)

Comment by Dima Pasechnik

2013-03-25T17:06:59Z

I guess it should be 3-connected, and this is the only condition. (But I might be off by a lot :–))

Comment by Dima Pasechnik

2013-03-25T12:07:18Z

For the graph in question, computing $\theta$ and $\theta'$ reduces to linear programming, as it comes from a commutative association scheme.

Comment by Dima Pasechnik

2013-03-24T16:06:36Z

There is an example with the cyclic group of order 5 in B.Sturmfels' "Algorithms in invariant theory", Sect. 2.7. The latter section has a general treatment of finite abelian groups, too. It actually looks as if the number of generators of the ring grows quite fast as n increases, e.g. in the case of n=5 you need 11 generators. Counting/finding generators amounts to dealing with certain integer points in a lattice... B.Sturmfels' "Algorithms in invariant theory" (2nd edition) ISBN 978-3-211-77416-8 Springer 2008, Wien New-York

Comment by Dima Pasechnik

2013-03-19T16:20:23Z

it might not come to quantifier elimination. Generically, $f'(x)=0$ together with the equations for extra variables needed for getting rid of square roots and the denominator will give you a 0-dimensional ideal. Then you're almost done...

Comment by Dima Pasechnik

2013-03-17T13:26:49Z

(1) as an SDP can have a non-0 duality gap, the primal and the dual problems are not equivalent. They are really different and hard to compare, IMHO.

Comment by Dima Pasechnik

2013-03-17T13:22:21Z

(2) - but note that it will remain an approximation, with arbitrary precision, just by nature of the ellipsoid method, and the fact that, unlike in LP, there are no rational vertex solutions, in general. If you want an exact (algebraic numbers!) solution, then the only known algorithms would be exponential-time w.r.t. the dimension or w.r.t. the number of constraints.

Comment by Dima Pasechnik

2013-03-17T13:18:37Z

Tim: (2) in short, the ellipsoid method seems to me the only one for which the complexity is known to be polynomial-time in the classical model of computation, assuming that the diameter of a Euclidean ball containing the feasible set is a part of the input. And the latter might be doubly exponential in the rest of the problem size, as examples of Khachiyan and Porkolab show. In some cases this diameter is small, and so it's not an issue, e.g. this is so for the MAXCUT SDP relaxation by Goemans and Williamson.

Comment by Dima Pasechnik

2013-03-15T17:21:24Z

convert to an integral, note that erf is an integral too, change the order of integration...