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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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)