User michael biro - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T06:07:05Z http://mathoverflow.net/feeds/user/19029 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/122801/untangling-entwined-rigid-chains-in-3-space/122832#122832 Answer by Michael Biro for Untangling entwined rigid chains in 3-space Michael Biro 2013-02-24T21:52:38Z 2013-02-24T21:52:38Z <p>Hopefully, someone with better graphics-making ability than me will be able to post a picture of what I'm thinking of (or show that it doesn't work), but here's an attempt to show a pair that require $\Omega(n^2)$ moves.</p> <p>For now, I'm restricting to translations only.</p> <p>The first chain is the standard square wave form in the first figure above. For the second chain, take a square spiral on a plane perpendicular to the square wave. The spiral should have largest side length equal to the vertical height of the square wave (so the only way to move a vertical segment through is by pushing it through that one slot. Now, to force the wave to travel the spiral over and over, we add another piece to the second chain. It should be on a plane parallel to the plane of the spiral, and should be a modified square that is just too small for the wave to fit through. We modify the square on the pair of horizontal sides, adding a small detour to each edge, pushing out a small section and adding little extra space, so that the square wave can fit through only if it is centered on the square. Then, line the two up so the center of the square is lined up with the center of the spiral.</p> <p>Then, the square wave starts going through the center of both parts of the second chain. In order to get each vertical segment through the spiral, we need to go around the spiral to the outside slot, but then to get that vertical segment through the square, we need to spiral back around to the middle.</p> <p>Does that make sense?</p> <p>If it does, it seems plausible to me that we'd be able to make 'rotation guards' to add to the second chain, that force us to do those motions even if rotations are allowed, but I'm not sure.</p> http://mathoverflow.net/questions/119047/unique-circular-ordering-of-edges-around-a-vertex/119109#119109 Answer by Michael Biro for Unique circular ordering of edges around a vertex Michael Biro 2013-01-16T19:40:14Z 2013-01-16T19:40:14Z <p>The converse to the cycle statement doesn't hold. Take a wheel graph, and split each spoke with a new vertex. Then, the center has the fixed circular ordering property, but there is no such cycle. </p> <p>Intuitively, I suspect the full condition for $v$ to have the property is that there exists in the planar graph a (spoke-divided) wheel graph with $v$ at its center with each of $v$'s neighbors dividing a distinct spoke (where the case of the neighbors being on a cycle is with degenerate spoke-dividing).</p> http://mathoverflow.net/questions/110505/is-there-a-simple-test-to-determine-whether-a-polytope-is-integral/110508#110508 Answer by Michael Biro for Is there a simple test to determine whether a polytope is integral? Michael Biro 2012-10-24T03:50:36Z 2012-10-24T03:50:36Z <p>An incomplete solution:</p> <p>There is a polynomial-time test for total unimodularity, and if $A$ is totally unimodular, then the polytope is integral.</p> http://mathoverflow.net/questions/110238/maximizing-the-number-of-lattice-points-in-a-circle-of-radius-r-placed-on-a-lat/110248#110248 Answer by Michael Biro for Maximizing the number of lattice points in a circle of radius $r$ placed on a lattice Michael Biro 2012-10-21T16:58:06Z 2012-10-21T16:58:06Z <p>I want to say that by symmetry, the only relevant centers are lattice points, midpoints of square edges, and centers of squares, and that they each are optimal for varying values of $r > \sqrt(2)$.</p> <p>If we take $r = 1.55$, then the circle centered at a lattice point contains $9$ lattice points, the circle centered on a square contains $4$ lattice points, and the circle centered on an edge midpoint contains $8$ lattice points. Winner: Center on a lattice point.</p> <p>If we take $r = 1.6$, then the circle centered at a lattice point contains $9$ lattice points, the circle centered on a square contains $12$ lattice points, and the circle centered on an edge midpoint contains $8$ lattice points. Winner: Center at the center of a lattice square.</p> <p>If we take $r = 2.1$, then the circle centered on a lattice point contains $13$ lattice points, while the circle centered on a square contains $12$ lattice points, and the circle centered on an edge midpoint contains $16$ lattice points. Winner: Center at the midpoint of a lattice edge.</p> <p>I suspect that the three possible centers cycle through as optimal solutions.</p> http://mathoverflow.net/questions/110211/how-many-binary-operations-are-associative/110212#110212 Answer by Michael Biro for How many binary operations are associative? Michael Biro 2012-10-21T03:58:27Z 2012-10-21T03:58:27Z <p>The are bounds known for the number of semigroups on ${1,2,3,\dots,n}$. This is one reference I found (from 1976), no doubt there are better bounds known by now.</p> <p><a href="http://www.jstor.org/discover/10.2307/2041879?uid=3739920&amp;uid=2134&amp;uid=2&amp;uid=70&amp;uid=4&amp;uid=3739256&amp;sid=21101177017183" rel="nofollow">The Number of Semigroups of Order $n$</a></p> http://mathoverflow.net/questions/106705/2d-problems-which-are-easier-to-solve-in-3d/106774#106774 Answer by Michael Biro for 2D Problems Which are Easier to Solve in 3D Michael Biro 2012-09-10T03:50:22Z 2012-09-10T03:50:22Z <p>Voronoi diagrams in the plane can be described as the lower envelopes of wave-front surfaces in 3D. I'm not sure if this makes them 'easier', but it's a useful way of thinking about them.</p> http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube/103912#103912 Answer by Michael Biro for Minimal blocking objects with shadows like a cube Michael Biro 2012-08-04T04:35:41Z 2012-08-07T07:00:04Z <p>Here is a way to get $26$ for the $C_3(4)$ case, and $2(n^2-n) + 2$ in general. </p> <p>In the bottom level, add $4n-5$ cubes around the outside, leaving one out adjacent to a corner. For the second level, fill in the interior $(n-2)^2$ cubes, add the two diagonal corners (one of which is next to the missing cube from the base), and then put a cube in the missing cube's column. For the remaining $n-2$ levels, stack on the diagonal.</p> <pre> 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 </pre> <p>In general, that works out to $C_3(n) \leq (4n-5) + (n-2)^2 + 3 + n(n-2) = 2(n^2 - n) + 2$</p> <p>Edit: My $26$ bound for $C_3(4)$ has since been improved, but here is an optimal $C_3(5) = 37$ arrangement.</p> <pre> 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 </pre> http://mathoverflow.net/questions/93521/area-ratio-of-a-minimum-bounding-rectangle-of-a-convex-polygon Area ratio of a minimum bounding rectangle of a convex polygon Michael Biro 2012-04-08T21:35:13Z 2012-06-04T20:23:07Z <p>Take a convex polygon $P$ in the plane, and find its minimum area bounding rectangle, $R$. I'm interested in the ratio of the area of $R$ to the area of $P$. The ratio has a minimum of $1$ for rectangles and is $2$ for triangles. I want to say that $2$ is the maximum ratio possible.</p> <p>Is this known? Is there a nice proof/counterexample for it? </p> http://mathoverflow.net/questions/88946/readings-for-an-honors-liberal-art-math-course/88949#88949 Answer by Michael Biro for Readings for an honors liberal art math course Michael Biro 2012-02-19T18:41:22Z 2012-02-19T18:41:22Z <p>I like "Introduction to Graph Theory" by Trudeau. It's a short (a few hours of reading) introduction to some nice and accessible parts of graph theory.</p> http://mathoverflow.net/questions/83869/getting-started-combinatorial-optimization-for-computer-scientists/83927#83927 Answer by Michael Biro for Getting started: combinatorial optimization for computer scientists Michael Biro 2011-12-20T07:10:03Z 2011-12-20T16:16:59Z <p>For the short version, <a href="http://www.amazon.com/Combinatorial-Optimization-Algorithms-Complexity-Computer/dp/0486402584/ref=sr_1_1?ie=UTF8&amp;qid=1324364722&amp;sr=8-1" rel="nofollow">Combinatorial Optimization</a> by Papadimitriou and Stieglitz is a good introduction, and at $12, you can't really go wrong.</p> <p>For the in-depth version, <a href="http://www.amazon.com/Combinatorial-Optimization-3-B-C/dp/3540443894/ref=sr_1_3?s=books&amp;ie=UTF8&amp;qid=1324397794&amp;sr=1-3" rel="nofollow">Combinatorial Optimization</a> by Schrijver is pretty encyclopedic.</p> http://mathoverflow.net/questions/83881/a-book-in-topology/83885#83885 Answer by Michael Biro for A book in topology Michael Biro 2011-12-19T18:21:34Z 2011-12-19T18:21:34Z <p>I'd recommend a combination. <a href="http://www.amazon.com/Topology-2nd-James-Munkres/dp/0131816292" rel="nofollow">Topology</a> by Munkres for the point set stuff, and <a href="http://www.math.cornell.edu/~hatcher/AT/ATpage.html" rel="nofollow">Algebraic Topology</a> by Hatcher for the algebraic topology. You get all the advantages of two more specialized textbooks, and since Hatcher's text is free, your students won't need to buy two textbooks. </p> http://mathoverflow.net/questions/83432/ratio-of-sequences-sum-inequality Ratio of Sequences Sum Inequality Michael Biro 2011-12-14T16:22:46Z 2011-12-15T23:41:04Z <p>I have two real sequences$a_1,a_2,\dots,a_n$and$b_1, b_2, \dots, b_n$, with$a_i > 0$and$1 \leq b_i &lt; n$, and I'm looking for a lower bound of$\sum_i \frac{a_i}{b_i}$in terms of$\sum_i a_i$and$\sum_i b_i$. There is also an extra contraint that if$b_i$is large then$a_i$is small (something like$a_i &lt; b_i/e^{b_i})$</p> <p>They're not necessarily monotonic, so I can't use Chebyshev's inequality. Is there something else that I'm missing?</p> <p>Edit: </p> <p>After thinking a bit more about the problem I get that, as stated, there are instances where$\sum \frac{a_i}{b_i} = \frac{\sum a_i}{\sum b_i - (n-1)}$. </p> <p>That is if$a_i = \epsilon$for$1 \leq i \leq n-1$and$a_n = \sum a_i - (n-1)\epsilon$, and$b_i = 1$for$1 \leq i \leq n-1$and$b_n = \sum b_i - (n-1)$. Then, as long as$\sum a_i &lt; \frac{\sum b_i - (n-1)}{e^{\sum b_i - (n-1)}} + (n-1)\epsilon$, we get the above as$\epsilon$goes to$0$. Is this tight as long as the inequality is satisfied? If it isn't satisfied, then$\sum a_i$is larger than$\frac{\sum b_i - (n-1)}{e^{\sum b_i - (n-1)}}$, implying that the lower bound should be larger. </p> <p>So to tweak the problem a bit more, what if the inequality isn't satisfied (for small$ \epsilon $)? Say for$\sum a_i = 1$and$\sum b_i = 2n$?</p> http://mathoverflow.net/questions/82928/characteristics-of-locally-triangle-free-graph/82932#82932 Answer by Michael Biro for Characteristics of locally triangle-free graph Michael Biro 2011-12-08T03:48:43Z 2011-12-08T03:48:43Z <p>$G$isn't necessarily connected.</p> <p>Take a pentagon,$1,2,3,4,5$with$D$containing$3$of it's vertices (say$1,3,4$). Triangulate the pentagon with$(2,4)$and$(2,5)$. You can put it inside a bounding triangle with all the proper edges to get it to be a valid triangulation.</p> <p>Then,$G$contains no triangle, and consists of vertices$1,3,$and$4$, along with edge$(3,4)$, and isn't connected. </p> http://mathoverflow.net/questions/82331/smallest-containing-simplex/82356#82356 Answer by Michael Biro for Smallest containing simplex Michael Biro 2011-12-01T08:33:56Z 2011-12-01T08:40:32Z <p>The paper <a href="http://www.springerlink.com/content/cu7rvr8m7vnlhgtr/" rel="nofollow">Parallelotopes of Maximum Volume in a Simplex</a> by Lassak gives the maximum possible volume of a parallelotope in a simplex as$n!/n^n$times the volume of the simplex. This gives us a bound of$V_n \geq n^n/n!$, which I suspect is tight.</p> http://mathoverflow.net/questions/82236/kappa-coloring-of-mathbbr2-and-triangle-with-area-1/82240#82240 Answer by Michael Biro for$\kappa$-coloring of$\mathbb{R}^2$and triangle with area 1 Michael Biro 2011-11-30T02:45:12Z 2011-11-30T02:45:12Z <p>I think that you can always find such a triangle for any finite$\kappa$. Not sure how to prove that though.</p> <p>There are countably infinite colorings that do not contain such a triangle. Partition the plane into a checkerboard of unit squares and color each square a different color. Then, the largest monochromatic triangle has area$0.5 &lt; 1$.</p> http://mathoverflow.net/questions/81499/nim-like-game-winning-strategy/81503#81503 Answer by Michael Biro for Nim-like(?) game winning strategy? Michael Biro 2011-11-21T14:17:29Z 2011-11-21T15:43:01Z <p>Well, if$\sum a_i$is odd, then there cannot be a draw and so by Zermelo's theorem one of the players has a winning strategy. If the sum of the$a_i$'s is even then one player may be able to force a draw.</p> <p>Edit: False statement removed, see answer by Joshua Erde.</p> <p>You could naively work out the min-max tree to find the optimal strategy for each player in$O(2^k)$worst-case time using a branch and bound algorithm, which would probably work much better than$O(2^k)$as a heuristic.</p> <p>Using dynamic programming it can be done in polynomial time.</p> http://mathoverflow.net/questions/80532/maximum-graph-cut-in-directed-planar-graphs/80534#80534 Answer by Michael Biro for Maximum graph cut in directed planar graphs Michael Biro 2011-11-09T23:44:25Z 2011-11-09T23:44:25Z <p>This paper <a href="http://web.cs.gc.cuny.edu/~mlampis/papers/dtreewidthDO.pdf" rel="nofollow">http://web.cs.gc.cuny.edu/~mlampis/papers/dtreewidthDO.pdf</a> proves MAX DICUT hard for DAGs, among other things. Not quite what you're looking for, but support for the idea that it's hard.</p> http://mathoverflow.net/questions/80242/complexity-of-detecting-a-convex-body-in-mathbbrn/80319#80319 Answer by Michael Biro for Complexity of detecting a convex body in$\mathbb{R}^n$? Michael Biro 2011-11-07T17:56:25Z 2011-11-07T17:56:25Z <p>Without more constraints on the problem, there is no deterministic algorithm that can decide which is convex with a finite number of queries. For randomized algorithms, I think that you can never get a finite expected number of queries.</p> <p>Take$K_0$to be a sphere. Run your algorithm, and let every query response be$K_1$. Now, whatever the response of the algorithm, we can construct a contradicting example with the same responses.</p> <p>If the response was$K_1$is convex, take$K_2$to be a small sphere in$K_0$that is disjoint from the query set. Then,$K_2$is convex and$K_1$is not.</p> <p>If the response was$K_2$is convex, we are going to take a slightly flattened sphere to be$K_1$and the non-convex spherical cap to be$K_2$. Take the convex hull of the query points and choose a supporting hyperplane of any face of the convex hull. If we remove the spherical cap defined by the intersection of$K_0$and the hyperplane and bulge the resulting flat face outwards, we get$K_1$as convex and$K_2$is not convex.</p> http://mathoverflow.net/questions/57190/maximizing-the-number-of-correct-literals-in-planar-monotone-3sat Maximizing the number of 'correct' literals in planar monotone 3SAT Michael Biro 2011-03-03T01:07:25Z 2011-03-03T01:07:25Z <p>I'm trying to find the complexity of this optimization problem:</p> <p>Given an instance of planar monotone 3SAT, with positive clauses <code>$C_i = v_{i1} V v_{i2} V v_{i3}$</code> and negative clauses <code>$D_i = not(w_{i1}) V not(w_{i2}) V not(w_{i3})$</code>, (it's possible that <code>$v_{ij} = w_{jl}$</code> for some i,j,k,l), find the 0-1 assignment that maximizes the number of agreeing literals. Basically, maximize <code>$(/sum_{C_i} v_{i1}+v_{i2}+v_{i3}) + (/sum_{D_i} 3 - w_{i1} - w_{i2} - w_{i3})$</code>.</p> <p>Thanks</p> http://mathoverflow.net/questions/29404/network-flow-gadget Network flow gadget Michael Biro 2010-06-24T16:29:02Z 2010-06-25T00:37:52Z <p>Given m units of flow from a source node, and several possible destinations, is there a network flow gadget to force the flow to use only one destination? That is, send all m units to one (unspecified) destination and 0 to all the others?</p> <p>If m = 1, we can just connect the source to the destinations and use the integral flow theorem, but what about m > 1?</p> http://mathoverflow.net/questions/28135/when-is-a-triangular-matrix-totally-unimodular When is a triangular matrix totally unimodular? Michael Biro 2010-06-14T15:35:14Z 2010-06-14T17:37:32Z <p>I have an {0,1}, invertible, triangular matrix, that I would like to show to be totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?</p> http://mathoverflow.net/questions/126911/how-long-can-this-string-of-digits-be-extended Comment by Michael Biro Michael Biro 2013-04-09T05:12:56Z 2013-04-09T05:12:56Z An idea to get past the$b$lower bound - suppose there are$k$different$n$-digit numbers,$n_1,n_2,\dots,n_k$, with the stated property. Look at the values of$b \cdot n_i \mod (n + 1)$and try to argue that if$k$is large enough, there must be an$i$such that$b \cdot n_i \mod (n+1) = (n+1)-m$for$m = 0,1,2,\dots,b-1$. If we take$n = b$, that reduces to showing that not all the numbers have$b\cdot n_i = 1 \mod (b+1)$. http://mathoverflow.net/questions/126060/on-mentioning-recommenders-names-in-cover-letter-for-postdoctoral-applications/126068#126068 Comment by Michael Biro Michael Biro 2013-03-31T05:08:30Z 2013-03-31T05:08:30Z This doesn't come across at all from the applicant side of the MathJobs setup. If what you're saying is true, why even ask for a mandatory cover letter at all? http://mathoverflow.net/questions/126060/on-mentioning-recommenders-names-in-cover-letter-for-postdoctoral-applications/126065#126065 Comment by Michael Biro Michael Biro 2013-03-31T02:43:31Z 2013-03-31T02:43:31Z That's what I did too, except I had longer (short paragraph) description for each of research and teaching. http://mathoverflow.net/questions/125016/maintaining-boundary-of-unit-circle-arrangement/125033#125033 Comment by Michael Biro Michael Biro 2013-03-20T02:04:47Z 2013-03-20T02:04:47Z If we're allowed four crossings, thin rectangles arranged in a square grid pattern gives the$\Omega(n^2)$lower bound, right? http://mathoverflow.net/questions/122801/untangling-entwined-rigid-chains-in-3-space/122832#122832 Comment by Michael Biro Michael Biro 2013-02-25T01:12:35Z 2013-02-25T01:12:35Z Yes, I meant the plane containing the spiral, perpendicular to the axis. http://mathoverflow.net/questions/110505/is-there-a-simple-test-to-determine-whether-a-polytope-is-integral/110508#110508 Comment by Michael Biro Michael Biro 2012-10-24T05:29:34Z 2012-10-24T05:29:34Z Right, if$A$is not totally unimodular then this test is inconclusive. I'm not aware of an efficient test that works for all$A,b$, though I'd certainly be interested to see one! http://mathoverflow.net/questions/110238/maximizing-the-number-of-lattice-points-in-a-circle-of-radius-r-placed-on-a-lat/110248#110248 Comment by Michael Biro Michael Biro 2012-10-21T19:11:54Z 2012-10-21T19:11:54Z Depending on what you mean by small, I think so. Given$r$and a square, look at all lattice points that are in the circle for some center in the square but not in the circle for a different center. There are$O(r)$of these points and if you take the arrangement of radius$r$circles centered at these lattice points, we get$O(r^2)$faces, where two circles of radius$r$with centers in the same face in the square contain the same lattice points. So, there are at most$O(r^2)$different values the function can take, even without looking for peaks, and most small movements won't matter at all. http://mathoverflow.net/questions/110211/how-many-binary-operations-are-associative Comment by Michael Biro Michael Biro 2012-10-21T04:10:25Z 2012-10-21T04:10:25Z Also in the line is <a href="http://oeis.org/A023814" rel="nofollow">oeis.org/A023814</a>, which gives values up to$n = 7$. http://mathoverflow.net/questions/109343/optimal-gear-trains Comment by Michael Biro Michael Biro 2012-10-11T01:41:53Z 2012-10-11T01:41:53Z For$Q3$, take$n = 4$,$t = 2$. It seems to me (no proof, and Will's example might mean that I'm wrong), that the only relevant slowdowns will be either$(2/8)$or$(2/4,2/4)$. The first has teeth cost$10$and metal cost$68$, while the second has teeth cost$12$and metal cost$40$. http://mathoverflow.net/questions/108834/compute-generalized-pentagram-map Comment by Michael Biro Michael Biro 2012-10-05T18:05:14Z 2012-10-05T18:05:14Z I don't think that's a serious issue. Just find the convex hull first, and if the points are degenerate, move down to the proper dimension so that the half-space intersection idea works. http://mathoverflow.net/questions/108834/compute-generalized-pentagram-map Comment by Michael Biro Michael Biro 2012-10-04T18:20:46Z 2012-10-04T18:20:46Z Is$d$fixed? Naively, you can take every collection of$d$points, check if there are at most$t$points on one side, then intersect those$n^d$half-spaces. http://mathoverflow.net/questions/106754/detecting-a-hidden-convex-body-with-line-probes Comment by Michael Biro Michael Biro 2012-09-10T03:37:58Z 2012-09-10T03:37:58Z I think it might be possible to extend the$f(2) = \frac{1}{3}$example to show that$f(k) \leq \frac{1}{k+1}$. Cut the sphere equitably into two spherical caps and$k-1$sandwiches, then orient the probes so that when projected along the axis of the sandwiches, they are the center diagonals of a regular$2k$-gon. The ordering of the diagonals seems to matter, and I haven't gone through the details, but I think it should work. http://mathoverflow.net/questions/106392/lower-bound-on-py-3-2-ey-where-y-of-triangles-in-graph Comment by Michael Biro Michael Biro 2012-09-05T01:59:04Z 2012-09-05T01:59:04Z How tight do you want the bound to be? Have you looked at Chernoff bounds? http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube/103912#103912 Comment by Michael Biro Michael Biro 2012-08-07T15:31:50Z 2012-08-07T15:31:50Z Still no arrangement of$(3n^2-1)/2$for general$n$, but this solution is symmetric enough that I'm somewhat confident that it's possible. Maybe the arrangements will be different for$n$even, vs odd? http://mathoverflow.net/questions/103882/minimal-blocking-objects-with-shadows-like-a-cube/103921#103921 Comment by Michael Biro Michael Biro 2012-08-04T14:42:15Z 2012-08-04T14:42:15Z Is your$C_3(4)$example connected? It seems like the component of$3\$ in the bottom right corner of the first picture never connects to the rest.