User michael biro - MathOverflow

Answer by Michael Biro for Untangling entwined rigid chains in 3-space

2013-02-24T21:52:38Z

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.

For now, I'm restricting to translations only.

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.

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.

Does that make sense?

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.

Answer by Michael Biro for Unique circular ordering of edges around a vertex

2013-01-16T19:40:14Z

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.

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

Answer by Michael Biro for Is there a simple test to determine whether a polytope is integral?

2012-10-24T03:50:36Z

An incomplete solution:

There is a polynomial-time test for total unimodularity, and if $A$ is totally unimodular, then the polytope is integral.

Answer by Michael Biro for Maximizing the number of lattice points in a circle of radius $r$ placed on a lattice

2012-10-21T16:58:06Z

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

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.

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.

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.

I suspect that the three possible centers cycle through as optimal solutions.

Answer by Michael Biro for How many binary operations are associative?

2012-10-21T03:58:27Z

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.

The Number of Semigroups of Order $n$

Answer by Michael Biro for 2D Problems Which are Easier to Solve in 3D

2012-09-10T03:50:22Z

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.

Answer by Michael Biro for Minimal blocking objects with shadows like a cube

2012-08-04T04:35:41Z

Here is a way to get $26$ for the $C_3(4)$ case, and $2(n^2-n) + 2$ in general.

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.

 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

In general, that works out to $C_3(n) \leq (4n-5) + (n-2)^2 + 3 + n(n-2) = 2(n^2 - n) + 2$

Edit: My $26$ bound for $C_3(4)$ has since been improved, but here is an optimal $C_3(5) = 37$ arrangement.

Area ratio of a minimum bounding rectangle of a convex polygon

2012-04-08T21:35:13Z

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.

Is this known? Is there a nice proof/counterexample for it?

Answer by Michael Biro for Readings for an honors liberal art math course

2012-02-19T18:41:22Z

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.

Answer by Michael Biro for Getting started: combinatorial optimization for computer scientists

2011-12-20T07:10:03Z

For the short version, Combinatorial Optimization by Papadimitriou and Stieglitz is a good introduction, and at $12, you can't really go wrong.

For the in-depth version, Combinatorial Optimization by Schrijver is pretty encyclopedic.

Answer by Michael Biro for A book in topology

2011-12-19T18:21:34Z

I'd recommend a combination. Topology by Munkres for the point set stuff, and Algebraic Topology 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.

Ratio of Sequences Sum Inequality

2011-12-14T16:22:46Z

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 < 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 < b_i/e^{b_i})$

They're not necessarily monotonic, so I can't use Chebyshev's inequality. Is there something else that I'm missing?

Edit:

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)}$.

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 < \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.

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$?

Answer by Michael Biro for Characteristics of locally triangle-free graph

2011-12-08T03:48:43Z

$G$ isn't necessarily connected.

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.

Then, $G$ contains no triangle, and consists of vertices $1,3,$ and $4$, along with edge $(3,4)$, and isn't connected.

Answer by Michael Biro for Smallest containing simplex

2011-12-01T08:33:56Z

The paper Parallelotopes of Maximum Volume in a Simplex 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.

Answer by Michael Biro for $\kappa$-coloring of $\mathbb{R}^2$ and triangle with area 1

2011-11-30T02:45:12Z

I think that you can always find such a triangle for any finite $\kappa$. Not sure how to prove that though.

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 < 1$.

Answer by Michael Biro for Nim-like(?) game winning strategy?

2011-11-21T14:17:29Z

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.

Edit: False statement removed, see answer by Joshua Erde.

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.

Using dynamic programming it can be done in polynomial time.

Answer by Michael Biro for Maximum graph cut in directed planar graphs

2011-11-09T23:44:25Z

This paper http://web.cs.gc.cuny.edu/~mlampis/papers/dtreewidthDO.pdf 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.

Answer by Michael Biro for Complexity of detecting a convex body in $\mathbb{R}^n$?

2011-11-07T17:56:25Z

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.

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.

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.

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.

Maximizing the number of 'correct' literals in planar monotone 3SAT

2011-03-03T01:07:25Z

I'm trying to find the complexity of this optimization problem:

Given an instance of planar monotone 3SAT, with positive clauses $C_i = v_{i1} V v_{i2} V v_{i3}$ and negative clauses $D_i = not(w_{i1}) V not(w_{i2}) V not(w_{i3})$ , (it's possible that $v_{ij} = w_{jl}$ for some i,j,k,l), find the 0-1 assignment that maximizes the number of agreeing literals. Basically, maximize $(/sum_{C_i} v_{i1}+v_{i2}+v_{i3}) + (/sum_{D_i} 3 - w_{i1} - w_{i2} - w_{i3})$ .

Thanks

Network flow gadget

2010-06-24T16:29:02Z

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?

If m = 1, we can just connect the source to the destinations and use the integral flow theorem, but what about m > 1?

When is a triangular matrix totally unimodular?

2010-06-14T15:35:14Z

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?

Comment by Michael Biro

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

Comment by Michael Biro

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?

Comment by Michael Biro

2013-03-31T02:43:31Z

That's what I did too, except I had longer (short paragraph) description for each of research and teaching.

Comment by Michael Biro

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?

Comment by Michael Biro

2013-02-25T01:12:35Z

Yes, I meant the plane containing the spiral, perpendicular to the axis.

Comment by Michael Biro

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!

Comment by Michael Biro

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.

Comment by Michael Biro

2012-10-21T04:10:25Z

Also in the line is oeis.org/A023814, which gives values up to $n = 7$.

Comment by Michael Biro

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$.

Comment by Michael Biro

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.

Comment by Michael Biro

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.

Comment by Michael Biro

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.

Comment by Michael Biro

2012-09-05T01:59:04Z

How tight do you want the bound to be? Have you looked at Chernoff bounds?

Comment by Michael Biro

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?

Comment by Michael Biro

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.