User david benson-putnins - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T03:16:51Z http://mathoverflow.net/feeds/user/3669 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/131473/approximating-higher-dimension-step-function/131756#131756 Answer by David Benson-Putnins for Approximating higher dimension step function David Benson-Putnins 2013-05-24T18:02:47Z 2013-05-24T18:02:47Z <p>A first pass to get continuity: for $||s||\geq \epsilon$, $f(s) = s/||s||$. For $||s||&lt;\epsilon$,</p> <p>$f(s) = \frac{s}{||s||} (e^{1/\epsilon^2-1/||s||^2})$</p> <p>If you want differentiability you just need to fiddle with the $&lt; \epsilon$ function to have a derivative of 0 in the increasing $||s||$ direction at $||s||=\epsilon$ (I'm not quite motivated enough to figure it out)</p> <p>Alternatively if you're willing to accept your function never quite being correct</p> <p>$f(s) = e^{-\epsilon/||s||^2} \frac{s}{||s||}$</p> http://mathoverflow.net/questions/43148/basic-results-with-three-or-more-hypotheses/130854#130854 Answer by David Benson-Putnins for Basic results with three or more hypotheses David Benson-Putnins 2013-05-16T17:24:08Z 2013-05-16T17:24:08Z <p>Let $A\subset \mathbb{R}^d$ be (a)closed, (b) convex, and (c) contains the origin. Then $\left( A^{o} \right)^{o} = A$ where $o$ denotes the polar of $A$</p> http://mathoverflow.net/questions/130763/sums-of-uniformly-random-vectors-from-the-n-dimensional-unit-ball/130779#130779 Answer by David Benson-Putnins for Sums of uniformly random vectors from the $n$-dimensional unit ball David Benson-Putnins 2013-05-16T00:37:48Z 2013-05-16T04:36:43Z <p>EDIT: Woops just realized the vectors are drawn from the ball, not the sphere. But the measure of the ball is almost entirely concentrated at the sphere so the same result should apply with just slightly weaker asymptotics</p> <p>This is a concentration of measure problem on the sphere for fixed $k$ and large $n$. The probability that $|\left&lt; v_1, v_j \right>| \leq \epsilon$ for each fixed $j$ is larger than $1-2e^{-\epsilon^2 n/2}$. So the probability it holds for all $j$ is at least $1-2k e^{-\epsilon^2 n/2}$. The probability that it holds for all pairs of $i$ and $j$ $|\left&lt; v_i, v_j \right>| \leq \epsilon$ is at least $1-2k^2 e^{-\epsilon^2 n/2}$. For any $k$, we can pick $\epsilon$ very small so that this condition implies that $v_1+...+v_k$ has norm almost $\sqrt{k}$ with very high probability if $n$ is large enough.</p> <p>To nail down some more asymptotics, let $w= v_1+...+v_k$.</p> <p>$\left&lt; w, w \right> = k + \sum_{i\neq j} \left&lt; v_i,v_j \right>$.</p> <p>This means that with probability at least $1-2k^2 e^{-\epsilon^2 n/2}$ we have $k-k^2 \epsilon \leq||w||^2 \leq k+ k^2\epsilon$. Choose $\epsilon$ to get the desired level of resolution for large $n$. For example if $\epsilon = 1/k^3$, we get if $d&lt; \sqrt{k-1/k}$ that $||w|| \geq d$ with probability larger than $1-2k^2 e^{-n/(2k^6)}$ and if $d > \sqrt{k+1/k}$ that $||w||\geq d$ with probability smaller than $2k^2 e^{-n/(2k^6)}$</p> http://mathoverflow.net/questions/130492/higher-dimensional-convex-hull/130504#130504 Answer by David Benson-Putnins for Higher dimensional convex hull David Benson-Putnins 2013-05-13T16:32:24Z 2013-05-13T16:32:24Z <p>I think the answer is yes. First observe that $CH(P) \subset CH(S)\cap H$: if $x\in CH(P)$ then $x$ is written as a convex combination of things which are convex combinations of vertices of $CH(S)$, so is a convex combination of vertices of $CH(S)$.</p> <p>Then we note that $CH(S)\cap H$ has as its vertices the points in $P$ corresponding to $E(v)$ (in general this is going to be all of $E(v)$ are, which are all contained in $P$ of course so $CH(S)\cap H \subset CH(P)$ and the two sets are equal, and we know the vertices of $CH(S)\cap H$</p> <p>To see that $CH(S) \cap H$ has the correct vertices, the faces of $CH(S) \cap H$ correspond to faces of $CH(S)$ with their dimension dropped by at most 1 (if the face happens to be parallel to the hyperplane, then it will not drop in dimension). The edges in $E(v)$ cannot be parallel to the hyperplane because that means the hyperplane does not separate $v$ and the corresponding vertex on the other side of the edge</p> http://mathoverflow.net/questions/130422/strategic-vertex-labeling/130450#130450 Answer by David Benson-Putnins for Strategic vertex labeling David Benson-Putnins 2013-05-13T03:18:08Z 2013-05-13T03:18:08Z <p>Some observations which are too long for a comment to simplify the problem. The edges that are do not connect to G' are irrelevant, as is every 0 vertex that is outside of G'. So we can throw those away. If a vertex in G' has some 1s and some -1s, then we know that if we make it a 1 we get the sum of the weights to the 1s - weights to (-1)s, and if we make the G' vertex a -1 we get negative that contributed to the sum. So we can throw away G entirely and we have a graph G' with weights $w_{ij} > 0$ for each edge, and weights $v_k$ of any sign for each vertex and we want to maximize </p> <p>$\sum_{i,j} w_{ij} l_i l_j + \sum_{k} v_k l_k$</p> <p>This is resistant to a greedy algorithm attempt. For example suppose that I have twelvevertices, which I will label $a$ and $b_1,...b_{11}$. My objective is to pick each $l_j$ one at a time to maximize the sum given the other $l_j$s. I'll call the labels $l_a$ and $l_1,..,l_{11}$. If $v_a = 10$ and $v_j = -1$ for each $j$, and $w_{aj} = 1.001$ for each $j$, and there are no other edges, then the first thing you would do is assign $l_a = 1$. After that, assigning $l_j=1$ increases the sum by .001, and making it a $-1$ decreases it by .01, so you would make each $l_j = 1$ and the total sum would be 10.01.</p> <p>But if I had instead assigned each vertex a $-1$ labeling, my total sum would be 11.01. Also the greedy algorithm solution of all 1s is resistant to changing a single vertex, so trying to solve this on a local level is probably impossible</p> http://mathoverflow.net/questions/129802/counting-integer-points-in-a-minkowski-sum/129845#129845 Answer by David Benson-Putnins for Counting integer points in a Minkowski sum David Benson-Putnins 2013-05-06T14:24:26Z 2013-05-06T14:24:26Z <p>Proving this is actually problem 3 on page 164 of Integer Points in Polyhedra by Alexander Barvinok - the number of integer points is a polynomial in $t_1,...,t_k$ as long as they are non-negative integers.</p> <p>Proof omitted at the moment because I'm too rusty to produce one</p> http://mathoverflow.net/questions/96745/finding-a-hamiltonian-circuit-using-nearest-neighbor-algorithm/96746#96746 Answer by David Benson-Putnins for Finding a Hamiltonian Circuit using Nearest-neighbor algorithm David Benson-Putnins 2012-05-12T05:57:47Z 2012-05-12T05:57:47Z <p>The nearest neighbor algorithm as I understand it (repeatedly select a neighboring vertex that hasn't been visited yet and travel to that vertex) does not guarantee that you will find a circuit even if one exists. For example consider the graph with vertices A,B,C,D with edges AB, AC, AD, BC and CD (a complete graph on 4 vertices with edge BD removed). Starting at A, you travel to C. You can then travel to either B or D, at which point your only choice is to go back to A. So if you go from A to C, you can't complete the loop and construct a Hamiltonian circuit even though one exists.</p> http://mathoverflow.net/questions/95632/maximum-singular-value-of-a-random-1-1-matrix/95669#95669 Answer by David Benson-Putnins for Maximum Singular Value of a random +1/-1 matrix David Benson-Putnins 2012-05-01T13:48:28Z 2012-05-01T13:48:28Z <p><a href="http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf" rel="nofollow">http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf</a> Theorem 5.39 (page 23) gives a non-asymptotic upper bound on the largest singular value</p> http://mathoverflow.net/questions/95549/finding-missing-edge-in-dag-which-when-added-would-create-the-longest-cycle/95561#95561 Answer by David Benson-Putnins for finding missing edge in DAG which, when added, would create the longest cycle David Benson-Putnins 2012-04-30T07:47:41Z 2012-04-30T07:47:41Z <p>Actually your context tells us you are interested in a much simpler problem. Rather than finding the longest directed simple path in the graph, you are only interested in the longest directed simple path which ends at a specified vertex (the person who is using the app at that moment). So if you just construct a new graph which reverses the directions of the edges, and from that specified vertex do a DFS/BFS to find the longest directed simple path starting at that vertex, the endpoint of that path is the person who should be recommended as a person to 'thank'. In your search you can keep track of the k longest paths if you want to recommend multiple people for thanking</p> http://mathoverflow.net/questions/13533/binary-codes-with-large-distance/13559#13559 Answer by David Benson-Putnins for Binary codes with large distance David Benson-Putnins 2010-01-31T14:49:20Z 2010-01-31T14:49:20Z <p>Gama doesn't have to be negative, in fact if delta is smaller than 1/2 gamma will be positive. It's known for Hadamard codes that arbitrarily large codes exist, and it seems intuitive that if the distance between vectors should be smaller then large codes should exist still, but I don't have a proof</p> http://mathoverflow.net/questions/131473/approximating-higher-dimension-step-function/131756#131756 Comment by David Benson-Putnins David Benson-Putnins 2013-05-24T22:28:28Z 2013-05-24T22:28:28Z <a href="http://www.wolframalpha.com/input/?i=x%2F%7Cx%7C+e%5E%7B-.0000001%2Fx%5E2%7D" rel="nofollow">wolframalpha.com/input/&hellip;</a> It's differentiable at zero because $e^{-\epsilon/||s||^2}$ goes to zero so fast. By &quot;never quite being correct&quot; I meant there is no choice of s for which f(s) = s/||s|| exactly http://mathoverflow.net/questions/131473/approximating-higher-dimension-step-function/131756#131756 Comment by David Benson-Putnins David Benson-Putnins 2013-05-24T21:58:48Z 2013-05-24T21:58:48Z The second option is defined for all s in one shot, not piecewise. http://mathoverflow.net/questions/131238/real-root-of-a-cubic-equation/131242#131242 Comment by David Benson-Putnins David Benson-Putnins 2013-05-20T16:36:16Z 2013-05-20T16:36:16Z It seems like you should just post your specific polynomial http://mathoverflow.net/questions/130521/number-of-edges-in-graph-in-terms-of-reliability Comment by David Benson-Putnins David Benson-Putnins 2013-05-14T03:58:38Z 2013-05-14T03:58:38Z Yuichiro, $p^c$ is the probability that the minimum cut gets removed (and the other edges do whatever), which necessarily disconnects the graph. http://mathoverflow.net/questions/130492/higher-dimensional-convex-hull/130504#130504 Comment by David Benson-Putnins David Benson-Putnins 2013-05-13T17:51:17Z 2013-05-13T17:51:17Z If you think of CH(S) as being a polyhedron: A polyhedron P of dimension n has a face F of dimension d if there are n-d linearly independent inequalities for P which are active (have an equality at that point). So if we take P=CH(S), the edges are the places were n-1 inequalities are active. If we restrict to $CH(S)\cap H$, inequalities for $P$ correspond to inequalities for $CH(S)\cap H$ inside of $H$. The edge which originally had n-1 active inequalities still has n-1 active inequalities inside of $H$ as long as $H\cap edge$ is not equal to the whole edge http://mathoverflow.net/questions/130492/higher-dimensional-convex-hull/130501#130501 Comment by David Benson-Putnins David Benson-Putnins 2013-05-13T16:17:39Z 2013-05-13T16:17:39Z The excluded dot isn't lying on an edge of the volume though, is it? http://mathoverflow.net/questions/130422/strategic-vertex-labeling/130426#130426 Comment by David Benson-Putnins David Benson-Putnins 2013-05-13T02:42:22Z 2013-05-13T02:42:22Z Actually wait this makes the problem fairly trivial &quot;the challenge is to relabel the 0s on the side of G′ in such way that product of labels on both sides maximizes the sum &quot; If all I'm worried about is the sum over the boundary edges then I can pick each vertex independently as a 1 or a -1 to maximize the sum of its edge weights. It's only interesting if the internal edges of G' are included as well http://mathoverflow.net/questions/130422/strategic-vertex-labeling/130426#130426 Comment by David Benson-Putnins David Benson-Putnins 2013-05-13T01:49:05Z 2013-05-13T01:49:05Z Dustin, I don't think it's correct anyway. The correct labeling of G' would be to just set every value to 1. Solving maxcut would be equivalent to minimizing the sum wouldn't it? http://mathoverflow.net/questions/130422/strategic-vertex-labeling/130426#130426 Comment by David Benson-Putnins David Benson-Putnins 2013-05-12T18:29:03Z 2013-05-12T18:29:03Z Joseph this comment confused me a little.. from your original post I would have thought that G' had ALL the vertices with weight 0, but from the comment it sounds like G' only contains some of them, and some might be left in G. I'm not sure if it makes a difference in the problem since any leftover 0 vertices can just be ignored but I wanted to check which interpretation is correct http://mathoverflow.net/questions/130363/non-convex-polytope-definition Comment by David Benson-Putnins David Benson-Putnins 2013-05-11T20:07:41Z 2013-05-11T20:07:41Z Apparently wikipedia has a very broad definition of polytope <a href="http://en.wikipedia.org/wiki/Polytope" rel="nofollow">en.wikipedia.org/wiki/Polytope</a> But I have only seen polytope be used to mean that definition, which immediately implies that it is convex http://mathoverflow.net/questions/130120/bipartite-graph-coloring Comment by David Benson-Putnins David Benson-Putnins 2013-05-08T21:31:22Z 2013-05-08T21:31:22Z The number of colors that you are required to use is basically independent of N because of how little it affects the graph. Consider the following graph: I have a vertex in V1 connected to N vertices in V2. I also have a bunch of vertices in V1 which are connected to vertices in V2 that aren't from the original N. The number of colors required is essentially independent of N The number required can also be arbitrarily high. For the vertex set V2, for each pair of vertices put a vertex in V1 that connects to both of them. Then every vertex in V2 needs to be colored differently. http://mathoverflow.net/questions/129886/enumerating-counting-paths-of-a-given-length-on-a-2d-lattice Comment by David Benson-Putnins David Benson-Putnins 2013-05-06T21:45:21Z 2013-05-06T21:45:21Z When you say &quot;2D lattice&quot; you mean explicitly $\mathbb{Z}^2$? http://mathoverflow.net/questions/129843/integral-inequality-for-convex-function/129863#129863 Comment by David Benson-Putnins David Benson-Putnins 2013-05-06T18:07:07Z 2013-05-06T18:07:07Z My impression was that there just happened to be some values a and b for which the first equation were true, not that it was true for all a and b. Zamoura, can you clarify this? http://mathoverflow.net/questions/129843/integral-inequality-for-convex-function Comment by David Benson-Putnins David Benson-Putnins 2013-05-06T14:52:30Z 2013-05-06T14:52:30Z I think this is false. For example pick u(x) = 0, c=-1, d=1 (it doesn't matter what a and b are). Then the claim is that $f(0) \geq \frac{1}{2} \int_{-1}^{1} f(x) dx$ which $f(x) = x^2$ shows is false http://mathoverflow.net/questions/96016/another-matrix-diagonalization-problem Comment by David Benson-Putnins David Benson-Putnins 2012-05-04T20:10:34Z 2012-05-04T20:10:34Z Small typo.... the dimension of the input and output of X are the same but that doesn't jive with the nxm shape of X. More importantly I can't figure out what the properties of Q are supposed to be