User dima pasechnik - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T17:40:25Z http://mathoverflow.net/feeds/user/11100 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130481/usage-of-complex-moments-in-complex-plane/130502#130502 Answer by Dima Pasechnik for Usage of complex moments in complex plane Dima Pasechnik 2013-05-13T16:19:23Z 2013-05-13T16:19:23Z <p>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. <a href="http://arxiv.org/abs/1209.4014" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/125581/automorphisms-of-graphs-and-finite-permutation-groups/125595#125595 Answer by Dima Pasechnik for automorphisms of graphs and finite permutation groups Dima Pasechnik 2013-03-26T04:31:21Z 2013-03-26T04:31:21Z <p>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$. </p> <p>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.</p> <p>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 <a href="http://www.maths.qmul.ac.uk/~pjc/permgps/pgbook.html" rel="nofollow">Peter Cameron's "Permutation groups"</a>, there are indeed <a href="http://quoll.uwaterloo.ca/mine/Books/index.html" rel="nofollow">books by Chris Godsil</a>, the book <a href="http://trove.nla.gov.au/work/21737703?selectedversion=NBD2976477" rel="nofollow">"Algebraic combinatorics I. Association schemes" by E.Bannai and T.Ito</a>, the book <a href="http://www.ams.org/journals/bull/1991-24-02/S0273-0979-1991-16054-4/S0273-0979-1991-16054-4.pdf" rel="nofollow">"Distance-regular graphs" by A.Brouwer, A.Cohen, and A.Neumaier</a>.</p> <p>A more graph-theoretic/CS point of view comes from work of L.Babai, see e.g. this <a href="http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf" rel="nofollow">survey</a>. </p> <p>The relations to spectra of graphs can be found in a recent <a href="http://www.springer.com/mathematics/algebra/book/978-1-4614-1938-9" rel="nofollow">book</a> by A.Brouwer and W.Haemers.</p> http://mathoverflow.net/questions/43820/extremely-messy-proofs/125387#125387 Answer by Dima Pasechnik for Extremely messy proofs Dima Pasechnik 2013-03-23T16:56:19Z 2013-03-23T16:56:19Z <p>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.</p> http://mathoverflow.net/questions/124971/what-is-the-dual-of-an-semidefinitely-representable-sdr-cone/124982#124982 Answer by Dima Pasechnik for What is the dual of an semidefinitely representable (SDR) cone? Dima Pasechnik 2013-03-19T16:31:23Z 2013-03-19T16:31:23Z <p>It's a long comment, not an answer. </p> <p>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.</p> http://mathoverflow.net/questions/124894/rigorous-numerics-for-maxima-and-minima-one-variable/124914#124914 Answer by Dima Pasechnik for Rigorous numerics for maxima and minima (one variable) Dima Pasechnik 2013-03-19T01:30:16Z 2013-03-19T01:30:16Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/123990/does-the-cubic-planar-graph-with-6-3-faces-and-6-7-faces-have-a-name/124053#124053 Answer by Dima Pasechnik for Does the cubic planar graph with 6 3-faces and 6 7-faces have a name? Dima Pasechnik 2013-03-09T07:45:45Z 2013-03-09T07:45:45Z <p><a href="http://sagemath.org/" rel="nofollow">Sage</a> 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 <a href="http://www.sagemath.org/doc/reference/graphs.html" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/123721/permutation-character-of-the-symmetric-group-on-subsets-of-certain-size/123754#123754 Answer by Dima Pasechnik for Permutation character of the symmetric group on subsets of certain size Dima Pasechnik 2013-03-06T12:59:26Z 2013-03-06T15:21:50Z <p>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)$. </p> <p>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).</p> <p>There is a description (see e.g. Volume 2 of the Richard Stanley's <a href="http://www-math.mit.edu/~rstan/ec/" rel="nofollow">book</a>) 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 <i>Kostka numbers</i> (in our case they are all 0 or 1). Using this, one can easily complete the proof of (1).</p> <hr> <p>PS. In <a href="http://www-math.mit.edu/~rstan/ec/" rel="nofollow">Stanley's book</a>, this question is Example 7.18.8 on p.355, Volume 2. </p> http://mathoverflow.net/questions/123543/what-kind-is-this-optimization-problem/123560#123560 Answer by Dima Pasechnik for What kind is this optimization problem Dima Pasechnik 2013-03-04T19:01:19Z 2013-03-05T01:19:22Z <p>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$. </p> <p>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$.</p> <p>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. </p> <hr> <p>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 &amp;-1/2\&bsol;-1/2 &amp; v\end{pmatrix}\begin{pmatrix} x\&bsol;y\end{pmatrix}$$ and note that it is nonnegative everywhere iff $\begin{pmatrix}u &amp;-1/2\&bsol;-1/2 &amp; v\end{pmatrix}$ is positive semidefinite.</p> http://mathoverflow.net/questions/121871/algorithm-to-solve-sokoban-like-game-on-graphs-move-chips-from-one-set-of-verti/121898#121898 Answer by Dima Pasechnik for Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another Dima Pasechnik 2013-02-15T13:24:19Z 2013-02-16T09:44:24Z <p><strong>Edit</strong>: Sokoban is a <em>harder</em> problem than this one!</p> <p>It is not hard to see that <a href="http://en.wikipedia.org/wiki/Sokoban" rel="nofollow">Sokoban</a> is a particular case of this problem (the graphs arising in Sokoban are undirected and planar, of degree at most 4). Sokoban <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.585" rel="nofollow">is known to be NP-complete</a>. (thanks to my wife, who is a complexity theorist by training, and used to play Sokoban :-)).</p> <p>Thus, in general, assuming that P is not equal to NP, any procedure to solve this problem will run in time exponential in $m$.</p> <p>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.</p> http://mathoverflow.net/questions/121871/algorithm-to-solve-sokoban-like-game-on-graphs-move-chips-from-one-set-of-verti/121893#121893 Answer by Dima Pasechnik for Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another Dima Pasechnik 2013-02-15T11:56:57Z 2013-02-15T11:56:57Z <p>Not an answer, but an improved version of the question:</p> <p>Consider a directed graph $G=(V,A)$, and a subset $F\subset V$ of <em>final</em> 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:</p> <ul> <li>choose an arc $vu\in A$ with a chip on $v$ no chip on $u$;</li> <li>move the chip from $v$ onto $u$.</li> </ul> <p>(i.e., with the formalism of functions, we modify $c$ so that $u$ enters $c^{-1}(V)$, and $v$ leaves $c^{-1}(V)$.)</p> <p>The <strong>goal</strong>: cover $F$ with chips. (i.e., achieve $c([1,2,\dots, m])=F$).</p> <p><strong>Question</strong>: what is the complexity of deciding whether the goal can be reached.</p> http://mathoverflow.net/questions/121353/complexity-of-finding-optimal-matchings-of-given-fixed-size/121398#121398 Answer by Dima Pasechnik for complexity of finding optimal matchings of given fixed size Dima Pasechnik 2013-02-10T15:14:57Z 2013-02-10T15:14:57Z <p>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 <a href="http://equatorialmaths.wordpress.com/2009/09/23/hungarian-algorithm-take-1/" rel="nofollow">old notes</a>, or Sect. 3.5 of <a href="http://homepages.cwi.nl/~lex/files/dict.pdf" rel="nofollow">A.Schrijver's lecture notes</a>. </p> <p>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 href="http://homepages.cwi.nl/~lex/files/book.pdf" rel="nofollow">A.Schrijver's 3-volume work</a>.</p> http://mathoverflow.net/questions/118494/largest-permutation-group-without-2-cycles-or-3-cycles/118498#118498 Answer by Dima Pasechnik for Largest permutation group without 2-cycles or 3-cycles Dima Pasechnik 2013-01-10T03:21:59Z 2013-01-10T03:31:09Z <p>For small $n$ your construction is not optimal (e.g. for $n=6$ there is a group of size 120, isomorphic to $S_5$; <a href="http://en.wikipedia.org/wiki/Mathieu_group" rel="nofollow">$M_{12}$</a>) is an example for $n=12$, the biggest exceptional $n$, it seems). </p> <p>But for sufficiently large $n$, your construction is <i>almost</i> 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:</p> <ul> <li>prove that this is the best possible with intransitive groups</li> <li>same for imprimitive groups</li> <li>for primitive groups, invoke <a href="http://www.maths.qmul.ac.uk/~raw/talks_files/ONStalk.pdf" rel="nofollow">O'Nan-Scott theorem</a> (eventually, the classification of finite simple groups).</li> </ul> <p>Perhaps there is a better way to deal with the last step, I don't know.</p> http://mathoverflow.net/questions/118386/a-sum-related-to-the-johnson-association-scheme/118443#118443 Answer by Dima Pasechnik for A sum related to the Johnson association scheme Dima Pasechnik 2013-01-09T12:24:29Z 2013-01-09T12:24:29Z <p>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 href="http://www.math.upenn.edu/~wilf/AeqB.html" rel="nofollow">A=B</a>. </p> <p>Then, perhaps, hypergeometric identities can be applied, but at least having your sum encoded like this might help.</p> http://mathoverflow.net/questions/118037/on-the-positive-definiteness-of-a-linear-combination-of-matrices/118214#118214 Answer by Dima Pasechnik for On the Positive Definiteness of a Linear Combination of Matrices Dima Pasechnik 2013-01-06T17:30:26Z 2013-01-07T09:43:42Z <p>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</p> <p>{$y\in \mathbb{R}^m\mid \det M_{KK}(y)&gt;0, \ K=(1,\dots,k), 1\leq k\leq n$} is nonempty.</p> <p>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$. </p> http://mathoverflow.net/questions/117774/automorphism-group-of-orbital-graphs/117788#117788 Answer by Dima Pasechnik for automorphism group of orbital graphs Dima Pasechnik 2013-01-01T17:01:15Z 2013-01-02T17:24:49Z <p>The property of $G$ you are looking at is called <em>2-closure</em>, 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. <em>J. London Math. Soc.</em> (2) <strong>37</strong> (1988), no. 2, 241–252, where this question is investigated for a particular class of primitive permutation groups.</p> <p>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$.</p> <p>In general such a classification is not known, and the problem is hopelessly hard, I think.</p> http://mathoverflow.net/questions/117562/graph-of-s-n-with-respect-to-transposition/117590#117590 Answer by Dima Pasechnik for Graph of $S_n$ with respect to transposition Dima Pasechnik 2012-12-30T05:23:02Z 2012-12-30T05:23:02Z <p>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$.</p> <p>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.</p> <p>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)$.</p> <p>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.</p> http://mathoverflow.net/questions/117399/extreme-rays-in-the-cone-of-semimetrics/117405#117405 Answer by Dima Pasechnik for Extreme rays in the cone of (semi)metrics Dima Pasechnik 2012-12-28T13:14:37Z 2012-12-28T13:14:37Z <p>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 ?</p> <p>There was a quite a bit of computer search done to go beyond $n=5$ in Avis' paper. E.g. I think <a href="http://www.cas.mcmaster.ca/~deza/lncs1996.pdf" rel="nofollow">here</a> you can find results for $n=7$. There are more links on a <a href="http://www.cas.mcmaster.ca/~deza/metric.html" rel="nofollow">page</a> maintained by A.Deza.</p> <p>I admit I don't recall asymptotic results, although it has been a while.</p> http://mathoverflow.net/questions/117147/confused-about-orbits/117157#117157 Answer by Dima Pasechnik for Confused about orbits Dima Pasechnik 2012-12-24T17:42:13Z 2012-12-24T17:42:13Z <p>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:</p> <ol> <li>{(1,1)}</li> <li>{(x,x) | x in {2..c}}</li> <li>{(p,p) | p in P}</li> <li>{(x,y) | x,y in {2..c}, x not equal to y}</li> <li>{(p,q) | p,q in P, the corresponding pairs of elements of {2..c} do not intersect}</li> <li>{(p,q) | p,q in P, the corresponding pairs of elements of {2..c} intersect in one element}</li> <li>{(1,x) | x in {2..c}}</li> <li>{(x,1) | x in {2..c}}</li> <li>{(1,p) | p in P}</li> <li>{(p,1) | p in P}</li> <li>{(x,p) | x in {2..c}, p in P, x in p}</li> <li>{(p,x) | x in {2..c}, p in P, x in p}</li> <li>{(x,p) | x in {2..c}, p in P, x not in p}</li> <li>{(p,x) | x in {2..c}, p in P, x not in p}</li> </ol> http://mathoverflow.net/questions/116962/strongly-regular-cayley-graphs/116964#116964 Answer by Dima Pasechnik for Strongly regular cayley graphs Dima Pasechnik 2012-12-21T10:51:34Z 2012-12-21T10:51:34Z <p>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 <a href="http://www.win.tue.nl/~aeb/graphs/Paulus.html" rel="nofollow">http://www.win.tue.nl/~aeb/graphs/Paulus.html</a>.</p> http://mathoverflow.net/questions/116220/what-graph-parameters-are-determined-by-parameters-for-strongly-regular-graph/116261#116261 Answer by Dima Pasechnik for What graph parameters are determined by parameters for strongly regular graph Dima Pasechnik 2012-12-13T09:41:41Z 2012-12-20T17:10:53Z <p>It's a classic result that a graph parameter called <i>Lovasz theta-function</i> $\theta(\Gamma)$ of a strongly regular graph $\Gamma$ is determined by its parameters. And the significance of $\theta(\Gamma)$ is that it is <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1a1" rel="nofollow">"sandwiched"</a> between the clique number and the chromatic number.</p> <p>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.</p> http://mathoverflow.net/questions/42386/poles-from-the-continued-fraction-expansion-of-the-tangent-function/116426#116426 Answer by Dima Pasechnik for Poles from the Continued Fraction Expansion of the Tangent Function? Dima Pasechnik 2012-12-15T03:49:33Z 2012-12-15T03:49:33Z <p>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|&lt;|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.</p> http://mathoverflow.net/questions/116372/k-paths-between-two-nodes-in-a-network/116373#116373 Answer by Dima Pasechnik for K Paths between two nodes in a network Dima Pasechnik 2012-12-14T13:44:28Z 2012-12-15T02:47:30Z <p>my understanding that this basically can be done by linear programming, as a variation of the classical max-flow min-cut approach. See this <a href="http://logic.pdmi.ras.ru/~gravin/Papers/k-path_camera.pdf" rel="nofollow">paper</a> in J. Graph Theory 67(2011) 34-37.</p> <p>Needless to say, in the non-directed case one can replace each edge by a pair of arcs going in opposite directions.</p> http://mathoverflow.net/questions/116256/are-there-pairs-of-combinatorial-graphs-that-are-both-isospectral-and-have-the-sa/116258#116258 Answer by Dima Pasechnik for are there pairs of combinatorial graphs that are both isospectral and have the same matroid? Dima Pasechnik 2012-12-13T09:18:26Z 2012-12-13T10:28:17Z <p>There exist co-spectral trees. As there are no cycles to preserve, they fit the bill.</p> <p>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 <i>twist</i>, 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$. </p> http://mathoverflow.net/questions/116069/exact-arithmetic-for-real-algebraic-numbers/116077#116077 Answer by Dima Pasechnik for Exact arithmetic for real algebraic numbers Dima Pasechnik 2012-12-11T13:04:52Z 2012-12-12T13:51:39Z <p>In the <a href="http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html" rel="nofollow">reference</a> 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). </p> <p>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".</p> <p>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 <a href="http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html" rel="nofollow">reference</a>. </p> <p>Thom encodings really shine when one has a parametric (e.g. multivariate), or/and a non-Archimedean, setting. </p> <p>Computation with isolating intervals is implemented e.g. in <a href="http://sagemath.org/" rel="nofollow">Sage</a>.</p> <pre><code>sage: s=sqrt(AA(2)) sage: s.numerical_approx(prec=1000) 1.4142135623730950488016887242096980785696718753769480731766797379907324784... sage: s&gt;AA(0) True sage: t=s-sqrt(AA(3)) sage: t.minpoly() x^4 - 10*x^2 + 1 sage: t.sign() -1 </code></pre> http://mathoverflow.net/questions/115677/is-the-tensor-product-of-polyhedra-a-polyhedron/115705#115705 Answer by Dima Pasechnik for Is the tensor product of polyhedra a polyhedron? Dima Pasechnik 2012-12-07T11:45:33Z 2012-12-07T12:46:34Z <p>An obvious route to a proof of <b>6</b> 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. </p> <p>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(...). </p> http://mathoverflow.net/questions/115608/sat-and-arithmetic-geometry/115630#115630 Answer by Dima Pasechnik for SAT and Arithmetic Geometry Dima Pasechnik 2012-12-06T17:23:37Z 2012-12-06T17:23:37Z <p>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 <a href="http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html" rel="nofollow">book</a>.</p> <p>Groebner bases (in characteristic 0) are also usually beaten by the machinery of <a href="http://homepages.cwi.nl/~monique/files/convex_pop_hierarchy_rev2.pdf" rel="nofollow">semidefinite programming relaxations</a>. Perhaps not coincidentally, a lot of recent work in computational complexity (in particular, approximation algorithms) uses semidefinite programming relaxations, too.</p> <p>There is also a <a href="http://en.wikipedia.org/wiki/Blum-Shub-Smale_machine" rel="nofollow">line of research</a> where the complexity is investigated w.r.t. arithmetic operations in $\mathbb{C}$ (or $\mathbb{R}$) having unit cost. </p> http://mathoverflow.net/questions/115270/how-to-work-with-infinite-random-graphs/115303#115303 Answer by Dima Pasechnik for How to work with infinite random graph(s) ? Dima Pasechnik 2012-12-03T14:50:14Z 2012-12-03T14:50:14Z <p>Do you mean countably infinite random graphs with probability of any two vertices being joined a constant? <a href="http://www.maths.qmul.ac.uk/~pjc/" rel="nofollow">Peter Cameron</a> wrote about these graphs in his books, and in his <a href="http://cameroncounts.wordpress.com/2010/07/09/the-random-graph-1/" rel="nofollow">blog</a> (there are more posts on the topic there).</p> http://mathoverflow.net/questions/114975/bounding-the-sum-of-the-entries-of-the-inverse-of-a-0-1-matrix-away-from-1 bounding the sum of the entries of the inverse of a 0-1 matrix away from 1? Dima Pasechnik 2012-11-30T13:01:45Z 2012-12-01T10:46:50Z <p>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?</p> <p>More precisely, the <i>conjecture</i> 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). </p> <p><b>Remark.</b> The condition $a\geq 1$ is not redundant, as there exist matrices $A$ with $a&lt;1$, e.g. $$A=\left(\begin{array}{rrrr} 0 &amp; 0 &amp; 0 &amp; 1 \&bsol; 0 &amp; 0 &amp; 1 &amp; 0 \&bsol; 0 &amp; 1 &amp; 1 &amp; 1 \&bsol; 1 &amp; 0 &amp; 1 &amp; 1 \end{array}\right), \quad A^{-1}=\left(\begin{array}{rrrr} -1 &amp; -1 &amp; 0 &amp; 1 \&bsol; -1 &amp; -1 &amp; 1 &amp; 0 \&bsol; 0 &amp; 1 &amp; 0 &amp; 0 \&bsol; 1 &amp; 0 &amp; 0 &amp; 0 \end{array}\right), \quad a=\sum_{i,j} (A^{-1})_{ij}=0.$$</p> <p>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}$$</p> http://mathoverflow.net/questions/114316/lines-through-a-n-reflection-arrangement-and-permutations lines through A_n reflection arrangement and permutations Dima Pasechnik 2012-11-24T06:59:46Z 2012-11-25T15:42:39Z <p>(<strong>updated</strong>; apologies for way too much room left for interpretation in the original post)</p> <p>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 <i>cells</i>) 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)$&lt;$d(x,e_2)$&lt;...&lt;$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$.</p> <p>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 <i>flipping</i> the adjacent entries, i.e. applying the transposition $(k,k+1)$ to the sequence $\sigma(c)$.</p> <p>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: </p> <ol> <li>(12), (23), (12)</li> <li>(23), (12), (23)</li> </ol> <p><b>Question.</b> Are all the sequences of $\binom{n}{2}$ <i>flips</i> leading from $1,2, \dots, n$ to $n, n-1, n-2, \ldots 1$ realized by general position lines in $H$? </p> http://mathoverflow.net/questions/113910/a-certain-type-of-quadratic-constrained-quadratic-programming-problem-qcqp/113958#113958 Answer by Dima Pasechnik for A certain type of Quadratic Constrained Quadratic Programming Problem (QCQP) Dima Pasechnik 2012-11-20T16:21:10Z 2012-11-20T16:21:10Z <p>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. <a href="http://arxiv.org/abs/cs.SC/0403008" rel="nofollow">this</a>.</p> <p>The complex case can obviously be reduced to the real one.</p> http://mathoverflow.net/questions/128352/what-are-the-most-important-open-problems-in-algebraic-combinatorics Comment by Dima Pasechnik Dima Pasechnik 2013-04-22T13:30:59Z 2013-04-22T13:30:59Z algebraic combinatorics is a wide subject (Stanley naturally, only treats problems from &quot;his&quot; area) and what really is &quot;biggest&quot; is a very subjective question. http://mathoverflow.net/questions/126507/two-questions-about-combinatorics-journals Comment by Dima Pasechnik Dima Pasechnik 2013-04-04T13:17:36Z 2013-04-04T13:17:36Z 1. The list contains a number of highly questionable entries... http://mathoverflow.net/questions/125277/inversion-of-complex-matrix Comment by Dima Pasechnik Dima Pasechnik 2013-04-03T16:43:54Z 2013-04-03T16:43:54Z does $AB=BA$ hold, by any chance? http://mathoverflow.net/questions/126164/strassens-algorithm Comment by Dima Pasechnik Dima Pasechnik 2013-04-01T13:17:12Z 2013-04-01T13:17:12Z What exactly do you mean by &quot;any algorithm&quot;? IMHO any procedure performing a sequence of arithmetic operations can be expressed by the tensor formalism, but beyond that one cannot say anything. http://mathoverflow.net/questions/126060/on-mentioning-recommenders-names-in-cover-letter-for-postdoctoral-applications/126068#126068 Comment by Dima Pasechnik Dima Pasechnik 2013-03-31T06:53:54Z 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. http://mathoverflow.net/questions/125721/polyhedra-classification/125723#125723 Comment by Dima Pasechnik Dima Pasechnik 2013-03-27T14:14:35Z 2013-03-27T14:14:35Z I wonder if anyone looked at the non-convex case. http://mathoverflow.net/questions/125581/automorphisms-of-graphs-and-finite-permutation-groups/125609#125609 Comment by Dima Pasechnik Dima Pasechnik 2013-03-26T11:49:09Z 2013-03-26T11:49:09Z regarding dessin d'enfant, I liked this book by S.Lando and A.Zvonkin: <a href="http://www.springer.com/mathematics/geometry/book/978-3-540-00203-1" rel="nofollow">springer.com/mathematics/geometry/book/&hellip;</a> Other than that, I can't help noticing that our answers have virtually empty intersection. :–) http://mathoverflow.net/questions/125544/conditions-for-a-graph-to-be-the-1-skeleton-of-a-surface Comment by Dima Pasechnik Dima Pasechnik 2013-03-25T17:06:59Z 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 :–)) http://mathoverflow.net/questions/122449/vector-chromatic-number-and-lovasz-theta/124200#124200 Comment by Dima Pasechnik Dima Pasechnik 2013-03-25T12:07:18Z 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. http://mathoverflow.net/questions/125454/cyclically-symmetric-functions Comment by Dima Pasechnik Dima Pasechnik 2013-03-24T16:06:36Z 2013-03-24T16:06:36Z There is an example with the cyclic group of order 5 in B.Sturmfels' &quot;Algorithms in invariant theory&quot;, 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' &quot;Algorithms in invariant theory&quot; (2nd edition) ISBN 978-3-211-77416-8 Springer 2008, Wien New-York http://mathoverflow.net/questions/124894/rigorous-numerics-for-maxima-and-minima-one-variable/124914#124914 Comment by Dima Pasechnik Dima Pasechnik 2013-03-19T16:20:23Z 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... http://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-tim/92961#92961 Comment by Dima Pasechnik Dima Pasechnik 2013-03-17T13:26:49Z 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. http://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-tim/92961#92961 Comment by Dima Pasechnik Dima Pasechnik 2013-03-17T13:22:21Z 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. http://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-tim/92961#92961 Comment by Dima Pasechnik Dima Pasechnik 2013-03-17T13:18:37Z 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. http://mathoverflow.net/questions/124601/looking-for-a-maximum Comment by Dima Pasechnik Dima Pasechnik 2013-03-15T17:21:24Z 2013-03-15T17:21:24Z convert to an integral, note that erf is an integral too, change the order of integration...