User klaus draeger - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:49:14Z http://mathoverflow.net/feeds/user/6634 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110706/fixed-points-of-system-of-quadratic-equations/110747#110747 Answer by Klaus Draeger for fixed points of system of quadratic equations Klaus Draeger 2012-10-26T11:36:22Z 2012-10-26T11:36:22Z <p>The property does not hold as stated. Consider the case $u=(\frac{1}{2},\dots,\frac{1}{2}), A=\frac{1}{4}I,$ and $Q(x)_i = \frac{1}{4}x_i^2$. Then $\Phi$ maps $(x_1,\dots,x_n)$ to $\frac{1}{4}(x_1^2+x_1+2,\dots,x_n^2+x_n+2)$, and all $x$ with $x_i\in{1,2}$ are fixed points.</p> http://mathoverflow.net/questions/27297/is-this-problem-solvable-in-polynomial-time/27342#27342 Answer by Klaus Draeger for Is this problem solvable in polynomial time? Klaus Draeger 2010-06-07T12:31:39Z 2010-06-07T12:31:39Z <p>There is a straightforward encoding of 3-SAT into this problem, which means that unless P=NP, no, there cannot be a polynomial-time algorithm that solves it. The encoding can be constructed as follows. Given a formula $\phi=\psi_1\wedge\dots\wedge\psi_k$ in conjunctive normal form over propositional variables $v_1,\dots,v_n$, you have the following boxes:</p> <ol> <li>For each $v_i$, two boxes $A_i, B_i$ representing the literals $v_i$ and $\neg v_i$. Both contain a single unit-weight circle. </li> <li>Also for each $v_i$, a box $C_i$ representing the law of the excluded middle: This box contains two circles with weight 0, one connected to $A_i$, the other to $B_i$.</li> <li>For each clause $\psi_j=l_1\vee l_2 \vee l_3$, a box $D_j$ containing three weight-0 circles connected to the corresponding $A_i$ or $B_i$.</li> <li>The root box, containing a single weight-0 circle connected to all the $C_i$ and $D_j$.</li> </ol> <p>This can be done in time linear in the size of $\phi$.</p> <p>Then a set of circles satisfying your constraints must contain at least one of $A_i,B_i$ for all $i$, and has weight $n$ if and only if it corresponds to a valid valuation of the $v_i$ which satisfies $\phi$. In particular, satisfiability of $\phi$ can be decided by checking if the minimum weight solution has weight $n$.</p> http://mathoverflow.net/questions/130573/two-boy-scouts-problems Comment by Klaus Draeger Klaus Draeger 2013-05-14T13:24:33Z 2013-05-14T13:24:33Z Your original problem does sound solvable to me (essentially, you need a $(2n-1)$-edge coloring of $K_{2n}$). Is there an additional constraint (e.g. only one match of each sport per round)? http://mathoverflow.net/questions/121784/who-knows-this-convex-polytope Comment by Klaus Draeger Klaus Draeger 2013-02-14T13:05:47Z 2013-02-14T13:05:47Z No real answer, but I think you want six parallelepipeds, not four. http://mathoverflow.net/questions/106591/sum-of-the-following-series-fibonacci-lucas Comment by Klaus Draeger Klaus Draeger 2012-09-07T11:37:00Z 2012-09-07T11:37:00Z In the step where you add the summation, I don't see why you have a quadratic polynomial factor in $(Luc(n+5)/5)*((n*(n+1)/2)-1)$. That should be just $(Luc(n+5)/5)*(n-1)$. http://mathoverflow.net/questions/99853/resources-aware-combinatorial-game-theory Comment by Klaus Draeger Klaus Draeger 2012-06-18T13:10:21Z 2012-06-18T13:10:21Z Just to clarify: the resources spent on moves are removed from the game? I'm asking because there is also the related version in which they go to the opponent, so that you can actually regain resources (and they don't a priori limit they number of moves). http://mathoverflow.net/questions/89659/affine-space-partition-of-a-general-set Comment by Klaus Draeger Klaus Draeger 2012-02-27T13:52:38Z 2012-02-27T13:52:38Z Do you have any restrictions on the kind of covering you want (minimum number of spaces, say?) After all, every single point of $F_q^n$ is an affine subspace. http://mathoverflow.net/questions/87688/linear-algebra-find-an-n-dimensional-vector-orthogonal-to-a-given-vector Comment by Klaus Draeger Klaus Draeger 2012-02-06T17:21:41Z 2012-02-06T17:21:41Z Are there any other constraints? Otherwise, let $a$ be the given vector. If $a_1=0$, then $(1,0,0,\dots)$ works; if $a_2=0$, then $(0,1,0,0,\dots)$ works; otherwise, $(a_2,-a_1,0,0,\dots)$ works. http://mathoverflow.net/questions/85311/optimization-of-a-specific-polynomial Comment by Klaus Draeger Klaus Draeger 2012-01-11T12:14:00Z 2012-01-11T12:14:00Z Following up on Pietro's comment: Suppose wlog that $c_1,c_2,c_3\neq 0$. Consider the behaviour of $f$ along the line $\{(x,x,x,0,\dots,0)|x\in\mathbb{R}\}$: It reduces to $g(x) = c_1c_2c_3x^3+h(x)$, where $h$ is quadratic, so $g$, and therefore also $f$, is unbounded in both directions. http://mathoverflow.net/questions/77676/is-there-an-upper-bound-to-strongly-connected-components Comment by Klaus Draeger Klaus Draeger 2011-10-10T15:17:21Z 2011-10-10T15:17:21Z Sorry, cannot edit my comment - that should of course be $n(n-1) + m(m+1)\geq 2e$. http://mathoverflow.net/questions/77676/is-there-an-upper-bound-to-strongly-connected-components Comment by Klaus Draeger Klaus Draeger 2011-10-10T13:50:30Z 2011-10-10T13:50:30Z If $e$ is greater than that, you can still get up to $n-m$ SCCs, where $m$ is the least integer such that $n(n-1)+m(m+1)\leq 2e$, by starting with the maximal acyclic graph and adding all back edges into a single SCC of minimal size. http://mathoverflow.net/questions/68436/what-the-heck-is-the-continuum-hypothesis-doing-in-weibels-homological-algebra/68514#68514 Comment by Klaus Draeger Klaus Draeger 2011-06-23T13:03:08Z 2011-06-23T13:03:08Z And even &quot;essentially countable&quot; structures (at least as I understand the term) are not entirely safe, see for example Friedman's paper <a href="http://arxiv.org/abs/math/9811187" rel="nofollow">arxiv.org/abs/math/9811187</a> http://mathoverflow.net/questions/65957/general-integer-solution-for-x2y2-z2-1/65961#65961 Comment by Klaus Draeger Klaus Draeger 2011-05-25T18:20:03Z 2011-05-25T18:20:03Z oops - yes, of course. Thanks! http://mathoverflow.net/questions/65952/n-partite-n-clique Comment by Klaus Draeger Klaus Draeger 2011-05-25T13:45:53Z 2011-05-25T13:45:53Z You would need at least some constraint on the number of isolated vertices, wouldn't you? Currently, the graph with no edges at all is a counterexample. http://mathoverflow.net/questions/65957/general-integer-solution-for-x2y2-z2-1/65961#65961 Comment by Klaus Draeger Klaus Draeger 2011-05-25T13:35:37Z 2011-05-25T13:35:37Z Looks good. One way of getting there is setting $a:=x+z, b:=x-y$ to obtain $ab=(1+y)(1-y)$, so that there must be $r,s,t,u$ with $rs=a,tu=b,1+y=rt,1-y=su$. http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known Comment by Klaus Draeger Klaus Draeger 2011-01-12T14:39:38Z 2011-01-12T14:39:38Z Just to clarify: You are really only interested in languages which satisfy the cyclicity condition and are, in addition, regular? I ask because the condition itself does not imply regularity - consider, for example, the language of well-matched parentheses. http://mathoverflow.net/questions/35787/upper-bound-on-number-of-lines-in-a-linear-space-given-degree-bounds Comment by Klaus Draeger Klaus Draeger 2010-08-17T09:36:44Z 2010-08-17T09:36:44Z For $n &gt; q+2$, that would violate the first condition (since every point would lie on $n-1 &gt; q+1$ lines)